Si algo puede ser decidido en el polinomio tiempo con un NP oracle, ¿por qué no es en NP? Se podría pensar que si se ejecutó un polinomio de tiempo de máquina de Turing no determinista exponencialmente muchas veces, que sólo serviría para aumentar su esfuerzo por un polinomio tiempo multiplicador, lo que significa que el problema podría ser resuelto por una máquina de Turing no determinista en tiempo polinomio.
Respuesta
¿Demasiados anuncios?
En realidad, es posible que $\mathrm{NP}=\mathrm{P}^{\mathrm{NP}}$, es incluso posible que todo Polinomio de Jerarquía se derrumba hacia abajo a $\mathrm{P}$ (lo que sucedería si, y sólo si, $\mathrm{P}=\mathrm{NP}$)!
La pregunta correcta debería decir "¿por Qué no es obviamente cierto que $\mathrm{NP}=\mathrm{P}^{\mathrm{NP}}$?". La respuesta está relacionada con la forma $\mathrm{NP}$ funciona cuando se utiliza directamente, o ser utilizado como un oráculo.
Una de las debilidades de $\mathrm{NP}$ es la negación. En orden para que un problema de pertenecer a $\mathrm{NP}$, se necesita un poco de polinomio de tiempo determinista algoritmo de $A$, el cual debe tener dos propiedades:
- Por cada "positivo" de la instancia, debe ser posible encontrar un testigo que puede ser utilizado para convencer a $A$ que la respuesta del problema es, de hecho, "sí".
- Por cada negativo instancia, ningún testigo puede ser usado para engañar a $A$ en el pensamiento de que la respuesta es "sí".
Nota la asimetría, "sí" instancias de pedir sólo un único testigo, pero "no" requieren que ninguno existe.
Como un ejemplo, considere el problema SAT = satisfiability de fórmula proposicional. Es fácil ver que para cada conste fórmula, cualquier satisfacción de asignación de las variables puede ser utilizado como testigo y si $A$ funciona mediante la comprobación de si la asignación de siempre, de hecho satisface la fórmula, que no puede ser engañado por cualquier falso podría ser testigos. Por lo tanto, el SAT problema es, sin duda, en $\mathrm{NP}$.
Sin embargo, ¿puede pensar en alguna manera de cómo producir polinomio de tiempo seleccionable testigos (y la correspondiente corrector $A$) para el problema de UNSAT, que pregunta si una fórmula es no válido? Por el momento, nadie sabe cómo hacerlo, o si incluso es posible [si se puede hacer, escribir y vas a ser famoso :-) ]
Ahora bien, si tenemos un $\mathrm{NP}$ oracle, todo esto se oculta de nosotros; nos acaba de obtener una caja mágica que responde correctamente a "sí" o "no" para la satisfiability problema (que hemos demostrado ser en $\mathrm{NP}$). Podemos, simplemente, de la mano de la fórmula y pedir "Es esto válido?" y justo de la salida de la negación de lo que dice. Bang, hemos demostrado que UNSAT pertenece a $P^\mathrm{NP}$ (de hecho, hemos utilizado el oráculo sólo una vez).
Por lo tanto, sabemos que $\mathrm{NP}\subseteq \mathrm{P}^\mathrm{NP}$, pero si la inclusión es estricta sigue siendo una cuestión abierta. De hecho, esto también explica por qué la clase $\mathrm{co-NP}$ (que consta de complementos de $\mathrm{NP}$ problemas; es decir, los problemas cuando el testigo está obligado por el "no" y su no-existencia es necesaria para el "sí" casos), en realidad, es muy interesante.
