Prove that $BPP^{BPP} = BPP$.

Obviously $BPP\subseteq BPP^{BPP}$. So we're left with proving $BPP^{BPP} \subseteq BPP$. Let's consider $L\in BPP^{BPP}$. Then, there's a PTM $M$ to decide $L$ for some $BPP(\alpha, \beta)$ which uses an oracle for some language $O\in BPP$. $O$ also has a $PTM\in BPP$, let's denote it $M_o$. So we could create $M'$, a PTM which behaves exactly as $M$, but everytime $M$ uses the oracle, it simulate $M_o$ on the given input for the oracle.

Now, I want to show that $M\in BPP$. By definition, $BPP=BPP(1/3, 1/3)$, so every time $M$ calls $M_o$ it takes a probabilistic risk basing a deciion upon $M_o$ answer.

We've learned in class that $BPP = BPP(1/3, 1,3) = BPP\left(\frac{1}{3^n}, \frac{1}{3^n} \right)$ and I think I shall explain that even though $M_o$ may return false answers, $M_o$ is still in $BPP$.

Can you help me with doing that?


Basically, I want to give a lower bound for the probability of $M$, answering correctly. Let's assume that $M$ queries the oracle $n^c$ times for some $n\in\mathbb{N}$. I think the lower bound is $\frac{1}{3^{n^c}}$.

My explanation is that we're assuming the worst case. That is, if the oracle is returning a false answer then we are returning a false answer.

Is that right?

I'm not sure it's $100\%$ correct, since I didn't take into account the probabilistic behavior of $M$ itself.


Here's a sketch: you seem to be on the right track. Let $L\in BPP^{BPP}$ be decided by a BPP machine $M$ that makes queries to an oracle $A\in BPP$ decided by a $BPP$ machine $M'$. Let $E$ be the error for $M$, $E'$ the error for $M'$ (that is, the probability that the BPP machines fail is at most $E, E'$). We will choose $E, E'$ appropriately via error reduction.

Now, fix a string $z$ to use as randomness for all queries to $M'$. There are at most polynomially many queries to $M'$, say at most $|x|^k$, since $M$ is a ppt TM. Thus, $$\operatorname{Pr}[\text{an error occurs in some query to } M']\le |x|^k\cdot E'$$ So the overall probability of error by $M$ in deciding $L$ is at most $|x|^k\cdot E' + E$, so if we choose $E=\frac{1}{6}$ and $E'=\frac{1}{6|x|^k}$ (which we may do by the standard BPP error reduction), we get an overall probability of error $\le\frac{1}{3}$, so the procedure described is a $BPP^P\subseteq BPP$ procedure.

By the same proof we have the more general statement that $BPP^{BPP^A}\subseteq BPP^A$.

  • $\begingroup$ but aren't the errors coupled with each other? I mean, $E$ is dependent on $E'$ $\endgroup$ – Covvar Jun 4 '17 at 10:00
  • $\begingroup$ i.e. an error of $M'$ could lead to a correct answer of $M$ $\endgroup$ – Covvar Jun 4 '17 at 10:00

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.