Ist die Klasse NP unter Ergänzung geschlossen?

Antworten:

6

Die Antwort lautet "der Wissenschaft nicht bekannt". Es ist bekannt, dass P unter Komplement geschlossen ist. Wenn also P = NP ist, wird NP auch unter Komplement geschlossen. Auch wenn NP nicht unter Komplement geschlossen ist, dann ist P! = NP.

Otto Normalverbraucher
quelle
3
Die Umkehrung von "Wenn P = NP, dann ist NP unter Komplement geschlossen" wäre "Wenn NP unter Komplement geschlossen ist, dann ist P = NP". Dies ist jedoch nicht als wahr bekannt: Es ist möglich, dass NP unter Komplement geschlossen wird, sich aber immer noch von P. unterscheidet
David Richerby
Danke für die Korrektur @DavidRicherby. "Umgekehrt" durch "Auch" ersetzt.
Joebloggs
15

Zunächst ist die Frage, die Sie stellen, offen, da eine positive Antwort zeigt, dass . Tatsächlich ist es eines der bekanntesten offenen Probleme in der Informatik.N.P.=cÖN.P.

Wenn , wird die Klasse unter Komplement geschlossen, da ist. Wenn andererseits ist, können wir nicht sagen, ob oder nicht. Beachten Sie, dass impliziert , dass die Polynom - Hierarchie auf der ersten Ebene zusammenbricht. Dies würde jedoch nicht bedeuten, dass .P.=N.P.N.P.P.P.≠N.P.N.P.=cÖN.P.N.P.=cÖN.P.P.=N.P.

A.Schulz
quelle
-2

"Jede deterministische Komplexitätsklasse (DSPACE (f (n)), DTIME (f (n)) für alle f (n)) wird unter Komplement geschlossen, weil man dem Algorithmus einfach einen letzten Schritt hinzufügen kann, der die Antwort umkehrt. Dies funktioniert nicht für nicht deterministische Komplexitätsklassen, denn wenn es sowohl Berechnungspfade gibt, die akzeptieren, als auch Pfade, die ablehnen, und alle Pfade ihre Antwort umkehren, gibt es immer noch Pfade, die akzeptieren und Pfade, die ablehnen - folglich akzeptiert die Maschine in beiden Fälle". Quelle

Nilabja Bhattacharya
quelle
2
Dies zeigt nur, dass eine Möglichkeit, den Abschluss unter Ergänzung zu beweisen, nicht funktioniert. Andere Möglichkeiten könnten möglich sein - zum Beispiel wird NL unter Komplementation geschlossen, und das Gleiche gilt für viele andere nichtdeterministische Raumkomplexitätsklassen .
Yuval Filmus
1
Außerdem suchen wir nach Antworten, nicht nach Kopierpasten aus Wikipedia. (Aber danke für die Bestätigung Ihrer Quelle.)
David Richerby
-3

Es ist unbekannt. Ein Beweis für das P vs. NP-Problem würde Ihnen eine Antwort geben.

user119264
quelle
4
Nein, würde es nicht. Wenn P≠NP (was die meisten Komplexitätstheoretiker glauben), dann ist es möglich, dass entweder NP = coNP oder NP≠coNP.
David Richerby