<p>It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world:</p>

<ol>
<li>If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions? </li>
<li>If NP=PSPACE, does RP=co-RP=ZPP follow automatically or does it require additional conditions? </li>
</ol>

<p>In both cases what additional constraints are required to prove RP=co-RP=ZPP if the conditions above are not sufficient?</p>

CC BY-SA 3.0
2015-03-20T20:55:32.073Z
As far as I know, no one has looked at the question as to whether there is an oracle $A$ where $NP^A=co-NP^A$ but $RP^A\neq co-RP^A$. My intuition says such an oracle should exist but the construction will be ugly.
Lance Fortnow
CC BY-SA 3.0
2015-03-21T08:01:32.300Z
Respected Prof. Thanks for the reply. What i understood was its still an open Q, but pointing to an Oracle as you indicated. my understanding is as follows: 1. Assuming in the original case the Oracle-A for NP, and Oracle-B for co-NP 2. If NP=co-NP, either Oracle-A or Oracle-B could be used for both NP and co-NP 3. And since both RP and co-RP are 'weaker' subsets of NP and co-NP respectively, wouldn't it point to a common Oracle for both RP and co-RP hence proving them equal. It can be totally wrong as i am still a beginner learning formal foundations of the domain.
TheoryQuest1
CC BY-SA 3.0
2015-03-21T10:26:00.580Z
TheoryQuest, even if NP=co-NP (without an oracle, which is considered unlikely) it doesn't follow that NP^A = co-NP^A relative to some arbitrary oracle.  I don't follow the rest of the argument in your comment but it looks faulty.
Andy Drucker
<cc.complexity-theory><complexity-classes><relativization>
Impact of proof of NP=co-NP on RP vs co-RP Question?
TheoryQuest1
# Impact of proof of NP=co-NP on RP vs co-RP Question?

(Asked by: username_0 on 2015-03-20)

It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world:

1. If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions?
2. If NP=PSPACE, does RP=co-RP=ZPP follow automatically or does it require additional conditions?

In both cases what additional constraints are required to prove RP=co-RP=ZPP if the conditions above are not sufficient?

**Tags:** cc.complexity-theory, complexity-classes, relativization

> **Comments:**
> **username_1**: As far as I know, no one has looked at the question as to whether there is an oracle $A$ where $NP^A=co-NP^A$ but $RP^A\neq co-RP^A$. My intuition says such an oracle should exist but the construction will be ugly.  
> **username_0**: Respected Prof. Thanks for the reply. What i understood was its still an open Q, but pointing to an Oracle as you indicated. my understanding is as follows: 1. Assuming in the original case the Oracle-A for NP, and Oracle-B for co-NP 2. If NP=co-NP, either Oracle-A or Oracle-B could be used for both NP and co-NP 3. And since both RP and co-RP are 'weaker' subsets of NP and co-NP respectively, wouldn't it point to a common Oracle for both RP and co-RP hence proving them equal. It can be totally wrong as i am still a beginner learning formal foundations of the domain.  
> **username_2**: TheoryQuest, even if NP=co-NP (without an oracle, which is considered unlikely) it doesn't follow that NP^A = co-NP^A relative to some arbitrary oracle.  I don't follow the rest of the argument in your comment but it looks faulty.  

---

## 0 answers

