PP (complexity) - PP Vs BPP

PP Vs BPP

BPP is a subset of PP; it can be seen as the subset for which there are efficient probabilistic algorithms. The distinction is in the error probability that is allowed: in BPP, an algorithm must give correct answer (YES or NO) with probability exceeding some fixed constant c greater than 1/2, such as 2/3 or 501/1000. If this is the case, then we can run the algorithm a polynomial number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. This number of repeats increases if c becomes closer to 1/2, but it does not depend on the input size n.

The important thing is that this constant c is not allowed to depend on the input. On the other hand, a PP algorithm is permitted to do something like the following:

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

Because these two probabilities are so close together, especially for large n, even if we run it a large number of times it is very difficult to tell whether we are operating on a YES instance or a NO instance. Attempting to achieve a fixed desired probability level using a majority vote and the Chernoff bound requires a number of repetitions that is exponential in n.