Czy istnienie problemów z uzupełnieniem PH relatywizuje się?

Wynik Baker-Gill-Solovay wykazał, że pytanie P = NP nie relatywizuje, w tym sensie, że żaden dowód relatywizacyjny (niewrażliwy na obecność wyroczni) nie może rozstrzygnąć pytania P = NP.

Moje pytanie brzmi: czy istnieje podobny wynik pytania: „Czy istnieje problem z pełnym PH?” Odpowiedź przecząca na to pytanie oznaczałaby P! = NP; odpowiedź twierdząca byłaby mało prawdopodobna, ale interesująca, ponieważ oznaczałoby, że PH spada do pewnego poziomu.

Nie jestem pewien, ale podejrzewam, że wyrocznia TQBF doprowadziłaby do tego, że PH byłaby równa PSPACE, a tym samym miałaby pełny problem. Oprócz tego, że jestem niepewny, jestem ciekawy, czy istnieje wyrocznia, w stosunku do której PH prawdopodobnie nie ma pełnego problemu.

-Philip

Yao wykazał w 1985 r., Że istnieją wyrocznie, wobec których Hierarchia Wielomianowa jest nieskończona. W stosunku do takiej wyroczni nie ma problemów z kompletnym PH.

Ponadto masz rację, że z wyrocznią TQBF PH równa się PSPACE. W rzeczywistości nawet P = PSPACE w obecności wyroczni TQBF.

PH ma pełną problemy wtedy i tylko wtedy, gdy zapadnie: jeśli zawiera pełny problemu , a następnie jakiegoś , tak . I odwrotnie, jeśli jest skończone, to dla pewnego , a jest wtedy PH-kompletne.L ∈ Σ k P k P H = Σ k P P H P H = Σ k$L$$L \in \Sigma_k P$$k$$PH = \Sigma_k P$$PH$$PH = \Sigma_k P$Σ k S A $k$$\Sigma_k SAT$

Jak zauważył Srikanth, istnieją wyrocznie, względem których PH jest nieskończone. (W rzeczywistości znalezienie takich wyroczni było jednym z powodów, dla których ludzie zaczęli patrzeć na PARYMENT, a nie w ). Stosując podobne techniki oparte na obwodach, istnieje również, dla każdego , wyrocznia, która zapada dokładnie ( Ker-I Ko, SICOMP 18 (2), 1989 ). Zainteresowanym polecam ankietę Ker-I Ko . k P H Σ k$AC^0$$k$$PH$$\Sigma_k P$