# Definition of BPP

We know that BPP is described as $$\{L\mid \exists \text{ TM }M, \text{ s.t. }\Pr[M(x)=L(x)]\geq2/3\}$$. I saw a proof which uses Chernoff bound to prove that any probability larger than $$1/2$$ can be turned to any probability in $$(1/2,1)$$. My question is what about probabilities below $$1/2$$. Do they fall on a different class?

Let $$\mathsf{BPP}_p$$ be the class of languages $$L$$ such that some polytime Turing machine satisfies $$\Pr[M(x) = L(x)] \geq p$$ for all $$x$$. For any fixed $$p \in (1/2,1)$$, we have $$\mathsf{BPP}_p = \mathsf{BPP}$$. On the other hand:
• $$\mathsf{BPP}_1 = \mathsf{P}$$.
• If $$p \leq 1/2$$ then $$\mathsf{BPP}_p$$ consists of all languages. This is because the machine $$M$$ which flips an unbiased coin satisfies $$\Pr[M(x) = L(x)] = 1/2 \geq p$$ for all $$x$$.
• I did not get your last point. How $\Pr[M(x) = L(x)] = 1/2 \geq p$ for all $x$ applicable for all other language? How every language is coming in that category? – roydiptajit Nov 8 '20 at 12:31
• I described a machine $M$ with this property. – Yuval Filmus Nov 8 '20 at 14:26
• If $L$ has a deterministic algorithm, then how a probabilistic TM, $M$ decides $L$? – roydiptajit Nov 8 '20 at 15:21
• Ok, I get it. Now Suppose we have $L$, s.t. $\exists M$, $Pr[M(x)=L(x)]=p$, $p\leq 1/2$. Now we can construct $TM$ $M'$, s.t. it repeats $M$. By this we get a probability amplification. Now, if $p>1/2$, after amplifying, does that comes under BPP? So $L\in BPP$? – roydiptajit Nov 8 '20 at 16:44