Relatywizowany świat, w którym

Chciałabym wiedzieć, czy istnieje zrelatywizowane świat, w którym . Jestem również zainteresowany, aby wiedzieć, czy istnieje zrelatywizowane świat, w którym . ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$ ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$

cc.complexity-theory oracles relativization

— Tayfun Pay
źródło

Mam wpis na blogu „ekstremalne wyrocznie”, który zawiera listę wyników wyroczni, z których wynika wiele innych, w tym dwa, o które pytasz. blog.computationalcomplexity.org/2005/08/extreme-oracles.html

— Lance Fortnow

@Lance: Cholera, właśnie to zobaczyłem po opublikowaniu mojej odpowiedzi! Cóż, być może OP nadal będzie przydatne dla moich „domowych” konstrukcji.

— Scott Aaronson

Nie znam referencji, ale uważam, że oba powinny być wykonalne.

$A_1$ $MAJORITY$ $P^{A_1}$ $NP^{A_1}$ $PP^{A_1}$ $A_2$ $PH^{A_1}$ $k^{th}$ $n^k$ $P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$ $A_2$ $A_2$ $PH^{A_1}$ $AC^0$ $PH^{A_1}$ $MAJORITY$ $A_1$ $PP^{A_1}$ $PP^{A_1,A_2} = PP^{PH^{A_1}}$

$B$ $NP$ $PSPACE$ $NP^{PSPACE}$ $PP^{PSPACE}$ $PSPACE$ $PSPACE$ $PSPACE$ $B$ $PSPACE^B$ $B$ $p(n)$ $B$ $>p(n)$ $PSPACE^B$ $P^B$

— Scott Aaronson
źródło