复杂度类 PP

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

MAJSAT 问一个 Boolean 公式是否被严格多于一半的赋值满足，是典型的 PP 完全问题。若公式有 $n$ 个变量和 $s$ 个满足赋值，随机选择一个赋值并检查公式，接受概率就是 $s/2^n$；严格多数的计数条件直接对应 PP 的概率阈值。

一般阈值 $s>t$ 也可这样编码，其中 $t$ 为满足 $0\le t\le 2^n$ 的整数。先抛一枚公平硬币：一面执行上述公式检查，另一面均匀选取整数 $z\in \{0,\dots ,2^n-1\}$，当 $z<2^n-t$ 时接受。总接受概率为

第二条分支提供了可精确计算的偏移，使任意给定阈值都落到严格多数比较上。

PP 的概率条件针对每个固定输入上的内部随机性。它与 BPP 的定义差别在于是否要求常数概率间隔；已知 $\mathbf{BPP}\subseteq \mathbf{PP}$，是否相等仍未知。

基本包含关系为 $\mathbf{P}\subseteq \mathbf{BPP}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$，并且 $\mathbf{NP}\subseteq \mathbf{PP}$。其中 BPP理路复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。 提供可靠的随机判定，PP 则给计数阈值判定提供多数接受模型。

#P理路计数复杂性类 #PSharp-P · #P可高效验证的见证计数类；由前缀计数构造均匀生成器，并给出近似计数到近均匀采样的完整误差预算。 函数计算接受路径数，比较这类计数可刻画 PP。Toda 定理进一步说明，带 #P 预言机的多项式时间足以覆盖整个多项式层级理路多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。，把路径计数与量词交替联系起来。

Toda 定理理路Toda 定理Toda's theorem · PH in P with a counting oracle用哈希隔离消去固定层量词，再把奇偶计数提升到高次二的模数，完整推出 PH 包含于带精确计数 oracle 的多项式时间。逐步说明 $PH\subseteq P^{\mathrm{\#}P}=P^{PP}$ 的 oracle 口径：阈值查询可二分恢复多项式位长的精确计数，而精确计数可回答阈值。不能据此删除外面的 P，把它改写成 $PH\subseteq PP$。