A clarification on $PP$

Question

Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following:

On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is the length of the input. On a NO instance, output YES with probability $1/2 - 1/2^n$."

Can we replace $2^n$ by something larger like $2^{n^{1+\epsilon}}$ or $2^{2^n}$? It seems that this case should be already known to be distinct from $BPP$.

Answer 1

First, let me change your definition of PP a little bit:

On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$

On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$

Here, I replaced the error term with $\epsilon(n)$ and added $\geq$ and $\leq$. If we don't include $\leq$ and $\geq$, then problems in $BPP$ would not fall under our definition of $PP$.

You can replace the error with any small $\epsilon(n)>0$ you want, but you are not accomplishing anything by going past $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$.

Realistically, we do not need an error term smaller than $\epsilon(n)^{-1} = 2^n$ because you can amplify the error by a polynomial amount to get $2^{poly(n)}$ (since we are a polynomial time machine).

We unfortunately can't amplify beyond this, but that turns out not to matter. There does not exist a probabilistic polynomial time Turing machine that can accept or reject with error probability $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$. A probabilistic polynomial time Turing machine does not have a large enough number of configurations to accept or reject with such a fine grained/detailed error.

To see what I mean, think about how you would design a PPTM that outputs YES with probability just $1/2^{2^n}$. The best you could do is use almost all of your runtime to generate $poly(n)$ random bits and accept if they are all $0$'s. The probability of this happening is bounded by $1/O(2^{poly(n)})$.