¿La pregunta abierta NP = co-NP es la misma que P = NP?

12

Me pregunto esto basado en varios lugares en línea que llaman a co- un problema abierto importante ... pero no puedo encontrar ninguna indicación de si esto es lo mismo que Problema ...NP=NPP=NP

Mirrana
fuente

Respuestas:

20

No. Es otro problema abierto y ciertamente relacionado, pero diferente. La clase de complejidad co-NP es el conjunto de idiomas cuyos complementos están en ; es decir, el conjunto de problemas de decisión para los cuales una respuesta "no" tiene un verificador determinístico de tiempo polinómico. Entonces, por ejemplo, la pregunta "¿Es esta fórmula SAT insatisfactoria?" Si la respuesta es "no", entonces hay una asignación satisfactoria de las variables que lo prueba; ese es el certificado para el verificador.NP

Es posible que , pero co- .PNPNP=NP

Pero, por otro lado, si , entonces co- seguro. Esto se debe a que si un idioma está en , entonces su complemento también está en , por lo que si , eso se aplica a todos los idiomas en también.P=NPNP=NPPPP=NPNP

usul
fuente
44
también si NP coNP entonces P NP porque P está cerrado bajo el complemento. entonces la pregunta NP coNP puede ser tan difícil como el infame problema P NP. =?=?
vzn
2
Sí, buen punto!
usul
1
Sin embargo, como una adición a eso, acabo de ver una afirmación en un documento de que NP = coNP es ampliamente creído.
vzn
4

Una buena manera de responder a esta pregunta es usar la jerarquía polinómica (PH) (ver también aquí ). La jerarquía polinómica es una jerarquía de clases de complejidad que generaliza las clases , y a las máquinas Oracle y se usa como una escala para medir la complejidad de los problemas.PNPcoNP

Se sabe que si o , la jerarquía polinómica se colapsa a su primer nivel.NP=coNPP=NP

Reza
fuente