Was ist der "wahre" Grund, warum IP = PSPACE nicht relativiert?

IP = PSPACE wird als kanonisches Beispiel für ein nicht relativierendes Ergebnis aufgeführt, und der Beweis dafür ist, dass es ein Orakel , das während für alle Orakeln . $O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Ich habe jedoch nur wenige Leute gesehen, die eine "direkte" Erklärung dafür gaben, warum das Ergebnis ${\sf IP} = {\sf PSPACE}$ nicht relativiert wird, und die übliche Antwort lautet "Arithmetisierung". Nach Prüfung des Beweises von IP = PSPACE ist diese Antwort nicht falsch , aber für mich nicht zufriedenstellend. Es scheint, dass der "wahre" Grund auf den Beweis zurückzuführen ist, dass das Problem TQBF - wahre quantifizierte Boolesche Formel - für PSPACE vollständig ist; Um dies zu beweisen, müssen Sie nachweisen, dass Sie Konfigurationen eines PSPACE-Computers in einem polynomgroßen Format codieren können, und (dies scheint der nicht relativierende Teil zu sein) Sie können "korrekte" Übergänge zwischen Konfigurationen in einem polynomgroßen Format codieren Boolesche Formel - Hier wird ein Schritt nach Cook-Levin-Art verwendet.

Die Intuition, die ich entwickelt habe, ist, dass nicht-relativierende Ergebnisse diejenigen sind, die mit dem Kern von Turing Machines herumspielen, und in dem Schritt, in dem gezeigt wird, dass TQBF für PSPACE vollständig ist, geschieht dieses Herumstöbern - und der Arithmetisierungsschritt könnte es Das ist nur passiert, weil Sie eine explizite Boolesche Formel zum Arithmetisieren hatten.

Dies scheint mir der fundamentale Grund zu sein, warum IP = PSPACE nicht relativierend ist; und das folkloristische Mantra, das Arithmetisierungstechniken nicht relativieren, scheint ein Nebenprodukt davon zu sein: Der einzige Weg, etwas zu arithmetisieren, ist, wenn Sie eine Boolesche Formel haben, die etwas über TMs codiert!

Fehlt mir etwas? Als Teilfrage - bedeutet dies, dass alle Ergebnisse, die TQBF auf irgendeine Weise verwenden, auch nicht relativiert werden?

cc.complexity-theory interactive-proofs relativization Henry Yuen
quelle

Sie können Orakelgatter in eine quantifizierte Boolesche Formel einbeziehen, und dann ist ein solches relativiertes TQBF ^ O für PSPACE ^ O vollständig, sodass dies nicht der nicht relativierende Schritt ist.

Emil Jeřábek unterstützt Monica am

Hallo Emil - könntest du noch etwas näher darauf eingehen? Nehmen wir an, ich habe eine Maschine M, und ich versuche, den gleichen Beweis zu führen, dass L (M) (die von M akzeptierte Sprache) auf (was auch immer bedeutet) reduzierbar ist . Irgendwann muss ich mir eine Boolesche Formel ausdenken, die ausdrückt, ob zwei Konfigurationen C, C 'der Orakelmaschine M Nachbarn sind (für zwei beliebige Konfigurationen C, C'). Wie kann ich sicherstellen, dass diese boolesche Formel unabhängig vom Orakel eine endliche Größe hat, geschweige denn eine polynomielle Größe? Beispielsweise könnte O das Problem des Anhaltens codieren.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Henry Yuen

Ich schätze, ich könnte das noch weiter zurückschieben - relativiert sich das Cook-Levin-Theorem selbst ? Aus den oben genannten Gründen glaube ich nicht, dass dies der Fall ist. Ob das Cook-Levin-Theorem relativiert, bestimmt, ob der PSPACE-Vollständigkeitsnachweis von TQBF auch relativiert.

Henry Yuen

Eine QBF ^ O-Formel kann, abgesehen von den üblichen Quantifizierern und Booleschen Konnektiven, auch ein neues unbegrenztes Fan-In-Gatter verwenden. Nennen wir es , dessen Semantik die folgende ist: wenn der String zum Orakel . In dieser Sprache auszudrücken, dass eine Konfiguration ein Nachfolger einer anderen ist, ist eine einfache Übung, da Sie den Inhalt des Oracle-Abfragebands einfach in einstecken können . (Ich gehe hier davon aus, dass eine PSPACE-Maschine nur polynomiell lange Abfragen durchführen kann.)

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$

Emil Jeřábek unterstützt Monica am

Ich verstehe - Sie sagen, wenn Sie den Beweis der PSPACE-Vollständigkeit von TQBF relativieren, relativieren Sie nicht nur die Maschinen im Spiel, sondern Sie relativieren auch die Booleschen Formeln selbst (sie sind also keine Booleschen Formeln mehr im engeren Sinne) ). In diesem Fall kann ich sehen, warum der Arithmetisierungsschritt zusammenbrechen würde. Vielen Dank! Vielleicht kannst du es als Antwort schreiben.

Henry Yuen

Jede Antwort auf eine Frage des Formulars "Was ist der wahre Grund, dass ..." wird notwendigerweise etwas subjektiv sein. Für den speziellen Fall von IP = PSPACE denke ich jedoch, dass man ziemlich gut sagen kann, dass Arithmetisierung tatsächlich der Schlüssel ist, wenn man beobachtet, dass IP = PSPACE zwar nicht relativiert , aber im Sinne von Aaronson und Wigderson algebriert . Wie sie in ihrem Papier erklären, grob gesagt, eine Einbeziehung Komplexitätsklasse algebrizes wenn für alle Orakel und alle niedriggradigen Erweiterungen von ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ $A$ . Insbesondere zeigen sie, dass der Einschluss PSPACE IP algebriert, obwohl er nicht relativiert. $\subseteq$

Die Intuition, die ich entwickelt habe, ist, dass nicht-relativierende Ergebnisse diejenigen sind, die mit dem Kern von Turing Machines herumspielen

Dies ist keine schlechte Intuition, aber ich denke, dass das Aaronson-Wigderson-Ergebnis zeigt, dass der IP = PSPACE-Beweis auf eine ziemlich eingeschränkte Art und Weise und mit Sicherheit nicht auf eine ausreichend ausgefeilte Art und Weise funktioniert, um P NP zu beweisen , seit Aaronson und Wigderson zeigen auch, dass nicht-algebrisierende Techniken erforderlich sind, um P von NP zu trennen. $\ne$

Timothy Chow
quelle

Danke für den Hinweis. Lassen Sie mich sehen, ob ich das verstehe: Was Sie - und das Aaronson / Wigderson-Papier - zu argumentieren scheinen, ist, dass "Arithmetisierung" ein schwach nicht-relativierender Schritt ist und dass eine winzige, natürliche Änderung des Begriffs der Relativierung (nämlich algebraische Relativierung) wird diese Eigenschaft brechen. Da der Rest des IP = PSPACE-Beweises relativiert (und ich bin von dem, was Emil oben gesagt hat, überzeugt), bedeutet dies, dass das IP = PSPACE-Ergebnis selbst sehr schwach nicht relativiert ist, was Sie gesagt haben. Sehr interessant! Vielen Dank. Ich brauche eine Möglichkeit, beide Antworten zu akzeptieren :)

Henry Yuen

Ja, das stimmt im Grunde.

Timothy Chow

Was ist der "wahre" Grund, warum IP = PSPACE nicht relativiert?

Antworten: