<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-21T05:34:51.400Z
2010-08-21T05:52:03.367Z
2010-08-21T05:52:03.367Z
Robin Kothari
<p>Just to avoid duplicate discussion of the same topic, this is very closely related to a previous question:</p>

<p><a href="https://cstheory.stackexchange.com/questions/64/what-specific-evidence-is-there-for-p-rp/">What specific evidence is there for P = RP?</a></p>

<p>In short, P=BPP follows from hardness assumptions, and P=BPP implies P=coRP.</p>

CC BY-SA 2.5
2010-08-21T16:07:02.747Z
2010-08-21T16:07:02.747Z
2017-04-13T12:32:28.743Z
Moritz
<p>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.  </p>

CC BY-SA 2.5
2010-08-21T16:34:16.570Z
2010-08-21T16:34:16.570Z
Noam
<p>What evidence is there that $coRP \neq NP$?</p>

<p>$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.</p>

CC BY-SA 2.5
2010-08-21T00:18:37.040Z
I think that a little bit of background, or what googling turned up, or both, would make this question much better.
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-21T02:50:46.017Z
$coR$ as in the complement of the Recursive Languages, as in the complement of set of problems solvable by a Turing machine?
Daniel Apon
CC BY-SA 2.5
2010-08-21T05:31:32.763Z
I think coR is the old name for the class now called coRP.
Robin Kothari
CC BY-SA 2.5
2010-08-21T10:26:55.503Z
Sorry for the confusion. See the update.
Serge Gaspers
<cc.complexity-theory><complexity-classes>
What evidence is there that $coRP \neq NP$?
Serge Gaspers
# What evidence is there that $coRP \neq NP$?

(Asked by: username_0 on 2010-08-21)

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.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: I think that a little bit of background, or what googling turned up, or both, would make this question much better.  
> **username_2**: $coR$ as in the complement of the Recursive Languages, as in the complement of set of problems solvable by a Turing machine?  
> **username_3**: I think coR is the old name for the class now called coRP.  
> **username_0**: Sorry for the confusion. See the update.  

---

## 3 answers

### Answer by username_5 on 2010-08-21. Score: 15 | Accepted answer

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.


---

### Answer by username_3 on 2010-08-21. Score: 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.


---

### Answer by username_4 on 2010-08-21. Score: 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?](https://cstheory.stackexchange.com/questions/64/what-specific-evidence-is-there-for-p-rp/)

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


---

