# Consequences and state-of-the-art of NP ≠ ZPP?

Consider the complexity classes $\mathsf{NP}$ and $\mathsf{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}$?

## migrated from cs.stackexchange.comNov 24 '13 at 22:45

This question came from our site for students, researchers and practitioners of computer science.

• 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 Nov 20 '13 at 1:12
• 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 Nov 25 '13 at 3:05

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:
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}$).
• 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 Nov 25 '13 at 3:07