HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
wouldimplyconp

Problem

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?

Solution

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:

  • RP in Wikipedia



  • Notes on Randomized Algorithms (pdf)



  • RP in the Complexity Zoo

Context

StackExchange Computer Science Q#27735, answer score: 3

Revisions (0)

No revisions yet.