<p>For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize.</p>

<p>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 <a href="http://www.cs.sfu.ca/~kabanets/Research/poly.html">Impagliazzo-Kabanets'04</a>, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $NEXP \not\subset P/poly$. </p>

<p>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.</p>

CC BY-SA 3.0
2013-01-07T21:08:47.660Z
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
CC BY-SA 3.0
2013-01-08T04:13:07.413Z
Scott: I've no doubt that is also true!
Ryan Williams
CC BY-SA 3.0
2017-05-15T03:35:58.727Z
@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$?
Turbo
CC BY-SA 3.0
2017-05-15T03:55:51.917Z
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.
Ryan Williams
CC BY-SA 3.0
2017-09-12T09:48:48.313Z
@RyanWilliams is 'Permanent does not have poly-size arithmetic circuits' same as $VNP\neq VP$ or is it weaker?
Turbo
CC BY-SA 3.0
2013-01-07T08:23:44.520Z
2013-01-07T19:47:19.770Z
2013-01-07T19:47:19.770Z
Ryan Williams
<p>Many believe that <span class="math-container">$\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$</span>. However we only know that <span class="math-container">$\mathsf{BPP}$</span> is in the second level of polynomial hierarchy, i.e. <span class="math-container">$\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$</span>. A step towards showing <span class="math-container">$\mathsf{BPP} = \mathsf{P}$</span> is to first bring it down to the first level of the polynomial hierarchy, i.e. <span class="math-container">$\mathsf{BPP} \subseteq \mathsf{NP}$</span>.</p>
<p>The containment would mean that nondeterminism is at least as powerful as randomness for polynomial time.</p>
<p>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) .</p>
<blockquote>
<p>Are there any known interesting consequences for <span class="math-container">$\mathsf{BPP} \subseteq \mathsf{NP}$</span>?</p>
<p>Are there any reasons to believe that proving <span class="math-container">$\mathsf{BPP} \subseteq \mathsf{NP}$</span> is out of reach right now (e.g. barriers or other arguments)?</p>
</blockquote>

<cc.complexity-theory><randomness><randomized-algorithms><nondeterminism><barriers>
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Kaveh
# Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

(Asked by: username_0 on 2013-01-07)

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

**Tags:** cc.complexity-theory, randomness, randomized-algorithms, nondeterminism, barriers


---

## 1 answers

### Answer by username_1 on 2013-01-07. Score: 40 | Accepted answer

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](http://www.cs.sfu.ca/~kabanets/Research/poly.html), 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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: Scott: I've no doubt that is also true!  
> **username_3**: @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$?  
> **username_1**: 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.  
> **username_3**: @RyanWilliams is 'Permanent does not have poly-size arithmetic circuits' same as $VNP\neq VP$ or is it weaker?  

---

