Ca alors, à 4 ans d’intervalle, j’écris quasiment le même poste (je vous garantie que je n’ai pas fait exprès !).
Je me disais aussi en relisant le début qu’il y avait un problème de date sur tric trac ! Bah en fait non, c’était moi qui n’avait pas tout vu !
C’est le début du radotage 
Sir, yes sir
Jeremie dit:L'explication de greuh est fausse.
Le plus célèbre des problèmes NP que l'on aimerait bien inclure dans P est SAT (satisfiabilité d'une formule logique). Et la c'est clairement un truc que l'on peut faire en force brute avec un arbre binaire.
Euh, quand greuh dit "on ne peut pas", il veut dire "dès que l'entrée est un peu importante, c'est pas la peine d'y penser, aucun ordinateur ne pourra jamais le faire". Le problème SAT est insoluble par la force brute au-delà de 25 variables propositionnelles et le restera à jamais (c'est pourquoi on a développé les méthodes de démonstration automatiques comme le principe de résolution, notamment).
Je trouve personnellement que l'explication de greuh est excellente. Même si d'un point parfaitement rigoureux et formel, elle est contestable voire partiellement fausse (tout comme la mienne en fait), elle vulgarise très correctement la chose (et quand on vulgarise, on ment, c'est presque inévitable).
Effectivement, il y a quelques erreurs dans l’explication de Greuh. Vite fait, les classes de complexité ont été inventées pour regrouper des problèmes de difficulté jugée théoriquement similaire. Le principe est le suivant : pour un problème donné, si le résoudre permet de résoudre un autre problème, alors ils sont de la même classe.
En fait, un problème est dans NP justement quand on est obligé de construire un arbre pour le résoudre, et que la profondeur de l’arbre dépend de la taille du problème. Pour un arbre binaire de profondeur 1, ça fait 1 coup à calculer, de profondeur 2 ça fait 5, de profondeur 3 ça fait 13, de profondeur 4 ça fait 29, etc. Ça évolue de manière exponentielle. Ça ne veut pas dire qu’on ne sait pas résoudre les problèmes, mais ça veut dire qu’une simple augmentation de la taille de quelques crans va vite faire exploser les temps de calcul. SAT est le problème NP de référence. Pour montrer qu’un problème est NP-difficile, on montre que le résoudre revient à résoudre SAT.
Le truc, c’est qu’on sait que la puissance des machines augmente de manière exponentielle aussi (la fameuse « loi de Moore »). Les problèmes dans NP sont utilisés en cryptographie parce qu’on peut facilement les rendre plus difficiles plus rapidement que la puissance des ordinateurs n’augmente. Il suffit d’augmenter d’un bit la taille de la clé de cryptage pour gagner x années de développement informatique.
Dans les jeux stratégiques, la profondeur de l’arbre dépend du nombre de coups que l’on peut jouer au cours d’une partie. En fait, c’est tout comme si on était dans NP, en supposant qu’on peut augmenter le nombre de coups (généralement en augmentant la taille du plateau de jeu, c’est facile au Go ou aux Dames, moins aux échecs). Parfois (souvent), on arrive à identifier des propriétés qui permettent de ne pas avoir à explorer l’ensemble de l’arbre. Parfois, on arrive à juger quelles parties de l’arbre permettront de progresser le plus vite dans la résolution du problème. Ça permet de gagner un temps plus que précieux. Mais ça ne suffit pas, on gagne juste un cran ou deux de taille de problème… Avec des méthodes de ce genre, on peut quand même faire tomber des instances de SAT à plusieurs millions de variables plus vite qu’il n’en faut pour lire le problème sur le disque dur… Et d’autres à 30 variables qui résistent encore. Le principal problème de ces méthodes, en fait, c’est qu’on ne peut pas prévoir à l’avance combien de temps ça va prendre pour résoudre le problème.
C’est aussi pour ça que je n’aime pas vraiment parler de « force brute ». Derrière l’apparente simplicité de la recherche arborescente, il y a 50 ans de recherche scientifique qui viennent s’intercaler dans le bousin, on est loin de la brutalité.
Ben c’est gentil 
Moi, j’ai surtout utilisé des métaheuristiques, que je considère pas comme de la force brute, justement.
C’est probablement le truc qui m’as le plus passionné de mes études.
greuh, avec la metallurgie.
grolapinos dit:Sauf erreur de ma part, l'ordinateur quantique, qui va peut-être voir le jour dans les décennies à venir, est censé résoudre les problèmes non-déterministes en temps polynômial, et là, pour le coup, on est dans la vraie petite complexité puisque grosso-modo, le non-déterminisme repose en général dans le choix des instances à vérifier, donc c'est globalement du quadratique pour la plupart des problèmes NP-complets classiques.
Il ne semble pas : http://fr.wikipedia.org/wiki/Probl%C3%A ... _quantique
VictorVVV dit:grolapinos dit:Sauf erreur de ma part, l'ordinateur quantique, qui va peut-être voir le jour dans les décennies à venir, est censé résoudre les problèmes non-déterministes en temps polynômial, et là, pour le coup, on est dans la vraie petite complexité puisque grosso-modo, le non-déterminisme repose en général dans le choix des instances à vérifier, donc c'est globalement du quadratique pour la plupart des problèmes NP-complets classiques.
Il ne semble pas : http://fr.wikipedia.org/wiki/Probl%C3%A ... _quantique
Voilà ce qui arrive quand on s'aventure à parler de choses dont on n'est pas spécialiste. Je me confonds en excuses.
Tiens en passant, si P réfère bien à Polynomial, NP ne signifie pas Non Polynomial, mais Non-déterministe Polynomial. Une machine déterministe est une machine capable de développer un arbre soit en travaillant sur toutes les branches à la fois, soit en faisant systématiquement la bonne décision à chaque nœud de l’arbre. Du coup, le développement d’un arbre de profondeur quelconque se fait en temps polynomial ! On pensait que l’ordinateur quantique en serait capable, mais on en est de moins en moins surs. De plus, si c’est suffisant pour trouver en temps polynomial la solution de n’importe quel problème NP-complet, ça ne suffit pas pour prouver qu’un problème dans NP n’aurait pas de solution : il est déjà prouvé que la preuve d’insatisfaisabilité d’un problème NP-complet est de taille exponentielle.
En tout état de cause, la plupart des chercheurs ont plus ou moins laissé tomber l’idée de démontrer que P=NP ou P≠NP. Chaque année, des dizaines de preuves dans un sens ou dans l’autre sont proposées et systématiquement démontées. On cherche plutôt à résoudre des instances (par définition bornées) de problèmes NP-difficiles en temps raisonnable. Interviennent ici les métaheuristiques (qui cherchent généralement à trouver des solutions approchées), ainsi que des évolutions de la recherche arborescente (qui marchent généralement très bien !) Et là, bizarrement, rares sont les problèmes à résister longtemps au bon algorithme… Ce genre de problème est soit très artificiel, soit issu de la recherche en cryptographie (en même temps, c’est fait pour !)
scand1sk dit:Tiens en passant, si P réfère bien à Polynomial, NP ne signifie pas Non Polynomial, mais Non-déterministe Polynomial. Une machine non-déterministe est une machine capable de développer un arbre soit en travaillant sur toutes les branches à la fois, soit en faisant systématiquement la bonne décision à chaque nœud de l'arbre. Du coup, le développement d'un arbre de profondeur quelconque se fait en temps polynomial ! On pensait que l'ordinateur quantique en serait capable, mais on en est de moins en moins surs. De plus, si c'est suffisant pour trouver en temps polynomial la solution de n'importe quel problème NP-complet, ça ne suffit pas pour prouver qu'un problème dans NP n'aurait pas de solution : il est déjà prouvé que la preuve d'insatisfaisabilité d'un problème NP-complet est de taille exponentielle.
Je crois que ce que tu viens de dire est équivalent à P≠NP. Pourrais-tu sourcer ?
En tout cas merci pour la définition de machine non-déterministe.
scand1sk dit:On pensait que l'ordinateur quantique en serait capable, mais on en est de moins en moins surs.
Ah ben il me semblait bien... La superposition d'états, c'est pas fait pour les chiens !
scand1sk dit:De plus, si c'est suffisant pour trouver en temps polynomial la solution de n'importe quel problème NP-complet, ça ne suffit pas pour prouver qu'un problème dans NP n'aurait pas de solution : il est déjà prouvé que la preuve d'insatisfaisabilité d'un problème NP-complet est de taille exponentielle.
Tu veux dire qu'on sait déjà que co-NP≠P ?
Bah les ordis quantiques c’est un peu l’art de programmer avec des machines qui n’existent pas encore… Alors dire définitivement ce que l’on pourra faire ou non avec c’est un peu aléatoire.
Après moi je veux bien vulgariser un peu mais dire que l’on ne peut pas résoudre par énumération c’est quand même très très faux.
SAT sa résolution dépend effectivement bcp des instances. Toutefois si tu as une instance de taille 25 (enfin ca dépend de ce qui est de taille 25 et de ce que l’on appelle ‘force brute’) non résolue je pense qu’il y a moyen de faire un papier avec 
(ou au moins un poster). Il y a une compétition sur SAT régulièrement (la dernière que j’aie vue était organisée en 07 par l’univ d’Artois et les plus petits problèmes un peu coriaces étaient de taille 45 et pourtant les solvers ont tendance à faire une sorte d’énumération guidée par une heuristique).
Les arbres de jeux je pense que la on s’éloigne pas mal de la question par contre on s’approche d’un domaine ou j’ai une vraie expertise. Je pense que c’est un mauvais exemple car il y a souvent la notion d’adversaire, voire d’équilibre de Nash qui font que clairement tout l’arbre n’est pas à considérer de la même façons.
Enfin la on est en train de dériver grave…
grolapinos dit:Tu veux dire qu'on sait déjà que co-NP≠P ?
C'est équivalent à NP≠P d'après Wiki :
P, the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases (and demonstrably cannot be strict in one case but not the other).
http://en.wikipedia.org/wiki/Co-NP
Jeremie dit:Bah les ordis quantiques c'est un peu l'art de programmer avec des machines qui n'existent pas encore... Alors dire définitivement ce que l'on pourra faire ou non avec c'est un peu aléatoire.
Les machines de Turing ont été créées pour modéliser la calculabilité théorique bien avant que le premier ordinateur ait été construit. Il n'y a rien d'aléatoire ni de fantaisiste à développer une théorie de la calculabilité quantique avant que ces ordinateurs voient le jour.
Jeremie dit:SAT sa résolution dépend effectivement bcp des instances. Toutefois si tu as une instance de taille 25 (enfin ca dépend de ce qui est de taille 25 et de ce que l'on appelle 'force brute') non résolue je pense qu'il y a moyen de faire un papier avec
Tu as raison pour le nombre de variables, j'ai mis 25 sans réfléchir et c'est clairement ridicule, le bon ordre de grandeur est plutôt 50. Je ne comprends pas ton "et pourtant".
Jeremie dit:Après moi je veux bien vulgariser un peu mais dire que l'on ne peut pas résoudre par énumération c'est quand même très très faux.
Oui et non. En fait, il manque surtout des ordres de grandeur (précis, pas balancés au petit bonheur comme je l'ai fait).
Jeremie dit:Les arbres de jeux je pense que la on s'éloigne pas mal de la question par contre on s'approche d'un domaine ou j'ai une vraie expertise. Je pense que c'est un mauvais exemple car il y a souvent la notion d'adversaire, voire d'équilibre de Nash qui font que clairement tout l'arbre n'est pas à considérer de la même façons.
Là encore, c'est ramener une réalité scientifique délicate à des choses que le lecteur connaît. En probas, on dit souvent que le Go est markovien, contrairement aux échecs. C'est contestable pour les raisons que tu donnes, mais encore une fois, ça "vulgarise".
Jeremie dit:Enfin la on est en train de dériver grave...
Je ne comprends pas ce que tu veux dire.
VictorVVV dit:grolapinos dit:Tu veux dire qu'on sait déjà que co-NP≠P ?
C'est équivalent à NP≠P d'après Wiki :P, the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases (and demonstrably cannot be strict in one case but not the other).
http://en.wikipedia.org/wiki/Co-NP
C'est ce qui me semble aussi, c'est pour ça que je pense que nous avons mal compris ce que disait scand1sk et que je lui pose la question en termes précis.
Pour le dériver grave, il était tard (retour de rando roller) et je voulais juste dire que l’on s’enfonçait dans des discussions pas forcément très compréhensibles sans background.
Il n’y a rien d’aléatoire ni de fantaisiste à développer une théorie de la calculabilité quantique avant que ces ordinateurs voient le jour.
Je pense pour le coup que le cadre n’est pas aussi clair que celui des machines de turing. En plus sans bien connaitre le domaine, je crois que plusieurs classes de composants quantiques existent et que l’on ne sait pas trop quels sont ceux qui sont physiquement possible (et il me semble que l’un d’entre eux permettrait effectivement de faire tomber SAT en temps polynomial si l’on possède suffisamment de bits quantiques et accessoirement RSA et à peu près tous les trucs combinatoires).
Sauf que pour le moment ca ne marche pas… Le seul truc qui soit tip top la dedans c’est la cryptographie justement. C’est déjà déployé pour quelques application hyper critiques et c’est d’un point de vue théorique quasi-inviolable (proba 1/2^(longueur message) mais en pratique il y a quelques merdouilles)
Au fait juste pour le fantasme, savez vous que l’on possède dans le cerveau de tous petits tubes dont l’intérieur semble suffisamment isolé du monde extérieur pour permettre de mener des calculs quantiques (attention il n’y a pas de preuves que ca se ferait).
On l’a p’tet sur les épaules l’ordi quantique. Personnellement je suis toujours étonné de voir comment les meilleurs humains sont capables d’approcher un équilibre de Nash ou une stratégie optimale y compris dans les cas difficiles (poker, Go)
grolapinos dit:VictorVVV dit:grolapinos dit:Tu veux dire qu'on sait déjà que co-NP≠P ?
C'est équivalent à NP≠P d'après Wiki :P, the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases (and demonstrably cannot be strict in one case but not the other).
http://en.wikipedia.org/wiki/Co-NP
C'est ce qui me semble aussi, c'est pour ça que je pense que nous avons mal compris ce que disait scand1sk et que je lui pose la question en termes précis.
J'ai un doute là, je vais vérifier. Il est bien possible que le théorème contienne un méchant « si P≠NP » au début de celui-ci
scand1sk dit:J'ai un doute là, je vais vérifier. Il est bien possible que le théorème contienne un méchant « si P≠NP » au début de celui-ci
À la réflexion, c'est trivial. Comme les problèmes P sont reconnus par des machines déterministes, on a co-P=P en échangeant les états acceptants et refusants, si bien que P=NP <=> co-P=co-NP <=> P=co-NP.
CQFD.
grolap', qui se réveille tard.
grolapinos dit:Le topic à déterrer tous les quatre ans... Encore deux français médaille Fields cette année
Si je n'ai jamais entendu parler de Ngô Bao-Châu, je connais un peu Cédric Villani, personnellement mais aussi professionnellement puisqu'il était président de mon jury de thèse. Je suis extrêmement heureux pour lui, c'est un type vraiment bien à plein de points de vue.
Je note aussi qu'un mathématicien russe a été récompensé pour ses travaux en percolation (un problème difficile de physique statistique donnant lieu à des modèles mathématiques très élégants). Après Werner il y a quatre ans, je suis content de voir que les probabilités au sens large sont définitivement considérées comme un domaine d'étude prestigieux pour autre chose que pour leurs sinistres applications en finance.
Pour en revenir à la médaille Fields, j'en profite pour placer ce lien vers un blog consacré aux math que j'aime bien et qui justement parle un peu des nouveaux lauréats :
http://eljjdx.canalblog.com/archives/2010/08/22/18868585.html