# Prove that $coRP \subseteq RP^{RP}$

I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$.

If $L \in coRP$, 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.

• Well, $RP^{\hspace{.03 in}RP}\hspace{-0.02 in}$ can be replaced with $P^{\hspace{.03 in}RP}\hspace{-0.02 in}$. $\;$ – user12859 Aug 28 '15 at 11:37

Suppose $L \in \mathsf{coRP}$, so that $\overline{L} \in \mathsf{RP}$. Using an oracle to $\mathsf{RP}$ we can determine whether a given string $x$ is in $\overline{L}$, and so whether $x \in L$. This gives a $\mathsf{P}^{\mathsf{RP}}$ algorithm for $L$.
• We know that $L \in coRP$ and equivalently $\overline{L} \in RP$. This means that for the suitable Turing machine $M$, if $x \in L$, then $Pr[M(x)=1]=1$ and if $x \notin L$, then $Pr[M(x)=0] \ge 0.5$. So as you say, we can determing whether $x \in L$ with the above probabilities. But those are not the $RP$ probabilties for $L$, but the opposite. What am I missing? – Cauthon Aug 28 '15 at 11:47
• Unless we accept the oracle's answer as always correct (i.e. if $L \in RP$ and we have an oracle for $L$, then the answers we get are no longer probabilistic, but 100%)? – Cauthon Aug 28 '15 at 11:56