Monde relativisé où

11

Je voudrais savoir s'il existe un monde relativisée où . Je suis également intéressé à savoir s'il existe un monde relativisée où P BN P B = P P B .PA=NPAPPAPBNPB=PPB

Tayfun Pay
la source
7
J'ai un article de blog "Extreme Oracles" qui contient une liste de résultats d'Oracle dont beaucoup d'autres suivent, y compris les deux que vous demandez. blog.computationalcomplexity.org/2005/08/extreme-oracles.html
Lance Fortnow
2
@Lance: Merde, je viens de voir ça après avoir posté ma réponse! Eh bien, peut-être que l'OP trouvera toujours mes constructions "maison" utiles.
Scott Aaronson

Réponses:

14

Je ne connais pas de référence, mais je pense que les deux devraient être réalisables.

A1MAJORITYPA1NPA1PPA1A2PHA1kthnkPA1,A2=NPA1,A2=PHA1,A2=PHA1A2A2PHA1AC0PHA1MAJORITYA1PPA1PPA1,A2=PPPHA1

BNPPSPACENPPSPACEPPPSPACEPSPACEPSPACEPSPACEBPSPACEBBp(n)B>p(n) PSPACEBPB

Scott Aaronson
la source