# 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 '13 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$.

I personally don't know why it looks "out of reach" but it does seem hard to prove. Certainly some genuinely new tricks will be needed to prove it.

• A small addendum, if anyone cares: while Avi and I didn't think to do this in our paper, I believe one could fairly easily show by adapting our arguments (e.g., for NEXP vs. P/poly) that any proof of BPP in NP would need to be non-algebrizing as well. Jan 7 '13 at 21:08
• Scott: I've no doubt that is also true! Jan 8 '13 at 4:13
• @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$?
– Mr.
May 15 '17 at 3:35
• Since natural properties generally only speak about barriers against non-uniform (circuit) lower bounds, I don't know what they could say about whether BPP is contained in NP. May 15 '17 at 3:55
• @RyanWilliams is 'Permanent does not have poly-size arithmetic circuits' same as $VNP\neq VP$ or is it weaker?
– Mr.
Sep 12 '17 at 9:48