¿Por qué es incorrecto este argumento para ?

11

Sé que es una tontería, pero logré confundirme y necesito ayuda para resolver esto

Suponga que P=NP , entonces claramente para cada oráculo A tenemos PA=NPA que contradice el hecho de que existe algún oráculo A para el cual PANPA , de ahí PNP

Que pasa ¡Gracias!

Ariel
fuente

Respuestas:

13

Claro, solo debes tener cuidado al pensar en lo que significa tener un oráculo.

El problema proviene de un molesto abuso de notación que usamos en CS: en la declaración P=NP , P refiere a un conjunto de lenguajes. Pero en el enunciado PA=NPA , P refiere a una clase de máquinas de Turing (Polytime TM determinístico). Debería pensar en estas dos P como de tipos completamente diferentes.

Por lo tanto, incluso si los dos conjuntos de lenguajes y son iguales, los TM polytime deterministas aún no funcionan de la misma manera que los no deterministas. En particular, dado un oráculo, una TM no determinista puede "hacer muchas preguntas a la vez", que es algo que la TM normal no puede hacer. Entonces, incluso si deciden el mismo conjunto de idiomas cuando ninguno de los tipos de máquina recibe ayuda adicional, el oráculo podría ayudar a un tipo de máquina más que a otro.PNP

usul
fuente