Question

does $BPP\subseteq P^{NP}$ ? it seems reasonable but I don't know if there is a proof of this!could any one post a proof or any material that discusses the statement or something that look like this .

Was it helpful?

Solution

It's open whether $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$.

The best we can currently say about $\mathsf{BPP}$ is that it is contained in S2P, a class contained in $\Sigma_2 \cap \Pi_2$ and $\mathsf{ZPP}^{\mathsf{NP}}$. See references given at Wikipedia.

If $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$, then this fact does not relativize (Stockmeyer, On Approximation Algorithms for #P).

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top