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$.
  • $\begingroup$ 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? $\endgroup$ – roydiptajit Nov 8 '20 at 12:31
  • $\begingroup$ I described a machine $M$ with this property. $\endgroup$ – Yuval Filmus Nov 8 '20 at 14:26
  • $\begingroup$ If $L$ has a deterministic algorithm, then how a probabilistic TM, $M$ decides $L$? $\endgroup$ – roydiptajit Nov 8 '20 at 15:21
  • $\begingroup$ Every deterministic algorithm can be viewed as a probabilistic algorithm which uses no randomness. $\endgroup$ – Yuval Filmus Nov 8 '20 at 15:39
  • $\begingroup$ 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$? $\endgroup$ – roydiptajit Nov 8 '20 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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