Wyrocznia, względem której

Zoologia złożoności autorstwa Grega Kuperberga stwierdza, że istnieje język $X$ taki, że $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ - innymi słowy, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X}$ - ale nie podaje odniesienia do tego wyniku. Dlaczego tak się dzieje? Lub gdzie można znaleźć dowód?

To pytanie jest częściowo uzasadnione moją odpowiedzią na pytanie „Co wiadomo o interaktywnych dowodach z wieloma dowodami za pomocą krótkich wiadomości?” Joe Fitzsimons.

Wysłałem to pytanie na math.stackexchange.com 2 października, ale nie otrzymałem żadnej odpowiedzi i usunąłem pytanie matematyczne po tym postu na meta.math.

— Tsuyoshi Ito
źródło

może to pomaga? icsi.berkeley.edu/pubs/techreports/tr-92-078.pdf

— Alessandro Cosentino

@Alessandro: Dzięki, wydaje się to bardzo istotne. Sprawdzę to.

— Tsuyoshi Ito,

link do wpisu w zoo złożoności zagubił się podczas edycji odpowiedzi. Oto, zaktualizowano po prośbie @MarcosVillagra: qwiki.stanford.edu/index.php/Complexity_Zoo:D#delta2p

— Alessandro Cosentino,

Wyrocznia wraca do Stockmeyera w 1983 roku. Heller dał mocniejszy wynik: w relatywizowanym świecie w 1986 roku. Karpiniski i Verbeek (wspomniani w komentarzach) potwierdzają wynik Hellera. $BPP = EXP^{NP}$

— Lance Fortnow
źródło

Dziękuję za przybicie. Poczekam jeden dzień lub dwa, a następnie zaakceptuję, chyba że wydarzy się coś zaskakującego.

— Tsuyoshi Ito,

byłoby miło, gdyby ktoś zaktualizował wpis w zoo złożoności. Mógłbym to zrobić, ale nie wiem jak.

— Marcos Villagra,

@MarcosVillagra może po prostu napisz do Grega Kuperberga?

— Suresh Venkat

@SureshVenkat Jeśli chodzi o zoologię złożoności, niestety nie jest to publiczna wiki. Jeśli chodzi ci o Zoo Złożoności, to już go zaktualizowałem.

— Alessandro Cosentino,