BPP borne supérieure

Question

fait $ BPP de subseteq P ^ {NP} $? il semble raisonnable, mais je ne sais pas s'il y a une preuve! pouvait-on poster une preuve ou tout matériel qui traite de la déclaration ou quelque chose qui ressemble à ça.

Answer 1

Il est ouvert si $ \ {mathsf BPP} \ subseteq \ mathsf {P} ^ {\ {mathsf NP}} $.

Le mieux que nous pouvons actuellement dire environ $ \ mathsf {BPP} $ est qu'il est contenu dans S ₂ P , une classe dans $ \ Sigma_2 \ cap \ Pi_2 $ et $ \ mathsf {} ZPP ^ {\ {mathsf NP}} $. Voir les références données dans Wikipedia.

Si $ \ {mathsf BPP} \ subseteq \ mathsf {P} ^ {\ mathsf {NP}} $, alors ce fait ne pas relativiser (Stockmeyer, On Algorithmes d'approximation pour #P ).