How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $
Can any body explain this to me in simple terms.
Any help on this is highly appreciated. 
 A: The key idea is that because the probability of error is less than one half you can decrease that probability further by repeatedly running the algorithm a polynomial number of times and accepting the majority result.  For example, using the standard definition of $BPP$ which has a 1/3 probability of error, if you wanted a 99% probability of getting a correct answer, you would need to run the algorithm enough times that the probability of getting a majority wrong answer is less than 1%.  For n runs the probability of a majority of runs producing  the wrong answer is $1 / 3^{(n/2)+1}$.  Solving for $n$:
$$
\begin{align*} 
\frac{1}{3^{(n/2)+1}} &< \frac{1}{100} \\
3^{(n/2)+1} &> 100 \\
\frac{n}{2}+1 &> log_3 100 \\
\frac{n}{2} &> (log_3 100) - 1 \\
n &> 2(log_3 100 - 1) \\
n &> 2(4.19 - 1) \\
n &> 6.38 \\
\end{align*}
$$
So 7 runs should produce a majority correct answer with 99% certainty.  As the overall formula indicates, you can always do this sort of amplification with a number of runs that has a logarithmic relationship to the degree of certainty required.
