复杂度类 PP

PP 用全部随机计算路径的多数票判定答案，只关心接受概率位于 $1/2$ 的哪一侧，不承诺常数间隔。接受分支只需严格超过一半，偏差可以小到指数级，因此与 BPP 的常数概率间隙有本质区别，也不能靠多项式次重复稳定放大；哪怕接受概率是 $1/2+2^{-n}$ 也已满足定义。名称中的“概率多项式时间”容易误导：PP 更接近比较两类指数计数，而不是通常意义上的可靠随机算法。

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

令机器随机猜 $n$ 位赋值并接受满足公式者，再做适当偏移使“满足赋值数是否超过某阈值”对应接受概率是否大于 $1/2$，便得到典型 PP 判定。若某实例接受概率恰为 $1/2$，按标准严格阈值应判为否。

算法在某个输入分布下平均准确不够；PP 的阈值针对每个固定输入上的内部随机性。不同定义中使用 $>1/2$ 或 $\ge 1/2$ 时，需要用增加一条受控分支等小改造对齐边界情形。

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

#P公理库计数复杂性类 #PSharp-P · #P计数非确定性多项式时间机器接受分支数的函数类。 函数可用来比较接受与拒绝路径数，从而刻画 PP。它包含 BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。 和 NP，并位于 PSPACE 内；Toda 定理进一步显示带 #P 预言机的多项式时间足以覆盖整个 多项式层级公理库多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。。