NP = coNP implique-t-il P = NP?

8

Nous savons que P = NP implique NP = coNP. L'implication inverse tient-elle? Est-ce que NP égal à coNP implique que P est égal à NP? Sinon pourquoi pas?

J'ai googlé mais je n'ai pas trouvé la réponse.

James Johnson
la source

Réponses:

6

Le cas PNP=coNPest possible. La raison pour laquelleP=NP implique NP=coNP est-ce P est fermé sous complément, et donc si P=NP, NP doit également être fermé sous complément.

Une classe fermée sous complément n'implique pas nécessairement quoi que ce soit sur son homologue déterministe. Par exemple, nous savons queNL est fermé sous complément, mais je ne sais pas si L=NL.

Mike B.
la source