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

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?

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 que$x\in A$, consiste à "deviner" de façon non déterministe un témoin $y$et utiliser l'algorithme déterministe de l'espace de journalisation pour le vérifier. cependant,$y$elle-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 $1$s.