World's most popular travel blog for travel bloggers.

Complexity bound on $RP^{RP}$

, , No Comments
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?

Asked By : Kuhndog
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback