Bedeutet NP = coNP P = NP?

8

Wir wissen, dass P = NP NP = coNP impliziert. Gilt die umgekehrte Implikation? Bedeutet NP gleich coNP, dass P gleich NP ist? Wenn nicht, warum nicht?

Ich habe gegoogelt, aber keine Antwort gefunden.

James Johnson
quelle

Antworten:

6

Der Fall, dass ist, ist möglich. Der Grund, warum impliziert, ist, dass unter Komplement geschlossen ist. Wenn also , muss auch unter Komplement geschlossen werden.PNP=coNPP=NPNP=coNPPP=NPNP

Eine Klasse, die unter Komplement geschlossen wird, impliziert nicht notwendigerweise etwas über ihr deterministisches Gegenstück. Zum Beispiel wissen wir, dass unter Komplement geschlossen ist , wissen aber nicht, ob .NLL=NL

Mike B.
quelle