34
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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