Czy ?

Wiemy, że pierwszy poziom hierarchii wielomianowej (tj. NP i co-NP) znajduje się w PP i że . Wiemy również z twierdzenia Tody, że .$PP \subseteq PSPACE$$PH \subseteq P^{PP}$

Czy wiemy, czy ? Jeśli nie, to dlaczego z wyrocznią jest silniejszy niż ? Czy to możliwe, że i PP \ nsubseteq PH ?$PH \subseteq PP$$P$$PP$$PP$$PH \nsubseteq PP$$PP \nsubseteq PH$

To pytanie jest bardzo proste, ale nie znalazłem żadnych zasobów.

Zadałem to powiązane, ale znacznie mniej szczegółowe pytanie na temat przepełnienia matematyki, zanim dowiedziałem się więcej na ten temat.

Oto nieco powiązane (ale inne) pytanie: czy $coNP^{\#P}=NP^{\#P}=P^{\#P}$ ?

Aktualizacja: Spójrz na pytanie Noama Nisana tutaj: Więcej na temat PH w PP?

Huck, jak zauważyli Lance i Robin, mamy wyrocznie, w stosunku do których PH nie jest w PP. Ale to nie odpowiada na twoje pytanie, jaka była sytuacja w „prawdziwym” (nierelatywizowanym) świecie!

Krótka odpowiedź jest taka, że ​​(podobnie jak w przypadku wielu innych teorii złożoności) nie wiemy.

Ale dłuższą odpowiedzią jest to, że istnieją bardzo dobre powody, aby przypuszczać, że rzeczywiście PH ⊆ PP.

Po pierwsze, Twierdzenie Tody implikuje PH ⊆ BP.PP, gdzie BP.PP jest klasą złożoności, która „jest na PP tak jak BPP na P” (innymi słowy, PP, gdzie można użyć randomizacji, aby zdecydować, które obliczenia WIĘKSZOŚCI chcesz wykonać). Po drugie, zgodnie z prawdopodobnymi hipotezami derandomizacji (podobnymi do tych, o których wiadomo, że oznaczają P = BPP, autorstwa Nisana-Wigdersona, Impagliazzo-Wigdersona itp.), Mielibyśmy PP = BP.PP.

Dodatek, aby odpowiedzieć na inne pytania:

(1) Powiedziałbym, że nie mamy ani jednej przekonującej intuicji w kwestii, czy PP = P ^PP . Wiemy z wyników Beigela-Reingolda-Spielmana i Fortnow-Reingolda, że ​​PP jest zamknięty z powodu nieadaptacyjnych (tabel prawdy) redukcji. Innymi słowy, maszyna P, która może wykonywać równoległe zapytania do wyroczni PP, nie jest bardziej wydajna niż sama PP. Ale fakt, że wyniki te całkowicie się psują w przypadku adaptacyjnych (nierównoległych) zapytań do wyroczni PP sugeruje, że być może te ostatnie są naprawdę potężniejsze.

(2) Podobnie, NP ^PP i coNP ^PP mogą być jeszcze silniejsze niż ^{PP PP} . PP ^PP może być jeszcze mocniejszy i tak dalej. Sekwencja P, PP, P ^PP , PP ^PP , P ^{PP ^ PP} itd. Nazywa się hierarchią zliczania i podobnie jak ludzie przypuszczają, że PH jest nieskończony, tak też można przypuszczać (choć może z mniejszą pewnością!), Że CH jest nieskończony. Jest to ściśle związane z przekonaniem, że w obwodach progowych o stałej głębokości (tj. Sieci neuronowe) dodanie większej liczby bramek progowych daje większą moc obliczeniową.

Richard Beigel ma wyrocznię, w stosunku do której nie jest zawarty w PP.$P^{NP}$

Vereshchagin [Ver] wykazał, że istnieje wyrocznia, w stosunku do której AM nie jest zawarty w PP. (Ten wynik wydaje się nieporównywalny z wynikiem vs PP.)$P^{NP}$

[Ver] NK Vereshchagin. O mocy PP , Proceedings of IEEE Complexity'92, s. 138-143, 1992.

Coś, o czym do tej pory nie wspomniano (o ile mi wiadomo) i co dotyczy nierelatywizowanego świata:

Zostało to zaobserwowane przez Vyalyi w tym artykule i wynika z umocnienia dwóch twierdzeń:

1. Twierdzenie Tody - Vyalyi pokazuje, że jedno zapytanie do wyroczni wystarcza, aby „ maszyna ” symulowała .$\sharp P$$P$$PH$
2. Włączenie udowodnione przez Kitaev i Watrous. Vyalyi udowadnia, że znajduje się również w , klasie zawartej w .$QMA \subseteq PP$$QMA$$A_0PP$$PP$