Probabilistic polynomial-time

The class of decision problems solvable by a probabilistic polynomial-time Turing machine that accepts with probability greater than 1/2 on “yes” inputs and at most 1/2 on “no” inputs (a majority-vote criterion). Unlike BPP, the gap between acceptance probabilities on “yes” and “no” instances can be as small as $2^{-\mathrm{poly}(n)}$, so the error cannot be amplified by repetition.

See the complexity zoo entry here.

Known relationships

• $\mathbf{BPP}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$: BPP has a constant gap (and thus sits inside PP), and PP’s computation can be simulated in polynomial space.
• $\mathbf{NP}\subseteq \mathbf{PP}$: given an NP machine, accept iff strictly more than half the nondeterministic paths lead to accepting, which is a PP criterion.
• $\mathbf{BQP}\subseteq \mathbf{PP}$: quantum polynomial-time is contained in PP — TODO citation (Adleman, DeMarrais, Huang 1997). This is the key relationship placing quantum computing within classical complexity.
• Toda’s theorem: $\mathbf{PH}\subseteq {\mathbf{P}}^{\#P}$, the polynomial hierarchy is contained in polynomial time with a $\#P$ oracle — TODO citation (Toda 1991). Since $\#P\subseteq {\text{classFP}}^{\mathbf{PP}}$, this also implies $\mathbf{PH}\subseteq {\mathbf{P}}^{\mathbf{PP}}$.
• PP is closed under complement, union, and intersection — TODO citation (Beigel, Reingold, Spielman 1995).