Relativiert sich die Existenz von PH-vollständigen Problemen?

12

Das Baker-Gill-Solovay-Ergebnis zeigte, dass die P = NP-Frage nicht relativiert, in dem Sinne, dass kein relativierender Beweis (unempfindlich gegenüber dem Vorhandensein eines Orakels) möglicherweise die P = NP-Frage lösen kann.

Meine Frage lautet: Gibt es ein ähnliches Ergebnis für die Frage "Gibt es ein PH-vollständiges Problem?" Eine negative Antwort auf diese Frage würde bedeuten, dass P! = NP; Eine bejahende Antwort wäre unwahrscheinlich, aber interessant, da dies bedeuten würde, dass der PH-Wert bis zu einem gewissen Grad zusammenbricht.

Ich bin nicht sicher, aber ich vermute, dass ein TQBF-Orakel dazu führen würde, dass PH gleich PSPACE ist und somit ein vollständiges Problem vorliegt. Ich bin nicht nur unsicher, sondern auch gespannt, ob es ein Orakel gibt, zu dem PH nachweislich kein vollständiges Problem hat.

-Philip

cc.complexity-theory complexity-classes Philip White
quelle

16

Yao zeigte 1985, dass es Orakel gibt, zu denen die Polynom-Hierarchie unendlich ist. In Bezug auf ein solches Orakel gibt es keine PH-vollständigen Probleme.

Sie haben auch Recht, dass bei einem TQBF-Orakel PH gleich PSPACE ist. Tatsächlich ist sogar P = PSPACE in Gegenwart eines TQBF-Orakels.

Srikanth
quelle

Danke, dies war die erste Antwort auf meine Frage.

Philip White

Um den Lesern einen Punkt zu verdeutlichen, gibt es für jedes Orakel

-vollständige Probleme . Das heißt, es gibt immer vollständige Probleme für jede feste Ebene der Hierarchie. Die Entscheidung, ob Spieler 1 ein gegebenes

Runden-Spiel gewinnt , bei dem der Schiedsrichter des Spiels durch eine Schaltung mit Orakelzugriff auf

, ist

-vollständig. (Ich gehe hier davon aus, dass Spieler 1 den ersten Zug bekommt; ansonsten ist es

-complete.)

Σ_{k} P^{A}

$\Sigma_k P^A$

A

$A$

k

$k$

A

$A$

Σ_{k} P

$\Sigma_k P$

Π_{k} P

$\Pi_k P$

Andy Drucker

14

$L$ $L \in \Sigma_k P$ $k$ $PH = \Sigma_k P$ $PH$ $PH = \Sigma_k P$ $k$ $\Sigma_k SAT$

$AC^0$ $k$ $PH$ $\Sigma_k P$

Joshua Grochow
quelle

Danke, diese Antwort ist auch nützlich. Ich denke, ich wusste, dass es vollständige Probleme hat, wenn es zusammenbricht, aber ich schätze die zusätzlichen Details, insbesondere in Bezug auf den PARITY / AC0-Kommentar.

Philip White

Relativiert sich die Existenz von PH-vollständigen Problemen?

Antworten: