Relativierte Welt mit

11

Ich würde gerne wissen, ob es eine relativierte Welt gibt, in der . Ich bin auch interessiert zu wissen, ob es eine relativierte Welt gibt, in der P BN P B = P P B ist .PA=NPAPPAPBNPB=PPB

Tayfun Pay
quelle
7
Ich habe einen Blog-Beitrag "extreme Orakel", der eine Liste von Orakel-Ergebnissen enthält, aus denen viele andere folgen, einschließlich der beiden, die Sie fragen. blog.computationalcomplexity.org/2005/08/extreme-oracles.html
Lance Fortnow
2
@Lance: Verdammt, habe das gerade gesehen, nachdem ich meine Antwort gepostet habe! Nun, vielleicht findet das OP meine "hausgemachten" Konstruktionen immer noch nützlich.
Scott Aaronson

Antworten:

14

Ich kenne keine Referenz, aber ich denke, beide sollten machbar sein.

A1MAJORITYPA1 P P A 1 A 2 P H A 1 k t h n k P A 1 , A 2 = N P A 1 , A 2 = P H A 1 , A 2 = P H A 1 A 2 A 2 P H A 1 A C 0 P H A 1NPA1PPA1A2PHA1kthnk(und daher können Sie nur eine konstante Anzahl von Wechsel in der Polynomzeit erhalten). Dieses zweite Orakel sollte . (Beachten Sie, dass nur eine "äußere" Ebene ist, was bedeutet, dass alle Abfragen an durch -Abfragen simuliert werden können.) Schließlich möchten Sie die unteren Grenzen von Yao und Hastad ansprechen (dh das Schalt-Lemma), um zu zeigen, dass eine -Maschine die Instanzen in immer noch nicht lösen kann , und daher (und sicherlich ) bleibt größer.PA1,A2=NPA1,A2=PHA1,A2=PHA1A2A2PHA1AC0PHA1MAJORITYA1PPA1PPA1,A2=PPPHA1

Für Ihr zweites Orakel möchten Sie so konstruieren, dass Sie ein Suchproblem lösen müssen, um einen Teil der Orakel-Zeichenfolge "freizuschalten", der dann Ihre Leistung auf erhöht . (Hier nutzen wir die Tatsache aus, dass und beide .) Eine Subtilität ist, dass der geheime Teil des Orakels nicht einfach eine nicht relativierte vollständige Sprache entscheiden kann: Er muss auch bereitstellen die Antworten auf Berechnungen, die selbst abfragen . Glücklicherweise ist bekannt, wie dies schrittweise erreicht werden kann, wobei die Zirkularität vermieden wird: Im Grunde codieren Sie die Ausgänge desBNPPSPACENPPSPACEPPPSPACEPSPACEPSPACEPSPACEBPSPACEB Maschinen, die für Eingaben der Größe oder weniger abfragen , in einem Teil von , für dessen Zugriff Abfragen der Größe erforderlich sind , und die daher für diese Maschinen "unerreichbar" sind (aber nicht für andere Maschinen). Währenddessen bleiben die Maschinen "völlig im Dunkeln".Bp(n)BP S P A C E B P B.>p(n) PSPACEBPB

Scott Aaronson
quelle