What evidence is there that $coRP \neq NP$?

$coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

  • $\begingroup$ I think that a little bit of background, or what googling turned up, or both, would make this question much better. $\endgroup$ – Evgenij Thorstensen Aug 21 '10 at 0:18
  • $\begingroup$ $coR$ as in the complement of the Recursive Languages, as in the complement of set of problems solvable by a Turing machine? $\endgroup$ – Daniel Apon Aug 21 '10 at 2:50
  • 2
    $\begingroup$ I think coR is the old name for the class now called coRP. $\endgroup$ – Robin Kothari Aug 21 '10 at 5:31
  • $\begingroup$ Sorry for the confusion. See the update. $\endgroup$ – Serge Gaspers Aug 21 '10 at 10:26

When considering the power of non-determinism (P vs NP), randomization seems like a 2nd order issue. In particular when we think about "P=NP?" we are really interested in the question "are all NP problems tractable", where randomization could be allowed, so tractability really means "in BPP". So "NP contained in BPP" seems essentially as unlikely as "P=NP", and in fact if these were considered different then people would care about the former rather than the latter. (The peculiar variant "NP in coRP" is formally somewhere in the middle between these two, but conceptually essentially the same). If good enough pseudo random generators exist then the two questions are formally the same. Similarly, in "non-uniform settings" randomization is known not to help and thus "NP in BPP" implies that NP has poly-size circuits.


If by coR you mean coRP, then it is believed by many that P = RP = coRP = BPP, and also that P is not equal to NP, thus coRP is not equal to NP.

More directly, if NP were equal to coRP, then it would be contained in coNP (since coRP is contained in coNP). Then by symmetry, NP = coNP. This would imply that the polynomial hierarchy collapses to the first level. It is, however, widely believed that the polynomial hierarchy is infinite.


Just to avoid duplicate discussion of the same topic, this is very closely related to a previous question:

What specific evidence is there for P = RP?

In short, P=BPP follows from hardness assumptions, and P=BPP implies P=coRP.


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.