<p>Yes, it is safe to claim that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$ -- and that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{BPP}$.</p>

<p>One consequence of $\mathsf{NP} = \mathsf{ZPP}$ is that computational cryptography is impossible.  This is described as the world Algorithmica in Impagliazzo's famous five worlds:</p>

<ul>
<li><a href="http://www.cs.ucsd.edu/users/russell/average.ps" rel="nofollow">A Personal View of Average-Case Complexity</a>.  Russell Impagliazzo.  1995 Complexity Conference. (A PDF version is <a href="http://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf" rel="nofollow">here</a>).</li>
</ul>

<p>Note that as far as practical consequences go, Impagliazzo says it doesn't matter much whether we have $\mathsf{P} = \mathsf{NP}$ or $\mathsf{NP} \subseteq \mathsf{BPP}$ (he even calls the latter the "moral equivalent" of $\mathsf{P} = \mathsf{NP}$).</p>

<p>See also <a href="http://blog.computationalcomplexity.org/2004/05/what-if-p-np.html" rel="nofollow">What if P = NP?</a> for additional practical consequences (assuming the constants hidden by asymptotic notation are not too large).</p>

<p>I don't know whether there are any surprising implications for complexity classes.</p>

CC BY-SA 3.0
2013-11-25T03:07:25.997Z
For complexity classes, if NP = BPP, then PH collapses to the second level. I consider NP = BPP itself more shocking, though. Also P $\neq$ NP = BPP implies $\mathsf{DTIME}(2^{O(n)}) \subseteq \mathsf{size}(2^{o(n)})$
Sasho Nikolov
CC BY-SA 3.0
2013-11-19T19:18:38.440Z
2013-11-25T01:15:25.027Z
2013-11-25T01:15:25.027Z
D.W.
<p>Consider the complexity classes <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aN#np">$\mathsf{NP}$</a> and <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aZ#zpp">$\mathsf{ZPP}$</a>. Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply $\mathsf{P} = \mathsf{NP}$. For example, there are many inapproximability results depending on $\mathsf{NP} \neq \mathsf{ZPP}$, but what evidence do we have for believing they would indeed be not equal?</p>

<p>In other words, what would be the consequences of $\mathsf{NP} = \mathsf{ZPP}$? Is it safe to claim that likewise for $\mathsf{P}$ and $\mathsf{NP}$, many theorists also believe $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$?</p>

CC BY-SA 3.0
2013-11-20T01:12:28.827Z
Many experts conjecture that $\mathsf{BPP} = \mathsf{P}$. That is one of the main reasons why many experts conjecture that $\mathsf{BPP}$ is not equal to $\mathsf{NP}$ (as most experts conjecture that $\mathsf{NP}$ is not equal to $\mathsf{P}$). $\mathsf{ZPP}$ is between $\mathsf{P}$ and $\mathsf{BPP}$ and therefore it is a common conjecture that it is not equal to $\mathsf{NP}$.
Kaveh
CC BY-SA 3.0
2013-11-25T03:05:50.070Z
aside from complexity theory considerations, the usual arguments why we do not believe P = NP work for BPP = NP: a lot of people have tried to come up with fast algorithms for NP-complete problems, and it's not like they haven't thought about Monte Carlo or Las Vegas algorithms, too
Sasho Nikolov
<cc.complexity-theory><complexity-classes><np>
Consequences and state-of-the-art of NP ≠ ZPP?
Juho
# Consequences and state-of-the-art of NP ≠ ZPP?

(Asked by: username_0 on 2013-11-19)

Consider the complexity classes [$\mathsf{NP}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aN#np) and [$\mathsf{ZPP}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aZ#zpp). Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply $\mathsf{P} = \mathsf{NP}$. For example, there are many inapproximability results depending on $\mathsf{NP} \neq \mathsf{ZPP}$, but what evidence do we have for believing they would indeed be not equal?

In other words, what would be the consequences of $\mathsf{NP} = \mathsf{ZPP}$? Is it safe to claim that likewise for $\mathsf{P}$ and $\mathsf{NP}$, many theorists also believe $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$?

**Tags:** cc.complexity-theory, complexity-classes, np

> **Comments:**
> **username_1**: Many experts conjecture that $\mathsf{BPP} = \mathsf{P}$. That is one of the main reasons why many experts conjecture that $\mathsf{BPP}$ is not equal to $\mathsf{NP}$ (as most experts conjecture that $\mathsf{NP}$ is not equal to $\mathsf{P}$). $\mathsf{ZPP}$ is between $\mathsf{P}$ and $\mathsf{BPP}$ and therefore it is a common conjecture that it is not equal to $\mathsf{NP}$.  
> **username_2**: aside from complexity theory considerations, the usual arguments why we do not believe P = NP work for BPP = NP: a lot of people have tried to come up with fast algorithms for NP-complete problems, and it's not like they haven't thought about Monte Carlo or Las Vegas algorithms, too  

---

## 1 answers

### Answer by username_3 on 2013-11-19. Score: 4 | Accepted answer

Yes, it is safe to claim that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$ -- and that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{BPP}$.

One consequence of $\mathsf{NP} = \mathsf{ZPP}$ is that computational cryptography is impossible. This is described as the world Algorithmica in Impagliazzo's famous five worlds:

* [A Personal View of Average-Case Complexity](http://www.cs.ucsd.edu/users/russell/average.ps). Russell Impagliazzo. 1995 Complexity Conference. (A PDF version is [here](http://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf)).

Note that as far as practical consequences go, Impagliazzo says it doesn't matter much whether we have $\mathsf{P} = \mathsf{NP}$ or $\mathsf{NP} \subseteq \mathsf{BPP}$ (he even calls the latter the "moral equivalent" of $\mathsf{P} = \mathsf{NP}$).

See also [What if P = NP?](http://blog.computationalcomplexity.org/2004/05/what-if-p-np.html) for additional practical consequences (assuming the constants hidden by asymptotic notation are not too large).

I don't know whether there are any surprising implications for complexity classes.

> **Comments:**
> **username_2**: For complexity classes, if NP = BPP, then PH collapses to the second level. I consider NP = BPP itself more shocking, though. Also P $\neq$ NP = BPP implies $\mathsf{DTIME}(2^{O(n)}) \subseteq \mathsf{size}(2^{o(n)})$  

---

