Kann genau einer von NP und Co-NP gleich P sein?

8

Vielleicht fehlt mir etwas Offensichtliches, aber kann es sein, dass P = co-NP NP oder umgekehrt? Mein Gefühl ist, dass es einen Satz geben muss, der diese Möglichkeit ausschließt.

aelguindy
quelle

Antworten:

14

Nein, weil P geschlossen ist, um dies nicht zu ergänzen, und wir sogar wissen, dass P=NPNP=co-NP .

Nehmen wir an, dass P=NP und Lco-NP , also LcNP . Wir haben P=NP , und daher existiert ein TM M st L(M)=Lc . Wenn wir das "Komplement" von M , das heißt eine Maschine M die mit M identisch ist, Maußer dass ihre Annahme- und Ablehnungszustände umgekehrt sind, erhalten wir L(M)=(Lc)c=L und also ist L in NP .

Dies zeigt , dass, unter der Annahme , dass , erhalten wir und somit .P=NP(P=)NP=co-NPP=co-NP

Boris Trayvas
quelle
9

P wird unter Komplement geschlossen (dh ¹); Wenn also (oder ), dann istP=co-PP=co-NPP=NPco-NP=NP


  1. Wenn eine Sprache , können wir ein deterministisches TM 'konstruieren, das in Polynomzeit wir einfach das TM nehmen, das und ...LPL¯L
Vor
quelle