PP (complexity)

In complexity theory, PP, or PPT is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.^[1]

If a decision problem is in PP, then there is an algorithm running in polynomial time that is allowed to make random decisions, such that it returns the correct answer with chance higher than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times.

Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines.^[2] This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2.

An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority-P.^[3]