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.
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 .
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)