According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference? Furthermore, am I correct that if this indeed the case, then $NP-COMPLETE \cap RP = \emptyset$ since we can use $NP$ completeness to solve all other $NP$ problems?

  • 1
    $\begingroup$ Wiki states that we need to assume this in addition to P=BPP, which makes it trivial. This implication is not known unconditionally. $\endgroup$ – Ariel Jun 26 at 17:05

You have not accurately summarized the statement in Wikipedia. The statement in Wikipedia also needs the extra assumption that $P=BPP$, which is widely conjectured but has not been proven to be true.

With that clarification, no reference is needed -- the reasoning is straightforward and already described on Wikipedia. If $P=BPP$, then $P=RP=co-RP$ (since $BPP=co-BPP$ and $RP \subseteq BPP$ and $co-RP \subseteq BPP$). If additionally $P \ne NP$, then it follows that $RP \ne NP$.

Yes, if $RP \ne NP$, then $NPC \cap RP = \emptyset$.

| cite | improve this answer | |

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.