PP (complexity)

PP algorithm
Answer
produced
Correct
answer
 Yes No
Yes > 1/2 < 1/2
No < 1/2 > 1/2


Diagram of randomised complexity classes
PP in relation to other probabilistic complexity classes (ZPP, RP, co-RP, BPP, BQP), which generalise P within PSPACE. It is unknown if any of these inclusions are strict.

In complexity theory, PP 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 for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less 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]

  1. ^ Gill, John (1977). "Computational Complexity of Probabilistic Turing Machines". SIAM Journal on Computing. 6 (4): 675–695. doi:10.1137/0206049.
  2. ^ Lindell, Yehuda; Katz, Jonathan (2015). Introduction to Modern Cryptography (2 ed.). Chapman and Hall/CRC. p. 46. ISBN 978-1-4665-7027-6.
  3. ^ Lance Fortnow. Computational Complexity: Wednesday, September 4, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html