¿NP = coNP implica P = NP?

8

Sabemos que P = NP implica NP = coNP. ¿Se cumple la implicación inversa? ¿NP es igual a coNP implica que P es igual a NP? ¿Si no, porque no?

Busqué en Google pero no encontré la respuesta.

James Johnson
fuente

Respuestas:

6

El caso de que es posible. La razón por la cual implica es que está cerrado bajo el complemento, por lo que si , debe estar cerrado bajo el complemento.PNP=coNPP=NPNP=coNPPP=NPNP

Una clase cerrada bajo complemento no implica necesariamente nada sobre su contraparte determinista. Por ejemplo, sabemos que está cerrado bajo complemento, pero no sabemos si .NLL=NL

Mike B.
fuente