# Can BPP be bounded around any constant other than 1/2?

A language $$L$$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $$1/2+1/p(n)$$ for some polynomial $$p(n)$$, where $$n$$ is the length of the input. This probability can be amplified to $$1-2^{q(n)}$$, for some polynomial $$q(n)$$ by repeating the algorithm polynomially many times and taking the majority.

I was wondering if it is necessary to have this bound around the constant $$1/2$$? Can we have a randomised algorithm that answers correctly with probability $$c+1/p(n)$$ for some $$c<1/2$$ and still amplify the probability in polynomial time?

The proof for the case of $$1/2 + 1/p(n)$$ uses Chernoff bound on lower tail that requires $$0 < \delta <1$$. $$\delta= 1-1/2p$$ in that case which means $$p$$ should be greater than $$1/2$$. Proof here.

However here is a proof that weak BPP = Strong BPP where strong BPP is BPP as we know it and weak BPP is when if $$x\in L,$$ $$P(TM\ accepts\ x) \geq s(n)+1/p(n)$$, and if $$x \not\in L, P(TM\ accepts\ x ) \leq s(n)$$, where $$p(n)$$ is any polynomial and $$s(n)$$ is any polynomial time computable function.

• Doesn't the proof that weak BPP = strong BPP already answer your question? After all, $s(n) = c$ is polynomial-time computable... (unless $c$ is irrational, of course, in which case you could always take some approximation thereof). – dkaeae Jun 13 at 7:24
• For any $c < 1/2$ and any problem, there is a probabilistic algorithm that gives the correct answer with probability at least $c + 1/p(n)$, namely the one that (for large enough $n$) just tosses a random coin. – Yuval Filmus Jun 13 at 7:27
• @YuvalFilmus then how is weak BPP = strong BPP ? should there be a restriction on $s(n)$? – emmy Jun 13 at 16:08
• The promise might be different. – Yuval Filmus Jun 13 at 16:11

## 1 Answer

If $$c < 1/2$$ then for any problem there is an algorithm that answers correctly with probability at least $$c+1/n$$, say. For small $$n$$, the algorithm just outputs the hardwired correct answer. When $$n$$ is large enough so that $$c + 1/n \leq 1/2$$, the algorithm just tosses a coin.

What went wrong? For BPP amplification to work, we need a gap between the promise for a Yes instance and the promise for a No instance. In your definition of "weak BPP" (not a standard term), you are given an algorithm such that:

• On a Yes instance, accepts with probability at least $$s(n) + 1/p(n)$$.
• On a No instance, accepts with probability at most $$s(n)$$.

In contrast, in your suggested definition, we have the following promise:

• On a Yes instance, accepts with probability at least $$c + 1/p(n)$$.
• On a No instance, accepts with probability at most $$1 - c - 1/p(n)$$.

If $$c < 1/2$$ then for large enough $$n$$, the two acceptance intervals overlap (at acceptance probability $$1/2$$), and so the definition is meaningless. When $$c = 1/2$$, there is an inverse polynomial gap, which can be amplified to a constant gap, to match the standard definition of BPP.