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}$: flip a coin; on heads accept, on tails sample a uniform candidate witness $w\in \{0,1{\}}^m$ and accept iff the NP verifier accepts $w$. The acceptance probability $1/2+a/2^{m+1}$, with $a$ the number of accepting witnesses, exceeds $1/2$ exactly on “yes” inputs — Gil77.
• $\mathbf{BQP}\subseteq \mathbf{PP}$: quantum polynomial-time is contained in PP — ADH97; see bqp-to-pp. 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 — Tod91. Since $\#P\subseteq {\mathbf{FP}}^{\mathbf{PP}}$, this also implies $\mathbf{PH}\subseteq {\mathbf{P}}^{\mathbf{PP}}$.
• PP is closed under complement — folklore. PP is closed under union and intersection — BRS95.

Participates in

Builds on Probabilistic polynomial-time

• PP ⊆ PSPACE

Produces Probabilistic polynomial-time

• BPP ⊆ PP
• BQP ⊆ PP
• MA ⊆ PP
• NP ⊆ PP
• QMA ⊆ PP

Barriers

• No relativizing reduction from AM to PP