# Probabilistic polynomial time

In complexity theory , PP is the class of decisions that can be solved by a probabilistic Turing machine in polynomial time and that the answer is correct in at least half of the cases. The abbreviation PP stands for Probabilistic Polynomial Time.

## properties

PP is completed under complement formation, union and cut. That means that for two languages too . So it is co-PP = PP. ${\ displaystyle L_ {1}, L_ {2} \ in {\ mathcal {PP}}}$${\ displaystyle L_ {1} ^ {c}, L_ {1} \ cup L_ {2}, L_ {1} \ cap L_ {2} \ in {\ mathcal {PP}}}$

A well-known PP-complete problem is MAXSAT, the decision problem whether a propositional formula is fulfilled by more than half of all possible assignments .

## Relationship to other complexity classes

PP contains BQP and thus also BPP . PP also contains NP co-NP and is itself contained in PSPACE . ${\ displaystyle \ cup}$

## Individual evidence

1. ^ A b Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .
2. ^ Richard Beigel, Nick Reingold, Daniel Spielman: PP is closed under intersection . In: STOC '91 . ACM, 1991, pp. 1-9 , doi : 10.1145 / 103418.103426 .
3. ^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 199 .
4. ^ Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability . In: SIAM Journal on Computing . tape 26 , no. 5 . SIAM , 1997, p. 1524-1540 ( psu.edu [PDF]).