Kann genau eines von NP und Co-NP gleich p sein?

Question

Vielleicht fehlt mir etwas Offensichtliches, aber kann es sein, dass p = co-np $ subetneq $ np oder umgekehrt? Ich habe das Gefühl, dass es einen Satz geben muss, der diese Möglichkeit ausschließt.

Answer 1

Nein, weil $ mathsf {p} $ geschlossen ist, um dies zu ergänzen, und wir wissen sogar, dass $ mathsf {p} = mathsf {np} impliziert mathsf {np} = mathsf {co text { -} np} $.

Nehmen wir an, dass $ mathsf {p} = mathsf {np} $ und $ l in mathsf {co text {-} np} $, somit $ l^c in mathsf {np} $ gelassen wird . Wir haben $ mathsf {p} = mathsf {np} $ angenommen, und daher gibt es ein tm $ m $ st $ l (m) = l^c $. Wenn wir das "Ergänzung" von $ M $ einnehmen, ist das eine Maschine $ m '$, die identisch mit M $ ist, außer dass die Zustände von Akzeptieren und Ablehnungen umgekehrt sind, haben wir das $ l (m') = (l^c )^c = l $, und somit ist $ l $ in $ mathsf {np} $.

Dies zeigt, dass wir unter der Annahme $ mathsf {p} = mathsf {np} $ $ ( mathsf {p} =) mathsf {np} = mathsf {co text {-} np} erhalten $ und so $ mathsf {p} = mathsf {co text {-} np} $.

Answer 2

$ mathsf {p} $ ist unter complement geschlossen (dh $ mathsf {p} = mathsf {co text {-} p} $ ¹); Also, wenn $ mathsf {p} = mathsf {co text {-} np} $ (oder $ mathsf {p} = mathsf {np} $) dann $ mathsf {co text {-} np} = mathsf {np} $

---

1. Bei einer Sprache $ l in mathsf {p} $ können wir ein deterministisches TM erstellen, das $ overline l $ in Polynomzeit einfach durch die TM mit $ l $ und ...