Relativierte Welt mit

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 B ≠ N P B = P P B ist .${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$

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

$A_1$$MAJORITY$$P^{A_1}$ 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 $NP^{A_1}$$PP^{A_1}$$A_2$$PH^{A_1}$$k^{th}$$n^k$(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.$P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$$A_2$$A_2$$PH^{A_1}$$AC^0$$PH^{A_1}$$MAJORITY$$A_1$$PP^{A_1}$$PP^{A_1,A_2} = PP^{PH^{A_1}}$

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 des$B$$NP$$PSPACE$$NP^{PSPACE}$$PP^{PSPACE}$$PSPACE$$PSPACE$$PSPACE$$B$$PSPACE^B$ 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".$B$$p(n)$$B$P S P A C E B P $>p(n)$ $PSPACE^B$$P^B$