Prove that $co-RP \subseteq RP^{RP}$

55 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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.