形式陈述

语言 $L$ 属于 $\mathbf{PP}$，若存在概率多项式时间机器 $M$，使对每个输入 $x$，

$$x\in L⟺\text{Pr}[M(x)\text{ 接受}]>\frac{1}{2}.$$

等价地，可令 $M$ 在多项式条随机位上分支，并要求属于 $L$ 的输入拥有严格多于一半的接受计算路径；不属于 $L$ 时，接受概率至多为 $1/2$。

直觉

PP 用全部随机计算路径的多数票判定答案。它只关心接受概率位于 $1/2$ 的哪一侧，不承诺与阈值之间存在常数间隔。

例子与边界

MAJSAT 问一个 Boolean 公式是否被严格多于一半的赋值满足，是典型的 PP 完全问题。概率恰为 $1/2$ 时按上述约定判为否。PP 不是 BPP：PP 的优势可以小到指数级，通常的多项式次重复不能把它放大成常数误差界；这里的 PP 也与“伪多项式时间”无关。

推论与应用

$\mathbf{P}\subseteq \mathbf{BPP}\subseteq \mathbf{PP}$，且 $\mathbf{NP}\subseteq \mathbf{PP}$。PP 为计数问题、量子复杂度上界和随机复杂度类包含关系提供多数接受基线。

参考资料

• John Gill, “Computational Complexity of Probabilistic Turing Machines,” SIAM Journal on Computing 6(4), 1977，pp. 675–695。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 7。