Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Well, I don't think it's known that $\: \text{coRP} \subseteq \text{NP} \;$. $\;\;$ –  Ricky Demer Jan 7 '13 at 8:06

1 Answer 1

up vote 33 down vote accepted

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.

share|improve this answer
    
Thank you Ryan. –  Kaveh Jan 7 '13 at 19:45
10  
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. –  Scott Aaronson Jan 7 '13 at 21:08
1  
Scott: I've no doubt that is also true! –  Ryan Williams Jan 8 '13 at 4:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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