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$.

  • 3
    $\begingroup$ Don't delete your own question after it has gotten an answer. That's impolite to answerers. It looks like you deleted your question one minute after receiving an answer -- that's not appropriate. Even if the question is no longer useful to you, that information might still be beneficial to others who may run into similar problems in the future -- this is the underlying philosophy of Stack Exchange. Thank you. $\endgroup$
    – D.W.
    Mar 20, 2016 at 3:41
  • $\begingroup$ @D.W. I thought my post was silly. $\endgroup$
    – user39969
    Mar 20, 2016 at 3:43

1 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)})$.


Your Answer

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