Cheap and Secure Web Hosting Provider : See Now

# Complexity bound on \$RP^{RP}\$

, ,
Problem Detail:

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?

###### Answered By : Yuval Filmus

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.