# Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$?

I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the other direction is trivial if $\sf RP = NP$) but to no avail, and I'm not even sure that it's true.

What do you think?

• I don't think there's a particular formal reason to think so (but no reason not to either). In short, I believe it is open. – Luke Mathieson Apr 8 '15 at 7:37
• Proving $\mathbb{BPP} \subseteq \mathbb{NP}$ unconditionally is an open problem. – chazisop Aug 5 '15 at 15:26

If we will able prove that RP is closed under complement then we can say that If RP = NP then it imply NP = Co-NP.

But we don't know whether RP=Co-RP or not. BPP = P can be proved under some reasonable assumptions but RP $\subseteq$ BPP.

If we show that RP = BPP then your statement will be correct.

References:

• or that ​ RP = ZPP . ​ ​ ​ ​ – user12859 Apr 26 '16 at 4:43

Use $\mathsf{RP=NP\implies NP\subseteq P/poly}$ in Cook and Krajicek, Consequences of the provability of NP$\,\subseteq\,$P/poly (Journal of Symbolic Logic, 72(4):1353–71, 2007; PS).