NP = coNP implica P = NP?

8

Sabemos que P = NP implica NP = coNP. A implicação inversa é válida? NP igual coNP implica que P é igual a NP? Se não, por que não?

Pesquisei no Google, mas não encontrei a resposta.

James Johnson
fonte

Respostas:

6

O caso em que é possível. A razão pela qual implica é que é fechado no complemento e, portanto, se , o deve ser fechado no complemento.PNP=coNPP=NPNP=coNPPP=NPNP

Uma classe sendo encerrada sob complemento não implica necessariamente nada sobre sua contraparte determinística. Por exemplo, sabemos queNeu está fechado sob complemento, mas não sei se eu=Neu.

Mike B.
fonte