Warum schließt Gödels zweiter Unvollständigkeitssatz einen formalisierbaren Beweis von P! = NP nicht aus?

Ich bin mir sicher, dass mit den folgenden Überlegungen etwas nicht stimmt, da sonst viele P- gegen NP-Untersuchungen eingeschränkt würden, aber ich kann meinen Fehler nicht feststellen:

Für jede feste ganze Zahl definieren Sie $k>0$

B_{k} := {⟨ φ ⟩ | φ is a wff of ZF and has a proof of length \leq k {| φ |}^{k}}

$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$

Nun ist für alle die Sprache in NP, da ein gültiger Beweis für der Länge ein NP-Zeuge sein kann, der von einem automatisierten Beweisprüfer in Polynomzeit verifiziert wurde. Ferner ist für ausreichend groß genug , NP-vollständig ist, da SAT reduziert: das heißt, für eine Instanz von SAT einen entsprechenden wfA von ZF machen Verwendung Existenzquantoren. Dann kann eine zufriedenstellende Wahrheitszuweisung von zu einem formalen Beweis von des Längenpolynoms inda eine Wahrheitszuweisung von $k$ $B_k$ $\varphi$ $\leq k{|\varphi|}^k$ $k$ $B_k$ $\phi$ $\varphi$ $\phi$ $\varphi$ $|\varphi|$ $\phi$ ist linear in. $|\phi|$

Wenn ZF inkonsistent ist, bedeutet dies, dass es eine formale Aussage so dass sowohl als auch Beweise in ZF haben. Bekanntlich kann jede andere Aussage dann aus der widersprüchlichen Konjunktion ( indem man dem Pfad folgt: $\sigma$ $\sigma$ $\neg \sigma$ $\tau$ $\langle \sigma \wedge \neg \sigma \rangle$

⟨ σ \land \neg σ ⟩ ⟹ both σ and \neg σ are true ⟹ ⟨ \neg τ \to σ ⟩ is true (since regardless of τ the implication is valid since σ is true) ⟹ ⟨ \neg σ \to τ ⟩ (by contraposition and double negation) ⟹ τ is true (by modus ponens with \neg σ)

$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau \; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$

). Wenn also ZF inkonsistent ist, hat jede Aussage in ein Beweispolynom (es scheint mir sogar nur linear) . $\varphi$ $|\varphi|$

Sei für ein ausreichend großes a, auf das oben Bezug genommen wurde, um zu ermöglichen, dass NP-vollständig ist. Wenn dann ZF inkonsistent ist, gibt es nur endlich viele so dass weil die hochgradige polynomielle Beweislängenzugabe von ausreicht, um die garantierten kurzen Beweise von wffs mit ausreichender Länge abzudecken. Dies impliziert, dass in der Polynomzeit entscheidbar ist, was aufgrund seiner NP-Vollständigkeit impliziert, dass P = NP ist. Wenn wir diese Argumentationskette in Bezug auf Kontrapositive umformulieren, wenn P! = NP, dann ist ZF nicht inkonsistent (das heißt, es ist konsistent). $B:=B_k$ $k$ $B$ $\varphi$ $\langle \varphi \rangle \notin B$ $B$ $B$

Wenn wir also einen formalen Beweis für P! = NP haben, dann haben wir einen formalen Beweis für die Konsistenz von ZF. Nach dem zweiten Unvollständigkeitssatz von Godel impliziert dies jedoch, dass ZF inkonsistent ist, was wiederum P = NP ergibt, wie oben beschrieben (sowie den Satz eines negierten Satzes).

Dies ist nicht gerade ein Beweis dafür, dass P vs. NP unabhängig von ZF ist. Es könnte sein, dass ZF konsistent ist und dass P = NP oder P! = NP durch Techniken nachgewiesen werden kann, die innerhalb von ZF nicht formalisierbar sind. Es stellt jedoch eine weitere gewaltige Barriere für die Auflösung von P gegen NP dar.

complexity-theory np-complete logic p-vs-np Ari
quelle

Antworten:

Es scheint einen Fehler zu geben, auf den Arno in seiner Antwort anspielt. Während die Reduktion harmlos genug erscheint (und in der Tat eine Lehrbuchübung ist, wie Ariel in seinem Kommentar ausgeführt hat), geht sie implizit von der Konsistenz von ZF aus. Andernfalls, wenn ZF inkonsistent ist, da nicht jede Aussage von ZF dann einen Beweis hätte, würden unbefriedigende SAT-Instanzen nicht notwendigerweise wffs die keinen relativ kurzen Beweis haben. $SAT \leq B$ $\varphi$

Wenn wir also annehmen, dass ZF konsistent ist und dann können wir, obwohl wir metamathematisch schließen können, dass (weil NP-vollständig ist, nicht in da wir annehmen ) Wir hätten keinen formalen Abzug von (da dies davon abhängt, dass eine etablierte NP-vollständige Menge ist. Wenn wir also die obige Reduktion verwenden möchten, müssen wir davon ausgehen, dass ZF konsistent ist, was nicht möglich ist formell durch Godels zweiten Unvollständigkeitssatz behauptet). Daher kann dieses Argument keine notwendigen Implikationen von vorschlagen . $ZF \vdash P \neq NP$ $B \notin P$ $B$ $P$ $P \neq NP$ $ZF \vdash B \notin P$ $B$ $ZF \vdash P \neq NP$

Ari
quelle

Gut gemacht! Dies scheint das Problem zu sein.

Ariel

Das Problem liegt in Ihrer Behauptung, dass für ausreichend großes die Sprache NP-vollständig ist. In Ihrer vorgeschlagenen Reduktion argumentieren Sie nur, dass jede zufriedenstellende SAT-Instanz eine ZF-Formel mit "kurzem" Beweis ist. Sie müssen jedoch auch argumentieren, dass die ursprüngliche SAT-Instanz immer dann zufriedenstellend ist, wenn die resultierende ZF-Formel einen kurzen Beweis enthält. Dies läuft natürlich nur darauf hinaus zu sagen, dass wenn ZF beweist, dass die SAT-Instanz zufriedenstellend ist, dies wirklich der Fall ist - aber hier verwenden wir die Solidität von ZF. $k$ $B_k$

Arno
quelle

Sie haben insofern Recht, als ich implizit die Solidität von ZF und die Richtigkeit eines Proof-Checkers annehme, aber wie wirkt sich dies auf den Beweis aus, dass NP-vollständig ist? Dies sind nur notwendige Annahmen, damit die Sprache von Interesse ist. Nach meiner Reduktion wird nur eine zufriedenstellende SAT-Instanz einen Beweis von beliebiger Länge haben, da eine nicht erfüllbare einer falschen ZF-Aussage entspricht.

B_{k}

$B_k$

B_{k}

$B_k$

Ari

@Ari Unbefriedigende SAT-Instanzen entsprechen ZF-Aussagen, die in Ihrer Meta-Theorie falsch sind. Damit die Reduzierung funktioniert, müssen falsche ZF-Anweisungen keinen ZF-Beweis haben.

Arno

Die Äquivalenz ist klar, wenn die Formel einen Beweis hat, ist die SAT-Instanz zufriedenstellend (ZF ist solide, ich verstehe nicht, warum dies hier ein Hindernis sein sollte). In dieser Frage finden Sie einen Beweis für die Vollständigkeit des NP.

Ariel

@Ariel Die Antwort in dieser Frage ist ungenau, was die Annahmen sind. Es muss unbedingt davon ausgegangen werden, dass ZF einwandfrei ist. Nur die Erinnerung: "Ton" bedeutet, dass eine Aussage, wenn sie einen Beweis hat, tatsächlich wahr ist. Wenn ZF inkonsistent ist, beweist es alles und kann daher nicht gesund sein. Insbesondere sehen wir, dass "ZF ist Klang" kein Satz von ZF ist. Wenn unsere Meta-Theorie beweist, dass "ZF gesund ist", dann beweist sie auch, dass "ZF konsistent ist", und es gibt kein Problem. Wenn es dies nicht beweist, haben wir keinen NP-Vollständigkeitsnachweis, und es gibt auch kein Problem.

Arno

Die Richtigkeit der Reduktion hängt zwar von der Konsistenz von ZF ab, hat jedoch nichts mit der Solidität zu tun. Denken Sie daran, dass die Solidität in Bezug auf eine bestimmte Semantik definiert ist und ZF in dem Sinne solide ist, dass nachweisbare Aussagen in allen Modellen zutreffen, wenn ZF inkonsistent ist, dass es leer klingt, da es keine Modelle hat.

Ariel