12

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.

Serge Gaspers
  • 5,116
  • 29
  • 42

3 Answers3

15

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.

Noam
  • 9,369
  • 47
  • 58
11

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.

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
4

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.

Moritz
  • 1,714
  • 15
  • 21