91影视

Given M be probabilistic polynomial time Turning machine, and C be a language where for some fixed ,

1. $\mathit{w}鈭�\mathit{C}$implies Pr[ M accepts w] $\mathbf{鈮�}{\mathbf{鈭�}}_{\mathbf{1}}$,
2. $\mathit{w}鈭�\mathit{C}$implies Pr[ M accepts w] $\mathbf{鈮�}{\mathbf{鈭�}}_{\mathbf{2}}$.

• Between any two distinct real numbers $\mathbf{<}{\mathbf{鈭�}}_{\mathbf{1}}\mathbf{<}{\mathbf{鈭�}}_{\mathbf{2}}$, there exists another real number that lies strictly between them. Thus, choose c such that$\mathbf{<}{\mathbf{鈭�}}_{\mathbf{1}}\mathbf{<}{\mathbf{鈭�}}_{\mathbf{2}}$
• Consider another machine S which repeatedly runs M. Now S accepts if the proportion of M鈥檚 acceptance is greater than or equal to c, and S rejects if the proportion of M鈥檚 acceptance is less than c.
• To show S decides in BPP, Consider the variable ${\mathbf{S}}_{\mathbf{k}}$be the total number of acceptances by machine M after k runs on input w. Hence for $\mathbf{w}鈭�\mathbf{C}\mathbf{,}{\mathbf{S}}_{\mathbf{k}}$is the sum of$\mathbf{k}\mathbf{0}\mathbf{-}\mathbf{1}$ random variables with common mean $\mathbf{渭}\mathbf{>}{\mathbf{鈭�}}_{\mathbf{2}}$, and for $\mathbf{w}鈭�\mathbf{C}\mathbf{,}{\mathbf{S}}_{\mathbf{k}}$, is the sum of $\mathbf{k}\mathbf{0}\mathbf{-}\mathbf{1}$random variables with common mean $\mathbf{渭}\mathbf{>}{\mathbf{鈭�}}_{\mathbf{1}}$.

1. For $\mathbf{w}鈭�\mathbf{C}\mathbf{,}\mathbf{Pr}$[S rejects w]=localid="1657793586246" $\mathbf{Pr}\mathbf{[}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{<}\mathbf{c}\mathbf{]}鈮�\mathbf{Pr}\mathbf{|}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{-}{\mathbf{渭}}_{\mathbf{2}}\mathbf{|}\mathbf{>}{\mathbf{渭}}_{\mathbf{2}}\mathbf{-}\mathbf{c}\mathbf{]}$
2. For $\mathbf{w}鈭�\mathbf{C}\mathbf{,}\mathbf{Pr}$[S accepts w]= localid="1657794124662" $\mathbf{Pr}\mathbf{[}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{鈮�}\mathbf{c}\mathbf{]}鈮�\mathbf{Pr}\mathbf{|}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{-}{\mathbf{渭}}_{\mathbf{1}}\mathbf{|}\mathbf{鈮�}\mathbf{c}\mathbf{-}{\mathbf{渭}}_{\mathbf{1}}\mathbf{]}$

• By using 鈥淎mplification lemma鈥� this shows $\mathbf{C}\mathbf{鈭�}\mathbf{BPP}$.