Question

LetM be a probabilistic polynomial time Turning machine, and let C be a language where for some fixed$\mathbf{0}\mathbf{<}{\in }_1<{\in }_2\mathbf{<}\mathbf{1}$,

1. localid="1657794094101" $\mathit{w}\notin \mathit{C}$implies Pr[ M accepts w], localid="1657794117156" $\le {\in }_1$and
2. localid="1657794100896" $\mathit{w}\notin \mathit{C}$implies Pr[ M accepts w] localid="1657794105827" $\le {\in }_2$.
3. Show that localid="1657794108596" $\mathbf{C}\in \mathbf{BPP}$.(Hint: Use the result of Lemma 10.5)

Short answer

By the weak law of large numbers (or various other bounds from probability theory), there exist k that will make those probabilities on the right as small as desired, and in particular, there exist k that will make them both strictly less than $\frac{\mathbf{1}}{\mathbf{2}}$ and by using “Amplification lemma” this shows $\mathbf{C}\mathbf{\in }\mathbf{BPP}$.

Step-by-step solution

Understanding the given problem

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

1. $\mathit{w}\notin \mathit{C}$implies Pr[ M accepts w] $\mathbf{\le }{\mathbf{\in }}_{\mathbf{1}}$,
2. $\mathit{w}\notin \mathit{C}$implies Pr[ M accepts w] $\mathbf{\le }{\mathbf{\in }}_{\mathbf{2}}$.

To show C∈BPP

• Between any two distinct real numbers $\mathbf{<}{\mathbf{\in }}_{\mathbf{1}}\mathbf{<}{\mathbf{\in }}_{\mathbf{2}}$, there exists another real number that lies strictly between them. Thus, choose c such that$\mathbf{<}{\mathbf{\in }}_{\mathbf{1}}\mathbf{<}{\mathbf{\in }}_{\mathbf{2}}$
• Consider another machine S which repeatedly runs M. Now S accepts if the proportion of M’s acceptance is greater than or equal to c, and S rejects if the proportion of M’s 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}\in \mathbf{C}\mathbf{,}{\mathbf{S}}_{\mathbf{k}}$is the sum of$\mathbf{k}\mathbf{0}\mathbf{-}\mathbf{1}$ random variables with common mean $\mathbf{\mu }\mathbf{>}{\mathbf{\in }}_{\mathbf{2}}$, and for $\mathbf{w}\in \mathbf{C}\mathbf{,}{\mathbf{S}}_{\mathbf{k}}$, is the sum of $\mathbf{k}\mathbf{0}\mathbf{-}\mathbf{1}$random variables with common mean $\mathbf{\mu }\mathbf{>}{\mathbf{\in }}_{\mathbf{1}}$.

Expressing the Error Probabilities

1. For $\mathbf{w}\in \mathbf{C}\mathbf{,}\mathbf{Pr}$[S rejects w]=localid="1657793586246" $\mathbf{Pr}\mathbf{[}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{<}\mathbf{c}\mathbf{]}\le \mathbf{Pr}\mathbf{|}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{-}{\mathbf{\mu }}_{\mathbf{2}}\mathbf{|}\mathbf{>}{\mathbf{\mu }}_{\mathbf{2}}\mathbf{-}\mathbf{c}\mathbf{]}$
2. For $\mathbf{w}\in \mathbf{C}\mathbf{,}\mathbf{Pr}$[S accepts w]= localid="1657794124662" $\mathbf{Pr}\mathbf{[}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{\ge }\mathbf{c}\mathbf{]}\le \mathbf{Pr}\mathbf{|}\frac{{\mathbf{S}}_{\mathbf{k}}}{\mathbf{k}}\mathbf{-}{\mathbf{\mu }}_{\mathbf{1}}\mathbf{|}\mathbf{\ge }\mathbf{c}\mathbf{-}{\mathbf{\mu }}_{\mathbf{1}}\mathbf{]}$

• By using “Amplification lemma” this shows $\mathbf{C}\mathbf{\in }\mathbf{BPP}$.