Quel est le problème avec cette preuve conditionnelle de P = NP?

8

J'ai récemment imaginé la preuve suivante que L = P implique P = NP.

Supposons que L = P. Soit A un problème dans NP. Selon la définition du vérificateur de NP, chaque solution positive à A a un témoin qui peut être vérifié en temps polynomial. Puisque P = L, la même solution peut être vérifiée dans l'espace logarithmique. Ainsi NP = NL. Mais alors NL est contenu dans P, ce qui signifie que NP est contenu dans P et donc P = NP.

Par l'hypothèse d'un marché efficace, je soupçonne que cette preuve est erronée. Je ne suis cependant pas en mesure de déterminer la nature exacte de l'erreur. Quelqu'un peut-il le signaler?

user44898
la source

Réponses:

9

Supposons que L = P. Soit A un problème dans NP. Selon la définition du vérificateur de NP, chaque solution positive à A a un témoin qui peut être vérifié en temps polynomial. Puisque P = L, la même solution peut être vérifiée dans l'espace logarithmique. Ainsi NP = NL.

Vous n'avez pas montré que NP=NL . La seule méthode que vous avez dérivée pour montrer queXUNE, consiste à "deviner" de façon non déterministe un témoin yet utiliser l'algorithme déterministe de l'espace de journalisation pour le vérifier. cependant,yelle-même peut être polynomiale, tandis que votre machine NL ne peut que deviner logarithmiquement de nombreux bits: votre machine NL n'a pas assez d'espace pour stocker le témoin, vous n'avez donc pas d' algorithme NL .

Aussi, notez que nous savons déjà que les témoins de NP problèmes de peut être vérifiée dans une classe de complexité plus petite que  L . Le théorème de Fagin dit que NP est exactement l'ensemble des problèmes qui peuvent être définis dans le fragment existentiel de la logique du second ordre. Cela revient à dire que vous pouvez vérifier un témoin de longueur polynomiale en utilisant une logique de premier ordre. FO est strictement plus faible que L , car la logique de premier ordre ne peut pas résoudre de simples problèmes d'espace de journalisation comme vous dire si votre chaîne témoin contient un nombre pair de 1s.

David Richerby
la source