Ist die offene Frage NP = co-NP dieselbe wie P = NP?

11

Ich frage mich , ob dies auf mehreren Online-Stellen basiert, die co- ein großes offenes Problem bezeichnen ... aber ich kann keinen Hinweis darauf finden, ob dies dasselbe ist wie Problem ...N P P = N P.NP=NPP=NP

Mirrana
quelle

Antworten:

19

Nein, es ist ein weiteres offenes Problem und sicherlich verwandt, aber anders. Die Komplexitätsklasse co-NP N P. ist die Menge der Sprachen, deren Ergänzungen in . das heißt, die Menge von Entscheidungsproblemen, für die eine "Nein" -Antwort einen deterministischen Polynomzeitverifizierer hat. So zum Beispiel die Frage "Ist diese SAT-Formel unbefriedigend?" Wenn die Antwort "Nein" lautet, gibt es eine zufriedenstellende Zuordnung der Variablen, die dies beweist. Das ist das Zertifikat für den Prüfer.NP

Es ist möglich, dass , aber co- .N P = N P.PNPNP=NP

Wenn andererseits , dann ist co- sicher. Dies liegt daran, dass wenn sich eine Sprache in , ihre Ergänzung auch in ist. Wenn also , gilt dies für jede Sprache in auch.N P = N P P P P = N P N P.P=NPNP=NPPPP=NPNP

usul
quelle
4
auch wenn NP coNP dann P NP, weil P unter Komplement geschlossen ist. Die Frage NP coNP kann also genauso schwierig sein wie das berüchtigte P NP-Problem. ? = ? ==?=?
VZN
2
Ja, guter Punkt!
Usul
1
Als Ergänzung dazu habe ich gerade in einem Artikel die Behauptung gesehen, dass NP = coNP weithin angenommen wird.
vzn
4

Eine gute Möglichkeit, diese Frage zu beantworten, ist die Verwendung der Polynomhierarchie (PH) (siehe auch hier ). Die Polynomhierarchie ist eine Hierarchie von Komplexitätsklassen, die die Klassen , und auf Orakelmaschinen verallgemeinert und als Skala zur Messung der Komplexität von Problemen verwendet.N P c o - N P.PNPcoNP

Es ist bekannt, dass wenn oder die Polynomhierarchie auf ihre erste Ebene zusammenbricht.P = N P.NP=coNPP=NP

Reza
quelle