10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Apr 8 '15 at 7:37
  • $\begingroup$ Proving $\mathbb{BPP} \subseteq \mathbb{NP}$ unconditionally is an open problem. $\endgroup$ – chazisop Aug 5 '15 at 15:26
3
$\begingroup$

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:

  1. RP in Wikipedia
  2. Notes on Randomized Algorithms (pdf)
  3. RP in the Complexity Zoo
$\endgroup$
  • $\begingroup$ or that ​ RP = ZPP . ​ ​ ​ ​ $\endgroup$ – user12859 Apr 26 '16 at 4:43
1
$\begingroup$

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).

$\endgroup$

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.