# Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Many believe that $$\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$$. However we only know that $$\mathsf{BPP}$$ is in the second level of polynomial hierarchy, i.e. $$\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$$. A step towards showing $$\mathsf{BPP} = \mathsf{P}$$ is to first bring it down to the first level of the polynomial hierarchy, i.e. $$\mathsf{BPP} \subseteq \mathsf{NP}$$.

The containment would mean that nondeterminism is at least as powerful as randomness for polynomial time.

It also means that if for a problem we can find the answers using efficient (polynomial time) randomized algorithms then we can verify the answers efficiently (in polynomial time) .

Are there any known interesting consequences for $$\mathsf{BPP} \subseteq \mathsf{NP}$$?

Are there any reasons to believe that proving $$\mathsf{BPP} \subseteq \mathsf{NP}$$ is out of reach right now (e.g. barriers or other arguments)?

• Well, I don't think it's known that $\: \text{coRP} \subseteq \text{NP} \;$. $\;\;$
– user6973
Jan 7, 2013 at 8:06

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize.
But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $NEXP \not\subset P/poly$.
• @RyanWilliams Does natural proofs barrier apply for BPP in NP too? asking this because how was it possible to overcome the barrier (if any at all) to show containment in $\Sigma_2$? May 15, 2017 at 3:35
• @RyanWilliams is 'Permanent does not have poly-size arithmetic circuits' same as $VNP\neq VP$ or is it weaker? Sep 12, 2017 at 9:48