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)?

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

1 Answer 1


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.

  • 12
    $\begingroup$ 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. $\endgroup$ Commented Jan 7, 2013 at 21:08
  • 3
    $\begingroup$ Scott: I've no doubt that is also true! $\endgroup$ Commented Jan 8, 2013 at 4:13
  • $\begingroup$ @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$? $\endgroup$
    – Turbo
    Commented May 15, 2017 at 3:35
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 15, 2017 at 3:55
  • $\begingroup$ @RyanWilliams is 'Permanent does not have poly-size arithmetic circuits' same as $VNP\neq VP$ or is it weaker? $\endgroup$
    – Turbo
    Commented Sep 12, 2017 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.