Was ist das Orakel mit der minimalen Komplexität, das PSPACE von der Polynom-Hierarchie trennt?

17

Hintergrund

Es ist bekannt, dass es ein Orakel A , das .PSPACEAPHA

Es ist sogar bekannt, dass die Trennung relativ zu einem zufälligen Orakel gilt. Informell kann man dies so interpretieren, dass es viele Orakel gibt, für die und getrennt sind.P HPSPACEPH

Frage

Wie kompliziert sind diese Orakel, die von trennen . Gibt es insbesondere ein Orakel so dass ?P H A D T I M E ( 2 2 n ) P S P A C E AP H APSPACEPHADTIME(22n)PSPACEAPHA

Haben wir ein Orakel , bei dem und eine bekannte obere Grenze der Komplexität haben?P S P A C E AP H A AAPSPACEAPHAA

Hinweis: Die Existenz eines solchen Orakels kann Auswirkungen auf die strukturelle Komplexitätstheorie haben. Weitere Informationen finden Sie im folgenden Update.

Update mit Details zu einer Technik für untere Schranken

Ansprüche: Wenn , dann für alle Orakel , .A P / p o l y P S P A C E A = P H APSPACE=PHAP/polyPSPACEA=PHA

Beweisskizze: Angenommen, .PSPACE=PH

Es sei ein Orakel gegeben. Wir können eine Polynomzeit oracle Turing machine erstellen , die für eine gegebene Länge eine Schaltung der Größe Verwendung einer existentiellen Quantifizierung errät und durch Vergleich der Auswertung der Schaltung und des Abfrageergebnisses überprüft, ob die Schaltung entscheidet für jede Länge String mit einer universellen Quantifizierung.Σ 2 M n p ( n ) A nAP/polyΣ2Mnp(n)An

Stellen Sie sich außerdem ein Entscheidungsproblem vor, das ich als quantifizierten Booleschen Kreis (QBC) bezeichne, bei dem Sie einen quantifizierten Booleschen Kreis erhalten und wissen möchten, ob er gültig ist (ähnlich wie QBF). Dieses Problem ist PSPACE-vollständig, da QBF PSPACE-vollständig ist.

Aus der Annahme folgt, dass QBC . Sagen wir für einige ausreichend groß sind. Es sei eine Polynomzeit Turingmaschine, die QBC löst.Q B C Σ k k N Σ kPHQBCΣkkNΣk

Wir können die Berechnung von und (ähnlich wie im Beweis des Karp-Lipton-Theorems) , um eine Polynomzeit oracle Turing machine zu erhalten, die löst .N Σ k Q B C AMNΣkQBCA

Informell nimmt diese neue Maschine als Eingabe ein Orakel-QBC (das ist ein QBC mit Orakel-Toren). Dann berechnet es eine Schaltung, die an Eingängen der Länge berechnet (wobei gleichzeitig die ersten beiden Quantifizierer abgeschält werden). Als nächstes werden die Orakeltore im Orakel QBC durch die Schaltung für . Schließlich wird der Rest des Algorithmus für die Polynomzeit , um für diese modifizierte Instanz zu lösen .n A Σ k Q B CAnAΣkQBC

Nun können wir die bedingte Untergrenze anzeigen.

Folgerung: Wenn es ein Orakel so dass , dann .P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

Beweisskizze: Angenommen, es existiert so dass . Wenn , dann würden wir einen Widerspruch bekommen.P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

Insbesondere wenn , dann haben wir nach dem obigen Anspruch . Es ist jedoch bekannt, dass impliziert .P S P A C E P H N E X P P / p o l y P S P A C E = P HNEXPP/polyPSPACEPHNEXPP/polyPSPACE=PH

(siehe hier für einige Details zu bekannten Ergebnisse für P / poly)

Michael Wehar
quelle
3
Es ist wahrscheinlich erwähnenswert, dass vermutet wird, dass PSPACE PH. dh ein triviales Orakel würde es tun, aber wir können es einfach nicht beweisen.
Thomas unterstützt Monica am
1
Wie genau definieren Sie relativierten PSPACE? In der Literatur taucht mehr als eine Möglichkeit auf. Werden insbesondere Orakelabfragen als polynomisch begrenzt angenommen?
Emil Jeřábek unterstützt Monica am
1
Enthalten Sie "Die Konstruktion von Q-Formeln", große monotone Boolesche Formeln, die alle 2 ^ n qbfs der ursprünglichen Formel in PH bestimmen? Weitere Informationen zu Q-Formeln finden Sie unter Einführung in QSpace, Satisfiability Conference 2002, Internationaler Workshop zu QBFS.
Daniel Pehoushek
1
Ich glaube, ich kann als Untergrenze zeigen, dass ein solches Wesen in der SEH "Konsequenzen in der strukturellen Komplexitätstheorie haben würde". Sollte ich das ziemlich bald posten (was morgen oder in 30 Minuten bedeuten könnte) oder länger unbeantwortet lassen, damit Sie mit größerer Wahrscheinlichkeit eine Antwort mit einer Klasse erhalten, die ausreicht? A
1
Angesichts der Tatsache, dass zufällige Orakel eine hohe Kolmogorov-Komplexität aufweisen, würde ich erwarten, dass eine berechenbare Obergrenze für solche Orakel bemerkenswerte Konsequenzen hat. Starke Obergrenzen wie einfach exponentiell sollten starke Konsequenzen haben. (Natürlich ist dieses Argument rein heuristisch und ich habe derzeit keine Ahnung, wie man es rigoros macht.)
András Salamon

Antworten:

9

Ich glaube, wenn Sie das Argument durchgehen, das z. B. in Abschnitt 4.1 der Umfrage von Ker-I Ko angegeben ist , erhalten Sie eine obere Schranke von . Tatsächlich können wir n 2 hier durch eine beliebige Funktion n f ( n ) ersetzen, wobei f ( n ) als n ∞ gilt . Dies ist nicht ganz das, was gefragt wurde, aber es ist nah.DTIME(22O(n2))n2nf(n)f(n)n

Insbesondere unter Verwendung der Übersetzung zwischen Orakeltrennungen und Schaltkreisuntergrenzen und der folgenden Ko-Notation haben wir Folgendes:

  • Wir werden diagonalisieren über Strings der Länge , wo p n ( x ) = x n + n ist "das" n - te Polynom (in einiger Aufzählung von Poly-Algorithmen) und m ( n ) wird unten angegeben.t(n)=pn(m(n))pn(x)=xn+nnm(n)

  • In Schaltkreisuntergrenzen übersetzt, bedeutet dies, dass wir Schaltkreise mit begrenzter Tiefe für Eingänge in Betracht ziehen .2t(n)

  • Die Anforderung (siehe Seite 15 von Ko) benötigen wir , um 1 zu erfüllenm(n)für allen. Hierdist die Tiefe der Schaltungen gegen wir diagonalisierensoll, oderäquivalenterdas NiveauΣ p d vonPHwir gegen diagonalisieren möchten. Um gegenPHzu diagonalisieren, wählen Sie einfachdals eine Funktion vonn, dieω(1) ist; wir können solch eindwählen1102m/(d1)>dpn(m(n))ndΣdpPHPHdnω(1)ddas wächst zwar willkürlich langsam (möglicherweise unter der Annahme einer Berechenbarkeit für , aber das sollte kein Hindernis sein). Wenn wir annehmen, dass d ( n ) konstant ist (obwohl dies nicht der Fall ist, aber es willkürlich langsam wächst), dann sehen wir, dass m ( n ) um 2 n herum funktionieren sollte.d(n)d(n)m(n)2n

  • Dies bedeutet, dass , daher suchen wir nach einer Untergrenze für Schaltungen mit 2 2 n 2 Eingängen.t(n)2n222n2

  • Trevisan und Xue (CCC '13) zeigten , dass ein einen Auftrag auf den eine gegebene begrenzte Tiefe Schaltung auf finden Eingängen Rechnen nicht PARITY mit einem Samen von p o l y l o g ( N ) der Länge.Npolylog(N)

  • Für uns ist , so dass p o l y l o g ( N ) = 2 O ( n 2 ) . Wir können solche Samen in 2 2 O ( n 2 ) Zeit mit Gewalt überziehen und den ersten verwenden, der funktioniert.N=22n2polylog(N)=2O(n2)22O(n2)

Um durch n f ( n ) zu ersetzen , sei stattdessen p n ( x ) = x f ( n ) + f ( n ) .n2nf(n)pn(x)=xf(n)+f(n)

Interessanterweise, wenn ich richtig verstehe, glaube ich, dass dies impliziert, dass man den Trevisan-Xue verbessern könnte ...

  • ... zu einem pseudodeterministischen / Bellagio- Algorithmus (siehe Andrew Morgans Kommentar unten) würde man erhalten, dass ; oderBPEXPP/poly

  • ... zu einem nichtdeterministischen Algorithmus, die vermuteten Bits , aber dann in liefen p o l y ( N ) die Zeit, und so , dass auf jedem Weg zu akzeptieren es die gleiche Leistung (macht vgl N P S V ), würde es bedeuten , N E X PP / p o l y ; oderpolylog(N)poly(N)NPSVNEXPP/poly

  • ... zu einem deterministischen Algorithmus würde man .EXPP/poly

Dies legt einerseits nahe, warum es schwierig sein sollte, das Switching-Lemma weiter zu derandomisieren - ein Argument, von dem ich nicht sicher bin, ob es zuvor bekannt war! Auf der anderen Seite erscheint mir dies als eine Art interessantes Spiel zwischen Härte und Zufälligkeit (oder ist dies tatsächlich eine neue Sache, Orakel und Zufälligkeit?).

Joshua Grochow
quelle
3
Eine Herausforderung, die hier beschönigt wird, ist, dass das Orakel, das gebaut wird, ein einzelnes, festes Orakel sein muss, sodass die Entscheidung in BPEXP oder was auch immer fällt. Wenn Sie nur einen zufälligen Samen eines guten Generators auswählen, erhalten Sie zwar ein funktionierendes Orakel, aber nicht unbedingt ein Entscheidungsverfahren für dieses Orakel, da verschiedene Samen (im Allgemeinen) verschiedene Orakel ergeben. Sie müssten mehr tun, beispielsweise einen kanonischen Samen finden, um die Konstruktion tatsächlich "konstruktiv" zu gestalten.
Andrew Morgan
3
Auch wenn das Argument BPEXP nicht ergibt, können Sie die Komplexität auf ein endliches EXPH-Niveau bringen?
Emil Jeřábek unterstützt Monica am
2
@ EmilJeřábek: Ohne die Details zu überprüfen, denke ich, dass funktionieren sollte. Raten Sie einen Samen mit , überprüfen sie arbeitet mit , und dann überprüfen, ob es die lexikographisch dest Samen mit ¬ = ¬ , für insgesamt . Σ3EXP¬=¬
Joshua Grochow
2
@EmilJerabek: Natürlich, wenn wir zumindest könnten diese nach unten bekommen , die besser wäre , auch (nicht verbesserungsfähig, ohne dass neue Schaltung untere Schranken zu beweisen), aber ich weiß noch nicht sehen , wie das zu tun ...MAEXP
Joshua Grochow
2
@JoshuaGrochow Ja, dein ursprünglicher Beitrag scheint in Ordnung zu sein. Ich habe Einwände gegen Ihre Antwort an Emil erhoben, wonach das Orakel in EXPH hergestellt werden kann, wo die Laufzeit einfach exponentiell ist. Im Nachhinein hätte ich das klarer sagen sollen.
Andrew Morgan