Fehler in meinem NP = CoNP Proof?

Ich habe diesen sehr einfachen "Beweis" für NP = CoNP und ich glaube, ich habe irgendwo etwas falsch gemacht, aber ich kann nicht finden, was falsch ist. Kann mir jemand weiterhelfen?

Sei A ein Problem in NP und sei M der Entscheider für A. Sei B das Komplement, dh B ist in CoNP. Da M ein Entscheider ist, können Sie damit auch B entscheiden (nur die Antwort umdrehen). Bedeutet das nicht, dass wir sowohl NP- als auch CoNP-Probleme mit demselben M lösen?

Genauer gesagt.

Sei A ein NP-vollständiges Problem, und sei M der Entscheider für A. Betrachte jedes Problem B in CoNP. Wir betrachten sein Komplement nicht-B, das in NP ist, und erhalten dann eine Polynomreduktion auf A. Dann führen wir unseren Entscheider M aus und drehen unsere Antwort um. Wir erhalten also einen Entscheider für B. Dies impliziert, dass B auch in NP ist.

Darf ich wissen, was an meiner Argumentation falsch ist?

Es gibt zwei mögliche Fehler in diesem Beweis:

1. Wenn Sie "Entscheider" sagen, meinen Sie ein deterministisches TM. In diesem Fall kann die beste Übersetzung (nach unserem Wissen) von einer NP-Maschine zu einer deterministischen Maschine eine Maschine ergeben, die in exponentieller Zeit läuft. Nach der Ergänzung haben Sie also einen Entscheider für die Ergänzung in exponentieller Zeit, der beweist, dass $co-NP\subseteq EXP$ (oder nach einer gewissen Optimierung ).$co-NP\subseteq PSPACE$

2. Wenn Sie "Entscheider" sagen, meinen Sie ein nicht deterministisches TM. In diesem Fall wird das Umdrehen der Antwort die Sprache nicht unbedingt ergänzen. In der Tat ist die Sprache der umgedrehten Maschine alle Wörter, für die es einen Ablehnungslauf von auf $M$$w$

Hier ist eine andere Sichtweise auf den Punkt, den Shaull in Bezug auf "Entscheider" macht.

Ein Problem ist in NP , wenn und nur wenn es einen Algorithmus , so dass$V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$

• für jede Instanz YES , gibt es ein Zertifikat , p ∈ { 0 , 1 } p o l y ( n ) , so daß V ( $x \in \{0,1\}^n$$p \in \{0,1\}^{\mathrm{poly}(n)}$ ; und$V(x,p) = 1$

• für jede NO-Instanz gilt V ( x , p ) = 0 für alle p ∈ { 0 , 1 } p o l $x \in \{0,1\}^n$$V(x,p) = 0$ .$p \in \{0,1\}^{\mathrm{poly}(n)}$

Diese werden üblicherweise als die bezeichnet Vollständigkeits- und Zuverlässigkeitsbedingungen für den NP- Überprüfungsalgorithmus beschrieben: Die Bedingung "Vollständigkeit" besagt, dass jede JA-Instanz ein Zertifikat besitzt, und die Bedingung "Zuverlässigkeit" besagt, dass der Algorithmus niemals von einer NEIN-Instanz getäuscht wird. Bei coNP ist es umgekehrt: Es gibt einen Überprüfungsalgorithmus , der mindestens ein Zertifikat für jede NO-Instanz akzeptiert, aber niemals von einer YES-Instanz getäuscht werden kann.

Wenn Sie diesen NP zeigen wollen ⊆ coNP ist , müssen Sie zeigen, dass jedes NP- Problem einen CoNP- Verifizierer hat, der NO-Instanzen anstelle von YES-Instanzen zertifizieren kann. Mit einer nicht deterministischen Turing-Maschine ist dies nicht möglich: Es gibt keine Möglichkeit, beispielsweise SAT-Instanzen so effizient aufeinander abzubilden, dass alle nicht erfüllbaren Formeln auf erfüllbare Formeln abgebildet werden, und umgekehrt. (Das Negieren der Ausgabe der Formel reicht beispielsweise nicht aus: Eine Formel, die befriedigend ist, aber keine Tautologie, würde nur einer anderen Formel zugeordnet, die befriedigend ist, aber keine Tautologie, wenn wir stattdessen eine unbefriedigende Formel benötigen würden.) Wir wissen einfach nicht, wie wir eine nicht deterministische Maschine zum Narren halten können, wenn sie erkennt, dass alle ihre Pfade Pfade ablehnen.

Sie könnten fragen: "Weiß die nichtdeterministische Turing-Maschine nicht , welches Ergebnis sie erzielt?" Die Antwort wäre nein , tut es nicht. Die Arbeitsweise der nicht deterministischen Maschine gibt ihr keinen Zugriff auf Informationen zu mehr als einem Computerpfad gleichzeitig: Sie können sich vorstellen, dass sie auf vielen Pfaden gleichzeitig funktioniert, aber innerhalb jedes Pfades kennt sie nur diesen einen Pfad. Wenn Sie versuchen, es mit der Fähigkeit auszustatten, zu "erkennen", ob es irgendwann Lösungen gibt oder nicht, beschreiben Sie stattdessen eine Maschine mit einem NP- Orakel , das (potenziell!) Leistungsfähiger ist als eine einfache nicht deterministische Turing-Maschine.

• Wenn Sie beispielsweise eine (deterministische) Turing-Maschine mit einem NP- Orakel ausstatten , werden die Probleme, die in Polynomzeit auf dieser Maschine gelöst werden können, als , was häufig als P N P bezeichnet wird . Das "Orakel" ermöglicht es der Maschine, einfach in einem Schritt Antworten auf NP- vollständige Probleme zu erhalten, und so enthält P N P offensichtlich P ; und weil man antworten negieren kann, enthält es natürlich auch coNP . Wir wissen jedoch nicht, ob die umgekehrten Einschlüsse zutreffen, gerade weil wir nicht wissen, wie wir nicht deterministische Turing-Maschinen dazu bringen sollen, NEIN-Antworten zu erkennen.$\Delta_2^{\mathrm P}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$

• Was mehr ist , wenn Sie geben einen nichtdeterministischen Turing - Maschine die Fähigkeit zur Erkenntnis über das Ergebnis eines Problems zu kommen NP , die Probleme , die die Maschine in Polynomzeit heißt lösen kann oder N P N P , und diese wird allgemein angenommen, dass sie streng größer als die Klasse P N P ist . Dies enthält auch NP und coNP - aber wie NP ist es nicht bekannt, dass es unter Komplementen geschlossen ist: Die nicht deterministische Orakelmaschine kann möglicherweise wissen, wann ein Problem in NP vorliegt$\Sigma_2^{\mathrm P}$$\mathsf{NP}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$hat eine NEIN-Antwort wegen des Orakels, aber es würde immer noch in einem seiner eigenen (ziemlich mächtigen) Rechenzweige arbeiten, so dass es nicht in der Lage wäre zu sagen, ob alle seine eigenen Rechenzweige ablehnen.

Wenn Sie die Maschine weiterhin mit leistungsstärkeren Orakeln zur Lösung von Problemen in , N P, N P usw. versorgen , definieren Sie schließlich die Klassen der Polynomhierarchie , von denen angenommen wird, dass sie sich alle von der unterscheiden erste Stufe ab.$\mathsf{NP}$$\mathsf{NP}^{\mathsf{NP}}$

Also, nein, es gibt keine Maschine (deterministisch oder anderweitig), die einfach "entscheiden" kann, dass ein Problem eine JA- oder NEIN-Instanz ist, es sei denn, wir verwenden Orakel; aber selbst mit einer solchen Orakel, beenden wir mit einer Maschine , die (wahrscheinlich) ist mehr mächtiger als entweder NP oder coNP , nicht eine , die zeigt , dass sie gleich sind .

Ihre Argumentation impliziert, dass RE = coRE, aber dies ist nachweislich falsch. Sie könnten versuchen, einen Beweis dafür zu finden und dann herauszufinden, wo Ihre Reduktion fehlschlägt.

Erinnern Sie sich, dass RE die Komplexitätsklasse von rekursiv aufzählbaren Sprachen ist, die Sprachen der Form . Man kann sich das auch nicht deterministisch vorstellen: RE ist die Klasse der Sprachen der Form { x : ( x , w ) ∈ L ′  für einige  w } , wobei L $\{ x : P \text{ halts on input } x \}$$\{ x : (x,w) \in L' \text{ for some } w \}$$L'$ rekursiv (berechenbar) ist.

Hier ist ein Beweis, dass beide Definitionen übereinstimmen. Nehmen wir an, dass zuerst anhält  . Sei L ' = { ( x , w $L = \{ x : p \text{ halts on input } x \}$ . Die Sprache L ' ist rekursiv und L = { x : ( x , w ) ∈ L '  für einige  w } .$L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$$L'$$L = \{ x : (x,w) \in L' \text{ for some } w \}$

Für die andere Richtung sei , wobei L ' rekursiv ist, beispielsweise berechnet durch das Programm $L = \{ x : (x,w) \in L' \text{ for some } w \}$$L'$ . Wir konstruieren ein neues Programm Q ( x ), das alle möglichen w auflistet und P ( x , w ) nacheinander auf allen w ausführt. Wenn P ( x , $P(x,w)$$Q(x)$$w$$P(x,w)$$w$ akzeptiert jemals für einige w , dannhält Q an. Es ist nicht schwer zu überprüfen, ob L = { x : Q  bei Eingabe x } anhält  .$P(x,w)$$w$$Q$$L = \{ x : Q \text{ halts on input } x \}$

Der Einfachheit halber finden Sie hier die Umrisse für den Beweis, dass sich RE von coRE unterscheidet. Die Sprache ist eindeutig rekursiv aufzählbar: Ein Programm dafür führt einfach P auf x aus . Angenommen, es gibt ein Programm H , bei dem H ( P , x ) genau dann anhält, wenn ( P , x ) x L ist . Wir definieren ein neues Programm G durch G ( x ) $L = \{(P,x) : P \text{ halts on input x}\}$$P$$x$$H$$H(P,x)$$(P,x) \notin L$$G$ . Ist ( G , G ) ∈ L ? Wenn ja, dann G stoppt auf G , so H stoppt auf ( G , G ) , so ( G , G ) ∉ L . Wenn ( G , G ) ∉ L , dannhört G nicht bei G auf , alsohört H nicht bei ( G , G $G(x)=H(x,x)$$(G,G) \in L$$G$$G$$H$$(G,G)$$(G,G) \notin L$$(G,G) \notin L$$G$$G$$H$$(G,G)$, So . Dieser Widerspruch zeigt, dass H nicht existieren kann.$(G,G) \in L$$H$

Versuchen Sie nun, Ihren Beweis in diesem Fall zu führen und festzustellen, was schief geht. Versuchen Sie genauer, das Programm anhand Ihres Rezepts zu konstruieren und befolgen Sie den Beweis - irgendwann stimmt etwas nicht mehr.$H$

Hier ist eine TL; DR-Version; Ich habe auch eine längere Antwort auf eine ähnliche Frage gepostet .

Angenommen, wir haben eine Sprache , die in der Polynomzeit von der nichtdeterministischen Turing-Maschine  M bestimmt wird . Der Punkt ist , dass x ∈ A iff dort M  hat eine Annahme Pfad auf Eingang  x . Da M  jedoch nicht deterministisch ist, können auch Pfade zurückgewiesen werden, wenn es auf  $A$$M$$x\in A$$M$$x$$M$$x$. Wenn Sie nur den Akzeptanz- und den Ablehnungsstatus umkehren, wechseln Sie von einem Computer mit einigen Akzeptanzpfaden und einigen Ablehnungspfaden zu einem Computer mit einigen Ablehnungspfaden und einigen Akzeptanzpfaden. Mit anderen Worten, es hat immer noch akzeptierende Pfade, also akzeptiert es immer noch. Das Umkehren der Zustände "Annehmen" und "Ablehnen" einer nicht deterministischen Maschine bewirkt im Allgemeinen nicht, dass Sie die Komplementsprache akzeptieren.

Es ist diese Asymmetrie der Definition (Akzeptieren, wenn ein Pfad akzeptiert wird; Zurückweisen, wenn alle Pfade zurückgewiesen werden), die das NP- gegen- Co-NP- Problem schwierig macht.

Tatsächlich stimme ich zu, dass Ihre nicht deterministische Maschine M entscheiden kann, ob eine bestimmte Eingabezeichenfolge in B enthalten ist. Sie "entscheidet" jedoch geringfügig anders als die Art und Weise, wie sie entscheidet, ob eine bestimmte Eingabe in A enthalten ist. Im letzteren Fall erfolgt dies durch ( nicht deterministisch) einen akzeptierenden Zustand finden. Im ersteren Fall werden keine akzeptierenden Zustände gefunden. Warum ist dieser Unterschied wichtig? Mal sehen:

Bei der Frage M "Ist die Zeichenfolge in der Sprache A?"

M erreicht einen Akzeptanzzustand. Dies können Sie beweisen (siehe zum Beispiel das Sipser-Buch Theorem 7.20), dass es eine deterministische Maschine gibt, die sicherstellt, dass die Zeichenfolge in der Polynomzeit in A ist

Bei der Frage M "Ist die Zeichenfolge in der Sprache B?"

M erreicht Rückweisungszustände in allen Zweigen seiner nichtdeterministischen Berechnung. Wenn Sie sich überlegen, wie der obige Überprüfungsnachweis funktioniert, werden Sie feststellen, dass dies in dieser Situation nicht möglich ist. Dies liegt grob daran, dass der Prüfer den Pfad, den M durch seinen Zustandsraum nimmt, als "Beweis" verwendet. In diesem Fall gibt es keinen solchen Pfad.

Fazit:

Wenn Sie die Existenz eines polynomiellen zeitdeterministischen Verifikators für eine Sprache als Definition einer NP-Sprache betrachten (was Sie sollten), beweist die Existenz von M nicht, dass B in NP ist.