Warum werden nicht relativierende Beweise den relativierenden vorgezogen?

Ich entschuldige mich, aber auch nach diesen beiden anderen Beiträgen: Hier und hier habe ich immer noch Probleme, Orakel-TMs und Relativierung zu verstehen. Diese Frage kommt aus einem anderen Blickwinkel auf das Thema:

Warum werden nicht relativierende Beweise als valider angesehen als Argumente, die auf relativierten Ergebnissen beruhen?

Zum Beispiel haben wir einen nicht relativierenden Beweis für IP = PSPACE, aber können wir nicht genauso gut ein Argument für das Gegenteil sagen, indem es ein Orakel gibt, das sie trennt (ich erkenne aus einer Antwort auf eine Frage, die ich zuvor gestellt habe) fragte, dass dieses Orakel aufgrund eines strukturellen Unterschieds zwischen den beiden Komplexitätsklassen existiert, aber ich sehe dies als noch mehr Beweis dafür, dass die Klassen in wichtigen Punkten unterschiedlich sind und möglicherweise nicht gleich sind).

Auf der anderen Seite, warum schließen wir aus der Tatsache, dass es Orakel gibt $A$ und $B$ so dass $P^A = NP^A$ und $P^B \neq NP^B$ dass nicht-relativierende Techniken erforderlich sind, um P gegen NP aufzulösen und nicht nur, dass Orakel zu inhärenten Widersprüchen führen, da wir nicht sowohl P = NP als auch P haben können $\neq$NP? Wiederum stelle ich aus einem früheren Beitrag fest, dass wir Orakel-TMs als verschiedene Berechnungsmodelle betrachten können, die Probleme lösen können, die gewöhnliche TMs nicht lösen können, aber ich sehe dies ähnlich wie die in Principia Mathematica verwendete "Theorie der Typentaktik", die meiner Meinung nach Nach diesem Verständnis erwies sich Gödel (durch die Unvollständigkeitssätze) als unzureichend, um Probleme der Vollständigkeit und Konsistenz axiomatischer Systeme zu lösen.

Lassen Sie mich versuchen, Ihre facettenreiche Frage mit einer Analogie aus der Zahlentheorie (oder besser Peano-Arithmetik) zu beantworten. Aus platonistischer Sicht hat jede Frage nach natürlichen Zahlen eine JA / NEIN-Antwort. Dies ist als "wahre Arithmetik" bekannt. Wie Gödel jedoch gezeigt hat, können einige Aussagen über natürliche Zahlen weder bewiesen noch widerlegt werden. Der platonistische Standpunkt besagt immer noch, dass diese Sätze einen bestimmten Wahrheitswert in Bezug auf die "wahre" Menge natürlicher Zahlen haben; Gödel hat gerade gezeigt, dass die nicht endliche Liste der Axiome ¹ die wahre Menge natürlicher Zahlen spezifizieren kann.

Mal sehen, was dies in Bezug auf die P vs. NP-Frage bedeutet. Der platonistische Standpunkt besagt, dass entweder P = NP oder P.$\neq$NP. Es könnte sein, dass P vs. NP unabhängig von den Grundlagen der Mathematik ist (z. B. ZFC). In diesem Fall können wir weder P = NP noch P beweisen$\neq$NP. Nach Ansicht der meisten Forscher ist diese Möglichkeit jedoch unwahrscheinlich. Daher möchten wir wirklich wissen, ob P = NP in der realen Welt ist oder nicht , was dasselbe ist wie ^2, ob P = NP oder nicht, gemäß den Standardgrundlagen der Mathematik . Dies ist die Forschungsfrage.

Was ist mit relativierten Modellen? Lassen Sie mich eine andere Analogie aus der Zahlentheorie anbieten. Wenn eine Polynomidentität über die ganzen Zahlen wahr ist, dann ist es auch wahr modulo$p$ für jede Primzahl $p$. Um eine Identität zu widerlegen, reicht es also zu zeigen, dass sie für einige nicht gilt$p$. Wir können an die ganzen Zahlen modulo denken$p$als "relativiertes Modell". Betrachten wir ein Beispiel:$1 + 1 = 0$ Modulo $2$ aber nicht modulo $3$. Bedeutet das, dass wir uns nicht mehr sicher sind, ob$1 + 1 = 0$oder nicht? Ganz und gar nicht. Wir wissen das$1 + 1 = 2$, und besonders $1 + 1 \neq 0$. In einigen relativierten Modellen gilt diese Gleichung jedoch nicht.

Das (informelle) lokal-globale Prinzip besagt, dass es in einigen Situationen eine Reihe von "relativierten Modellen" gibt, die für einige zahlentheoretische Aussagen vollständig sind. Das klassische Beispiel sind quadratische Formen: eine quadratische Form gegeben$Q$ und eine Nummer $n$, dann $Q$ repräsentiert $n$ über die Rationalen (das heißt, $n$ ist im Bild von $Q$ wenn die Eingaben beliebige rationale Zahlen sind) iff es darstellt $n$ über die reellen Zahlen und die $p$-adics.

Leider haben wir keine ähnlichen Sätze für die Komplexitätstheorie. Insbesondere angesichts des Wahrheitswertes relativierter Aussagen können wir nichts über die ursprüngliche Aussage ableiten . Die Situation ist noch schlimmer: Es ist nicht länger so, dass ein in der "wahren" Welt wahres Ergebnis auch für jedes Orakel relativiert ist. Wir können also nicht einmal erwarten, dass Aussagen wie das lokal-globale Prinzip hier gelten.

So etwas wie "relativierte Techniken" kommt auch in der Peano-Arithmetik vor. Es gibt Aussagen zu den natürlichen Zahlen, die in ZFC, aber nicht in Peano-Arithmetik bewiesen werden können. Die klassischen Beispiele sind der Paris-Harrington-Satz und der Goodstein-Satz. Alle Beweise in der Peano-Arithmetik "relativieren" in dem Sinne, dass sie in allen Modellen der Peano-Arithmetik gelten. Die Sätze von Paris - Harrington und Goodstein scheitern in einigen nicht standardmäßigen Modellen der Peano-Arithmetik, aber diese stellen keine echte Arithmetik dar; in wahrer Arithmetik gelten die Sätze. Das Problem liegt eher in der Peano-Arithmetik als in den Aussagen selbst: Es gibt einige Eigenschaften der natürlichen Zahlen, die nicht beschrieben werden, sodass sich diese nicht standardmäßigen Modelle einschleichen können. Gödel hat gezeigt, dass dieses Problem bei allen Modellen erster Ordnung auftritt der Arithmetik.

Jetzt können wir Ihre Fragen beantworten:

1. Warum wird ein nicht relativierender Beweis von IP = PSPACE gegenüber Orakeltrennungen derselben zwei Klassen bevorzugt? Wir kümmern uns nur um die Frage IP = PSPACE? in der "wahren" Welt. Es spielt keine Rolle, was in relativierten Welten passiert. Da es Orakel gibt, die IP und PSPACE trennen, müssen Beweise für IP = PSPACE nicht relativierend sein. Die Situation ist analog zu der von Paris-Harrington und Goodstein.

   Ein anderes Problem ist, dass es möglicherweise nicht klar ist, wie die relativierten Versionen dieser Klassen definiert werden sollen. Dies schließt die Darstellung relativierter Ergebnisse auch als Beweis aus.

2. P = NP gilt in Bezug auf ein Orakel und nicht in Bezug auf ein anderes; Warum schließen wir, dass nicht relativierende Techniken erforderlich sind, anstatt dass Orakel zu inhärenten Widersprüchen führen? Dies ist die gleiche Situation wie$1+1 \neq 0$über. Dieser Satz ist wahr, hat aber unterschiedliche Wahrheitswerte in verschiedenen "relativierten Welten", die den ganzen Zahlen modulo entsprechen$p$ für verschiedene Werte von $p$. Dies bedeutet, dass ein Beweis von$1+1 \neq 0$ muss einen Schritt enthalten, der nicht alle Modulo enthält $p$. Es bedeutet nicht, dass Modulo funktioniert$p$ "führt zu inhärenten Widersprüchen".

3. Sehen wir nicht etwas Ähnliches in der in Principia Mathematica entwickelten "Typentheorie"? Die Typentheorie wurde als konsistente Grundlage für die Mathematik entwickelt, nachdem Russell herausgefunden hatte, dass die naive Mengenlehre inkonsistent ist (unter Verwendung seines Paradoxons). In der Komplexitätstheorie sind keine derartigen grundlegenden Schwierigkeiten aufgetreten.

4. Was bedeutet Gödels Unvollständigkeitssatz? Der Unvollständigkeitssatz eröffnet die Möglichkeit, dass P vs. NP unabhängig von den aktuellen Grundlagen der Mathematik ist. Dies wird jedoch von den meisten Forschern als unwahrscheinlich angesehen. Viele schwierige Sätze wurden in der Vergangenheit bewiesen; Einige von ihnen waren seit Jahrhunderten offen (zum Beispiel Fermats letzter Satz). Die Tatsache, dass ein Satz schwierig ist, ist kein Grund zu der Annahme, dass er nicht mehr zu lösen ist.

Dies lässt eine Frage, die Sie nicht gestellt haben: Warum interessieren uns relativierte Ergebnisse? Ich kenne den historischen Grund nicht. Es könnte sein, dass diese Techniken in verwandten Bereichen, die als Inspirationsquellen dienten, alltäglich sind. Gleich am Anfang, vielleicht haben die Menschen erwarten , dass relativierten Ergebnisse keine absolute Ergebnisse implizieren. Ein gutes Beispiel ist die zufällige Orakelhypothese, die besagt, dass eine Aussage zur Komplexitätstheorie in Bezug auf ein zufälliges Orakel absolut gilt. Zum Beispiel zeigten Baker, Gill und Solovay, obwohl P gegen NP in Bezug auf ein beliebiges Orakel "unentschlossen" ist, dass P.$\neq$NP in Bezug auf ein zufälliges Orakel. Bedeutet das, dass P.$\neq$NP? Die Tatsache, dass IP = PSPACE widerlegte diese Hypothese. Seitdem wurde den Orakelergebnissen viel weniger Aufmerksamkeit geschenkt, und sie sind jetzt ziemlich unmodern. Sie sind zu einem eigenständigen Untersuchungsobjekt geworden, haben jedoch keinen Anspruch darauf, für die Trennung von P und NP relevant zu sein.

Endnoten:

1. Die übliche Axiomatisierung der Peano Arithmetik verwendet tatsächlich eine endliche Anzahl von Axiom Systeme . Gödels Ergebnis ist noch allgemeiner, wie Andrej Bauer in seinen nachdenklichen Kommentaren ausführt.

2. In den Kommentaren von Andrej Bauer finden Sie eine abweichende Meinung.