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.com Nov 24 '13 at 22:45

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

  • $\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 Nov 20 '13 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$ – 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}$).

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$ – Sasho Nikolov Nov 25 '13 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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