2

This appears in solutions to an exercise I had:

Question: Prove that $RP^{RP}=RP$, or show that it is equivalent to an open question.

Answer: $RP^{RP}=RP$ is equivalent to the open question $RP=co-RP$.
If $RP=co-RP$, then $RP=RP \cap co−RP=ZPP$, and therefore $RP^{RP} = ZPP^{ZPP} = ZPP = RP$.
If $RP^{RP}=RP$, then $co−RP \subseteq RP^{RP} = RP$, therefore $RP=co-RP$.

I understand everything except for the last part, If $L \in co-RP$, I don't understand how access to the oracle helps to build a probabilistic machine that proves $L \in RP^{RP}$.

Any explanation would be appreciated.

Community
  • 1
Cauthon
  • 389
  • 3
  • 16
  • have you got any references for $RP^{RP}$? – JMP Aug 28 '15 at 10:55
  • @JonMarkPerry Unfortunately no, but in the exercise I read this notation simply means that a language in $RP^{RP}$ is a language that can be decided by an $RP$ machine (with the suitable probabilities) that has an access to a $RP$ oracle. – Cauthon Aug 28 '15 at 10:58
  • @JonMarkPerry In general $A^B = \bigcup_{L \in B} A^L$ where $A^L$ means solvable by an algorithm in class $A$ with an oracle for the language $L$. – Loreno Heer Aug 28 '15 at 11:07
  • @Cauthon can you provide a link to the article? – Loreno Heer Aug 28 '15 at 11:24
  • @LorenoHeer it is answers to an exercise in Hebrew, I translated it word for word and posted in the original question. The writer seems to think it is obvious :/ – Cauthon Aug 28 '15 at 11:36
  • @Cauthon Oh, that makes more sense. So the statement only holds under the condition that $RP^{RP} = RP$. – Loreno Heer Aug 28 '15 at 11:38
  • @LorenoHeer the part that $co-RP \subseteq RP^{RP}$ isn't related. This is stated as obvious, and since we assume that $RP^{RP} = RP$, we get that $co-RP \subseteq RP$ which proves that $RP = co-RP$. – Cauthon Aug 28 '15 at 11:40
  • It seems I was confused with the definition of an oracle: http://cs.stackexchange.com/questions/45640/prove-that-co-rp-subseteq-rprp Thanks! – Cauthon Aug 28 '15 at 12:44

1 Answers1

-1

A definition of $RP^{RP}$ is given at Wikipedia.

A definition of an oracle is given on the same page here.

An oracle $O$ therefore takes an input $I$ and has a list of strings $S$ that produce 'yes' if $I\in S$ and 'no' otherwise.

So let $S=\{'no'\}$, and if the output from $RP$ is 'yes', then the output from $O$ is 'no' and vice versa.

JMP
  • 21,771
  • 1
    I don't quite understand what you mean. If you mean to simply flip the answers, that doesn't work out with the necessary $RP$ probabilities (otherwise $RP=co-RP$). – Cauthon Aug 28 '15 at 11:14
  • @Cauthon; if this doesn't work, then $L\not\in RP^{RP}$, so the article is wrong. – JMP Aug 28 '15 at 11:15