Expliquer la preuve par Vinay Deolalikar que P! = NP [fermé]

Question

Récemment il y a eu un papier flottant autour de Vinay Deolalikar à HP Labs qui prétend avoir prouvé que P! = NP .

Quelqu'un pourrait-il expliquer comment fonctionne cette preuve pour nous moins mathématiquement les gens enclins?

Answer 1

Je n'ai scruté à travers le papier, mais voici un résumé sommaire de comment tout se tient.

De la page 86 du document.

  

... polynomiale   algorithmes réussissent par successivement   « Casser » le problème en   plus petits sous-problèmes qui sont liés à   l'autre est conditionnelle   indépendance. Par conséquent, polynomiale   Les algorithmes de temps ne peuvent pas résoudre   problèmes dans les régimes où les blocs dont   ordre est le même que le sous-jacent   par exemple des problèmes nécessitent simultanément   résolution.

D'autres parties du document montrent que certains problèmes NP ne peut pas être divisé de cette manière. Ainsi NP / = P

Une grande partie du document est consacré à la définition de l'indépendance conditionnelle et prouver ces deux points.

Answer 2

Dick Lipton a une belle entrée de blog sur le papier et ses premières impressions de celui-ci. Malheureusement, il est aussi technique. D'après ce que je peux comprendre, l'innovation principale de Deolalikar semble être d'utiliser des concepts de la physique statistique et la théorie des modèles finis et de les attacher au problème.

Je suis avec Rex M avec celui-ci, des résultats, la plupart du temps les mathématiques ne peuvent pas être exprimés à des personnes qui ne disposent pas de la maîtrise technique.

Answer 3

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, le problème de satisfiabilité booléenne, qui demande si une collection d'états logiques peuvent tous être simultanément vraies ou si elles se contredisent. Ceci est connu pour être un problème NP.

     

Deolalikar prétend avoir montré que   il n'y a pas de programme qui peut compléter   rapidement à partir de zéro, et que   est donc pas un problème P. Le sien   l'argument implique l'utilisation ingénieuse de   la physique statistique, comme il utilise un   structure mathématique qui suit   un grand nombre des mêmes règles que random   système physique.

Les effets de ce qui précède peut être tout à fait significatif:

  

Si le résultat se, il prouverait   que les deux classes P et NP ne sont pas   identiques et imposent des limites sévères   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 ne   dire clairement si elles peuvent être résolus   rapidement. Mais un énorme sous-classe de   problèmes dits « NP-complets » seraient   condamné. Un exemple célèbre est le   problème du voyageur de commerce - trouver   le plus court chemin entre un ensemble de   villes. De tels problèmes peuvent être   rapidement, mais si P ≠ NP alors il y a   aucun programme informatique qui peut compléter   les rapidement à partir de zéro.

Answer 4

Ceci est ma compréhension de la technique de preuve: il utilise la logique de premier ordre pour caractériser tous les algorithmes de temps polynomiale, puis montre que pour les grands problèmes SAT avec certaines propriétés qu'aucun algorithme de temps polynomial peut déterminer leur satisfiabilité.

Answer 5

Une autre façon de penser à ce sujet, qui peut être tout à fait tort, mais ma première impression que je lis sur la première passe, est que nous pensons à l'attribution / termes de compensation dans la satisfaction du circuit de formage et la rupture des grappes de « structure ordonnée », et qu'il est alors en utilisant la physique statistique pour montrer qu'il n'y a pas assez de vitesse dans les opérations polynomiales pour effectuer ces opérations dans un « espace de phase » particulière des opérations, parce que ces « clusters » finissent par être trop loin à part.

Answer 6

Cette preuve devrait couvrir toutes les classes d'algorithmes, comme l'optimisation globale continue .

Par exemple, dans le problème 3-SAT , nous devons évaluer les variables à remplir toutes les alternatives de triplets de ces variables ou leurs négations. Regarde, x OR y peut être changée en optimisation

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

et analogue termes sept pour alternative de trois variables.

Trouver le minimum global d'une somme de ces polynômes pour tous les termes résoudrait notre problème. ()

Il va de techniques combinatoires standard au monde continue des méthodes de using_gradient, minims locales Supprimer les méthodes, les algorithmes évolutifs. Il est complètement différent royaume - analyse numérique - Je ne crois pas que cette preuve pourrait vraiment la couverture

(?)

Answer 7

Il convient de noter que des preuves, « le diable est dans le détail ». La vue d'ensemble de haut niveau est évidemment quelque chose comme:

  

Certains une sorte de relation   entre les éléments, montrer que cette   relation implique X et que   implique Y et donc mon argument est   représenté.

Je veux dire, il peut être par induction ou toute autre forme de prouver les choses, mais ce que je veux dire, est le haut niveau aperçu est inutile. Il est inutile de l'expliquer. Bien que la question se rapporte à l'informatique, il est préférable de laisser aux mathématiciens (pensé qu'il est certainement très intéressant).