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

^ ^A ^b Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .
^ Richard Beigel, Nick Reingold, Daniel Spielman: PP is closed under intersection . In: STOC '91 . ACM, 1991, pp. 1-9 , doi : 10.1145 / 103418.103426 .
^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 199 .
^ 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]).

Web links

PP . In: Complexity Zoo. (English)

[BoCr195-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 .

[BRS91-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 .

[BoCr199-3] Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 199 .

[ADH97-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]).