Mundo relativizado donde

Me gustaría saber si existe un mundo donde relativizada . También estoy interesado en saber si existe un mundo donde relativizada . ${\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
fuente

Tengo una publicación de blog "oráculos extremos" que tiene una lista de resultados de oráculos de la que muchos otros siguen, incluidos los dos que usted pregunta. blog.computationalcomplexity.org/2005/08/extreme-oracles.html

Lance Fortnow

@Lance: Maldición, ¡acabo de ver eso después de publicar mi respuesta! Bueno, tal vez el OP todavía encuentre útiles mis construcciones "caseras".

Scott Aaronson

Respuestas:

No conozco una referencia, pero creo que ambos deberían ser factibles.

$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
fuente