12
$\begingroup$

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?

$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – Lance Fortnow Mar 20 '15 at 20:55
  • $\begingroup$ 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. $\endgroup$ – TheoryQuest1 Mar 21 '15 at 8:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Andy Drucker Mar 21 '15 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.