3
$\begingroup$

regarding the following post: Prove that $BPP^{BPP} = BPP$

Let $L\in BPP^{BPP}$, by definition $BPP^{BPP} =\bigcup_{O\in BPP}BPP^O $, therefore there exists a language $A\in BPP$ such that $L\in BPP^{A}$.
This means that there exists a $\mathsf{PTM} $ $M^{A}(x,r)$ such that $\mathbb{P}_{r}(M(x,r)\neq L(x))\leq \frac{1}{3}$, and $M^A$ runs in polinomial time.
In addition, since $A\in BPP_{[\frac{1}{3},\frac{2}{3}]} \subset BPP_{[2^{-n},1-2^{-n}]}$, there exists a $\mathsf{PTM} $ $M'(x,r)$ such that $\mathbb{P}_{r}(M'(x,r)\neq L(x))\leq 2^{-n}$, and $M'$ runs in polinomial time.
I defiened a $\mathsf{PTM}$ $N$, that on input $x$ does the following:
Simulate $M^A$ on $x$ and every time we need to do an orcale quarey $\alpha_i$, we would simulate $M'$ on $\alpha_i$ and the answer to the query would be the answer of $M'$.

I understand why $N$ runs in polynomial time, but I was stuck in the probabilistic analysis.
This is what I have so far:
If $x\in L$ then $N$ answer correctly iff $M^A$ answer correctly and $M'$ answer correctly about every query, therefore I got:
$\mathbb{P}_{r}(N(x,r)= 1)= \mathbb{P}_{r}(M(x,r)= 1)\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)\geq \frac{2}{3} \prod_{i}(1-\frac{1}{2^{|\alpha_i|}}) $

How can I prove from here that $\mathbb{P}_{r}(N(x,r)= 1) \geq \frac{2}{3}$?
Would appreciate your help:)

$\endgroup$
5
  • $\begingroup$ (1) Replace $|\alpha_i|$ with $n$, (2) use the union bound. $\endgroup$ Commented Dec 23, 2020 at 21:10
  • $\begingroup$ 1) Why can I say that $|\alpha_i| \geq n, \forall i$? I know that $|\alpha_i| =O(n^c)$ for some $c\in \mathbb{N}$, but do I know it's length is at least n? 2) Why can I use the union bound? $\forall i$ doesn't mean intersection? $\endgroup$
    – Emma
    Commented Dec 24, 2020 at 9:20
  • $\begingroup$ You cannot say it. But you don't have to say it. You can reduce the error probability to $2^{-n}$ even if $|\alpha_i|$ is small. $\endgroup$ Commented Dec 24, 2020 at 9:21
  • $\begingroup$ I'm not sure I fully understand why, can you please elaborate? And about the union bound- is it because $\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)=1- \mathbb{P}_{r}(\exists i, M'(\alpha_i,r)$is wrong$)\geq 1-\Sigma_{i}\mathbb{P}_{r}( M'(\alpha_i,r)$is wrong$)$? $\endgroup$
    – Emma
    Commented Dec 24, 2020 at 9:38
  • $\begingroup$ You have a BPP algorithm with error probability $1/3$. By repeating it polynomially many times, you can reduce the error probability to $2^{-n}$, say. Since you are making only polynomially many queries, the union bound shows that you will get an error in any of your BPP oracle calls is extremely small. $\endgroup$ Commented Dec 24, 2020 at 9:40

1 Answer 1

1
$\begingroup$

Your BPP algorithm makes polynomially many queries to the BPP oracle, and assuming that all these queries are answered correctly, has error probability at most $1/3$, say.

In order to simulate this algorithm without appealing to the oracle, we replace each oracle call with the BPP algorithm itself. By repeating the BPP algorithm polynomially many times, we can reduce the error probability of each oracle call to $2^{-n}$, say. The union bound then implies that all oracle calls are answered correctly with probability $1-o(1)$, and so the entire algorithm has error probability at most $1/3+o(1)$, which suffices to put the language in BPP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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