1
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Cauthon Aug 28 '15 at 11:47
  • $\begingroup$ 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%)? $\endgroup$ – Cauthon Aug 28 '15 at 11:56
  • $\begingroup$ @Cauthon You are missing the definition of oracle Turing machine. The oracle is always correct, by definition. $\endgroup$ – Yuval Filmus Aug 28 '15 at 12:40
  • $\begingroup$ Yes, I suspected that was the case after reading your answer. Stupid mistake, thanks for the clarification! $\endgroup$ – Cauthon Aug 28 '15 at 12:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.