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}$?

  • $\begingroup$ 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}$. $\endgroup$
    – Kaveh
    Commented Nov 20, 2013 at 1:12
  • $\begingroup$ 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 $\endgroup$ Commented Nov 25, 2013 at 3:05

1 Answer 1


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}$).

See also What if P = NP? 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.

  • $\begingroup$ 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)})$ $\endgroup$ Commented Nov 25, 2013 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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