Vinay Deolalikar de HP Labs a récemment publié un article qui prétend avoir prouvé que P! = NP . Quelqu'un pourrait-il expliquer comment cette preuve fonctionne pour nous, les personnes moins enclines à la mathématique?
Réponses
Trop de publicités?
OK, donc je ne l'ai scanné à travers le papier mais voici un sommaire de comment tout se tient ensemble.
À partir de la page 86 du papier.
... temps polynomial les algorithmes de réussir successivement "casser" le problème en les petits sous-problèmes qui sont liés à les uns des autres par le biais conditionnel de l'indépendance. Par conséquent, le polynôme algorithmes temps ne peut pas résoudre les problèmes dans les régimes où les blocs dont le l'ordre est le même que le sous-jacent problème exemple, exiger simultanée la résolution.
D'autres parties de l'article montrent que certains problèmes NP ne peut être rompu de cette manière. Donc NP/= P
Beaucoup de ce document est consacrée à la définition d'indépendance conditionnelle, et à prouver que ces deux points.
recipriversexclusion
Points
1195
Dick Lipton a un bon article de blog sur le papier et ses premières impressions. Malheureusement, c'est aussi technique. D'après ce que je peux comprendre, la principale innovation de Deolalikar semble être d'utiliser certains concepts de la physique statistique et de la théorie des modèles finis et de les lier au problème.
Je suis avec Rex M avec celui-ci, certains résultats, principalement mathématiques, ne peuvent pas être exprimés à des personnes qui manquent de la maîtrise technique.
Tony Breyal
Points
2707
J'ai aimé ce ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ):
Son argument tourne autour d'une tâche particulière, la satisfiabilité Booléenne problème, qui est de savoir si une collection de déclarations logiques peuvent tous être simultanément vraies ou si elles se contredisent l'une l'autre. Ceci est connu pour être un problème NP.
Deolalikar prétend avoir montré que il n'existe pas de programme qui peut compléter il est rapidement à partir de zéro, et qu'il n'est donc pas un P problème. Son argument implique l'utilisation ingénieuse de l' la physique statistique, comme il utilise un structure mathématique qui suit les mêmes règles aléatoire le système physique.
Les effets de la ci-dessus peuvent être très importantes:
Si le résultat est, il s'avère que les deux classes P et NP sont pas identiques, et d'imposer des limites strictes sur ce que les ordinateurs peuvent accomplir – ce qui implique que de nombreuses tâches peuvent être fondamentalement, irréductiblement complexe.
Pour certains problèmes – y compris factorisation – le résultat n'est pas clairement dire qu'ils peuvent être résolus rapidement. Mais un énorme sous-classe de problèmes appelé "NP-complet" serait vouée à l'échec. Un exemple célèbre est l' problème du voyageur de commerce – trouver l'itinéraire le plus court entre un ensemble de des villes. De tels problèmes peuvent être vérifiées rapidement, mais si P ≠ NP alors il est pas de programme d'ordinateur qui peut compléter rapidement à partir de zéro.
smith
Points
41
C’est ce que je comprends de la technique de preuve: il utilise la logique du premier ordre pour caractériser tous les algorithmes de temps polynomiaux, puis montre que, pour les grands problèmes de SAT avec certaines propriétés, aucun algorithme de temps polynomial ne peut déterminer leur satisfiabilité.
John with waffle
Points
3472
Une autre façon d’y penser, ce qui peut être totalement faux, mais c’est ma première impression, telle que je la lis au premier passage, est que nous pensons attribuer / clarifier les termes relatifs à la satisfaction du circuit comme formant et brisant des grappes de structure "et qu'il utilise ensuite la physique statistique pour montrer que les opérations polynomiales ne sont pas assez rapides pour effectuer ces opérations dans un" espace phase "d'opérations donné, car ces" grappes "finissent par être trop éloignées les unes des autres.
