Editing PP (complexity) (section)

==PP vs BPP==
'''[[Bounded-error probabilistic polynomial|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 > 1/2, such as 2/3 or 501/1000. If this is the case, then we can run the algorithm a 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''.

More generally, if ''c'' can depend on the input size <math>n</math> polynomially, as <math>c = O(n^{-k}) </math>, then we can rerun the algorithm for <math>O(n^{2k})</math> and take the majority vote. By [[Hoeffding's inequality]], this gives us a '''BPP''' algorithm.

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&nbsp;+&nbsp;1/2<sup>''n''</sup>, where ''n'' is the length of the input.
* On a NO  instance, output YES with probability 1/2&nbsp;−&nbsp;1/2<sup>''n''</sup>.

Because these two probabilities are ''exponentially'' close together, even if we run it for a ''polynomial'' 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''.