patternMinor
Would $\sf RP = NP$ imply $\sf NP = coNP$?
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?
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:
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.