This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in $RP$ allowed to consult an oracle in $RP$, prove the "lowest complexity bound" for a set recognized by this algorithm.

I don't think this is a very good question, it's not clear exactly what is meant by lowest complexity bound. I suppose this means any set in this class ($RP^{RP}$) must fall in which complexity class..that is, find the lowest such one and prove it.

Any ideas?

  • 2
    $\begingroup$ Treat it like a research question – what can you say about $RP^{RP}$? One guess, for example, would be that $RP^{RP}$ can be simulated by $RP$ itself or by $BPP$. $\endgroup$ – Yuval Filmus Mar 5 '15 at 22:58

Hint: For BPP it is the case that $BPP^{BPP} = BPP$. The idea is that given a machine in $BPP^{BPP}$, we simulate each oracle call by a BPP computation, amplified so that the error probability is very small. Since there are only polynomially many oracle calls, overall the error coming from miscalculating the BPP oracle calls is small, and the resulting machine still has bounded error. (For a more complete proof, use your web search skills.) Try to emulate this line of reasoning for RP.

  • $\begingroup$ Thanks, so it's clear from what you wrote that $RP^{RP} \subset BPP$..I tried to show that it equals $RP$ but it doesn't seem possible since the error in the simulation of the oracle machines might cause an incorrect accept, which isn't allowed in $RP$. $\endgroup$ – Kuhndog Mar 6 '15 at 2:19
  • $\begingroup$ Also, since it's an open question whether $RP = BPP$, I guess I couldn't show an example where an element of $RP^{RP}$ is in $BPP$ but not $RP$. $\endgroup$ – Kuhndog Mar 6 '15 at 2:27

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.