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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 8, 2015 at 7:37
  • $\begingroup$ Proving $\mathbb{BPP} \subseteq \mathbb{NP}$ unconditionally is an open problem. $\endgroup$
    – chazisop
    Commented Aug 5, 2015 at 15:26

2 Answers 2

Reset to default
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
Improve this answer
$\endgroup$
1
  • $\begingroup$ or that ​ RP = ZPP . ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Apr 26, 2016 at 4:43
0
$\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).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.