¿Qué tiene de malo esta prueba condicional de P = NP?

8

Recientemente he pensado la siguiente prueba de que L = P implica P = NP.

Supongamos que L = P. Deje que A sea un problema en NP. Según la definición del verificador de NP, cada solución positiva a A tiene un testigo que puede verificarse en tiempo polinómico. Como P = L, la misma solución se puede verificar en el espacio logarítmico. Así NP = NL. Pero entonces NL está contenido en P, lo que significa que NP está contenido en P y, por lo tanto, P = NP.

Según la hipótesis del mercado eficiente, sospecho que esta prueba es errónea. Sin embargo, no puedo determinar la naturaleza exacta del error. ¿Alguien puede señalarlo?

user44898
fuente

Respuestas:

9

Supongamos que L = P. Deje que A sea un problema en NP. Según la definición del verificador de NP, cada solución positiva a A tiene un testigo que puede verificarse en tiempo polinómico. Como P = L, la misma solución se puede verificar en el espacio logarítmico. Así NP = NL.

No has demostrado que NP=NL . El único método que has derivado para mostrar queXUNA, es no adivinar "adivinar" un testigo yy use el algoritmo determinista de espacio de registro para verificarlo. Sin embargo,yen sí mismo puede ser polinómicamente largo, mientras que su máquina NL solo puede adivinar logarítmicamente muchos bits: su máquina NL no tiene suficiente espacio para almacenar el testigo, por lo que no tiene un algoritmo NL .

Además, nota que ya sabemos que los testigos de NP problemas -Complete puede ser verificada en una clase de complejidad menor que  L . El teorema de Fagin dice que NP es exactamente el conjunto de problemas que se pueden definir en el fragmento existencial de la lógica de segundo orden. Esto es equivalente a decir que puede verificar un testigo de longitud polinómica usando lógica de primer orden. FO es estrictamente más débil que L , ya que la lógica de primer orden no puede resolver problemas simples de espacio de registro como decirle si su cadena testigo contiene un número par de 1s.

David Richerby
fuente