¿Defecto en mi prueba NP = CoNP?

Tengo esta "prueba" muy simple para NP = CoNP y creo que hice algo mal en alguna parte, pero no puedo encontrar lo que está mal. ¿Alguien me puede ayudar?

Sea A un problema en NP, y sea M el decisivo para A. Sea B el complemento, es decir, B está en CoNP. Dado que M es un elemento decisivo, también puede usarlo para decidir B (simplemente voltee la respuesta). ¿No significa eso que resolvemos problemas NP y CoNP con la misma M?

Para decirlo más concretamente.

Deje que A sea un problema NP-completo, y que M sea decisivo para A. Considere cualquier problema B en CoNP. Consideramos su complemento no-B, que está en NP, y luego obtenemos una reducción polinómica a A. Luego ejecutamos nuestro decisor M y volteamos nuestra respuesta. De este modo obtenemos un decisor para B. Esto implica que B también está en NP.

¿Puedo saber qué hay de malo en mi razonamiento?

Hay dos posibles errores en esta prueba:

1. Cuando dices "decisivo", te refieres a una TM determinista. En este caso, la mejor traducción (a nuestro entender) de una máquina NP a una máquina determinista puede producir una máquina que funciona en tiempo exponencial, por lo que después de complementar tendrá un decisor para el complemento en tiempo exponencial, lo que demuestra que (o, después de alguna optimización, ).c o - N P ⊆ P S P A C $co-NP\subseteq EXP$$co-NP\subseteq PSPACE$

2. Cuando dices "decisivo" te refieres a una TM no determinista. En este caso, cambiar la respuesta no necesariamente complementará el idioma. De hecho, el lenguaje de la máquina invertida será todas las palabras para las cuales existe una ejecución de rechazo de en$M$$w$

Aquí hay otra forma de ver el punto que Shaull hace con respecto a los "decisores".

Un problema está en NP si y solo si hay un algoritmo tal que$V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$

• para cada instancia SÍ , hay un certificado p ∈ { 0 , 1 } p o l y ( n ) tal que V ( x , p ) = 1 ; y$x \in \{0,1\}^n$$p \in \{0,1\}^{\mathrm{poly}(n)}$$V(x,p) = 1$

• para cada instancia de NO , tenemos V ( x , p ) = 0 para todas las p ∈ { 0 , 1 } p o l y ( n ) .$x \in \{0,1\}^n$$V(x,p) = 0$$p \in \{0,1\}^{\mathrm{poly}(n)}$

Por lo general, se describen como las condiciones de integridad y solidez para el algoritmo de verificación NP : la condición de "integridad" dice que cada instancia de SÍ tiene un certificado, y la condición de "solidez" dice que el algoritmo nunca es engañado por una instancia de NO. Para coNP es al revés: hay un algoritmo verificador que aceptará al menos un certificado para cualquier instancia de NO, pero que nunca puede ser engañado por una instancia de YES.

Si desea mostrar que NP ⊆ coNP , debe mostrar que cada problema de NP tiene un verificador de tipo coNP , que puede certificar NO instancias en lugar de instancias YES. No puede hacer esto con una máquina de Turing no determinista: no hay forma de que sepamos, por ejemplo, de mapear eficientemente las instancias de SAT entre sí, de tal manera que todas las fórmulas insatisfactorias se asignen a otras satisfactorias, y viceversa.. (Negar el resultado de la fórmula no es suficiente, por ejemplo: una fórmula que es satisfactoria pero no una tautología simplemente se mapearía a una fórmula diferente que fuera satisfactoria pero no una tautología, cuando en su lugar requeriríamos una fórmula insatisfactoria). Simplemente no sabemos cómo engañar a una máquina no determinista para que detecte algo así como que todos sus caminos sean rechazados.

Puede preguntar: "¿No sabe la máquina de Turing no determinista qué resultado obtiene?" La respuesta sería no , no lo hace. El funcionamiento de la máquina no determinista no le da acceso a ninguna información sobre más de una ruta computacional a la vez: puede pensar que funciona en muchas rutas en paralelo, pero dentro de cada ruta solo conoce esa ruta. Si intenta equiparlo con la capacidad de "darse cuenta" de si hay alguna solución o no en algún momento, en su lugar, está describiendo una máquina con un oráculo NP , que es más (¡potencialmente!) Poderoso que una simple máquina de Turing no determinista.

• Por ejemplo, si usted equipa un (determinista) máquina de Turing con un NP oráculo, entonces los problemas que pueden ser resueltos en tiempo polinómico en esa máquina se llama , que a menudo se escribe P N P . El "oráculo" le permite a la máquina simplemente recibir respuestas a problemas completos de NP en un solo paso, por lo que P N P obviamente contiene P ; y debido a que puede negar respuestas, obviamente también contiene coNP . Pero no sabemos si las contenciones inversas se mantienen, exactamente porque no sabemos cómo engañar a las máquinas de Turing no deterministas para que no detecten respuestas.$\Delta_2^{\mathrm P}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$

• $\Sigma_2^{\mathrm P}$$\mathsf{NP}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$no tiene respuesta debido al oráculo, pero aún estaría atascado a operar dentro de una de sus propias ramas computacionales (bastante poderosas), de modo que no podría saber si todas sus propias ramas computacionales estaban rechazando.

$\mathsf{NP}$$\mathsf{NP}^{\mathsf{NP}}$

Entonces, no, no hay una máquina (determinista o no) que pueda simplemente "decidir" que un problema es una instancia SÍ o NO de manera eficiente, a menos que usemos oráculos; pero incluso con tal oráculo, terminamos con una máquina que es (probablemente) más poderosa que NP o coNP , no una que muestre que son iguales.

Su razonamiento implica que RE = coRE, pero esto es demostrablemente falso. Podría intentar descubrir una prueba de eso y luego ver dónde falla su reducción.

$\{ x : P \text{ halts on input } x \}$$\{ x : (x,w) \in L' \text{ for some } w \}$$L'$

$L = \{ x : p \text{ halts on input } x \}$$L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$$L'$$L = \{ x : (x,w) \in L' \text{ for some } w \}$

$L = \{ x : (x,w) \in L' \text{ for some } w \}$$L'$$P(x,w)$$Q(x)$$w$$P(x,w)$$w$$P(x,w)$$w$$Q$$L = \{ x : Q \text{ halts on input } x \}$

$L = \{(P,x) : P \text{ halts on input x}\}$$P$$x$$H$$H(P,x)$$(P,x) \notin L$$G$$G(x)=H(x,x)$$(G,G) \in L$$G$$G$$H$$(G,G)$$(G,G) \notin L$$(G,G) \notin L$$G$$G$$H$$(G,G)$$(G,G) \in L$$H$

$H$

Aquí hay una versión TL; DR; También publiqué una respuesta más larga a una pregunta similar.

$A$$M$$x\in A$$M$$x$$M$$x$. Si simplemente invierte los estados de aceptación y rechazo, pasará de una máquina que tenía algunas rutas de aceptación y algunas de rechazo a una máquina que tiene algunas rutas de rechazo y algunas de aceptación. En otras palabras, todavía tiene caminos de aceptación, por lo que todavía acepta. Voltear los estados de aceptar y rechazar de una máquina no determinista, en general, no hace que acepte el lenguaje complementario.

Es esta asimetría de definición (aceptar si alguna ruta acepta; rechazar solo si todas las rutas rechazan) lo que dificulta el problema NP vs co-NP .

De hecho, estoy de acuerdo en que su máquina no determinista M puede decidir si una cadena de entrada dada está en B. Sin embargo, "decide" de forma ligeramente diferente a la forma en que decide si una entrada dada está en A. En el último caso, lo hace por ( no determinista) encontrar un estado de aceptación. En el primer caso, lo hace al no encontrar ningún estado de aceptación. ¿Por qué importa esta diferencia? Veamos:

Al preguntar M "¿Está la cadena en el idioma A?"

M alcanza un estado de aceptación. Esto, usted puede probar (ver, por ejemplo, el teorema del libro de Sipser 7.20) implica que hay una máquina determinista que verifica que la cadena está en A en tiempo polinómico

Al preguntar M "¿Está la cadena en el idioma B?"

M alcanza estados de rechazo en todas las ramas de su cálculo no determinista. Si piensa en cómo funciona la prueba del verificador anterior, verá que no se puede lograr en esta situación. Esto se debe aproximadamente a que el verificador utiliza la ruta que M toma a través de su espacio de estado como "prueba". En este caso, no hay una ruta de ese tipo.

Conclusión:

Si considera que la existencia de un verificador determinista de tiempo polinómico para un lenguaje es la definición de un lenguaje NP (que debería), la existencia de M no prueba que B esté en NP.