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

12

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

cc.complexity-theory complexity-classes

— Philip White
źródło

16

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.

— Srikanth
źródło

Dzięki, to była pierwsza odpowiedź, która dokładnie odpowiedziała na moje pytanie.

— Philip White,

Aby wyjaśnić czytelnikom jeden punkt, dla każdej wyroczni istnieją -kompletne problemy . Oznacza to, że zawsze występują pełne problemy dla każdego ustalonego poziomu hierarchii. Mianowicie, decyzja, czy gracz 1 wygrywa daną grę typu round, w której sędzia gry jest opisany przez obwód z dostępem do wyroczni na , to . (Zakładam, że gracz 1 otrzymuje pierwszy ruch; w przeciwnym razie jest to .)

Σ_{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

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$ $L \in \Sigma_k P$ $k$ $PH = \Sigma_k P$ $PH$ $PH = \Sigma_k P$ $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 . $AC^0$ $k$ $PH$ $\Sigma_k P$

— Joshua Grochow
źródło

Dziękuję, ta odpowiedź jest również przydatna. Wydaje mi się, że wiedziałem, że ma pełne problemy, jeśli się zawali, ale doceniam dodatkowe szczegóły, szczególnie w odniesieniu do komentarza PARITY / AC0.

— Philip White,