PP (complexity)

In complexity theory PP is the class of the decisions in polynomial time solvable in a probabilistic Turing machine, and the answer is right in at least half of the cases. The abbreviation stands for Probabilistic polynomial time PP.

Properties

PP is closed under complementation, union and intersection. This means that for two languages ​​as well. It is co -PP = PP.

A well-known PP -complete problem is MAJSAT, the decision problem whether a propositional formula is satisfied by more than half of all possible allocations.

Relation to other complexity classes

PP contains BQP and hence BPP. PP also contains NP and co-NP is self- contained in PSPACE.