I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain:

By the definition of PP there is a polynomial-time probabilistic algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr} [A(x) = 1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.

Let $f(|x|)$ be the polynomial upper bound on the running time of A on input x. Thus A makes at most $f(|x|)$ random coin flips during its execution. In particular, $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.

I understand that:

  • By definition of PP, ${x\in L\Rightarrow \mathrm {Pr} [A(x) = 1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
  • The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.

But why is it so obvious that $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?

That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?


1 Answer 1


$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that you accept can't be exactly 0.501. It's either 0 (you never accept), 1/4 (one coin flip combination leads to acceptance), 1/2 (two combinations make you accept), 3/4 or 1.

So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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