复杂度类 BPP

BPP 算法每次可能答错，但在每个固定输入上，正确答案的概率都以一个常数间隙高于错误答案，因而在随机运行中形成稳定多数。这个间隙使独立重复与多数投票能把固定可靠性放大为极高置信度，而不是因为“随机算法平均起来总会正确”。双边误差允许是实例和否实例都偶尔答错，但保证必须对最坏输入成立。

若单次正确率为 $2/3$，独立运行 $k$ 次取多数，Chernoff 方法把“多数失败”写成独立 Bernoulli 和偏离均值的尾事件，给出错误概率 $e^{-\mathrm{\Omega }(k)}$；取 $k=O(\log n)$ 即可把错误压到 $1/n^c$，仍保持多项式时间。若成功率仅为 $1/2+2^{-n}$，多项式次样本无法稳定分辨，这不满足通常 BPP 的可放大间隙。

算法在某个输入分布下平均准确不够；BPP 对每个输入的内部随机位取概率，并要求随机位数和运行时间都由输入长度的多项式界定。重复运行若复用高度相关的随机性，也不能直接套独立多数分析。

随机学习器也可能以概率至少 $1-\delta$ 输出低风险预测器，但这不使它自动成为 BPP 算法。高效学习公理库高效 PAC 学习Efficient PAC learning在 PAC 统计保证之外，要求样本处理、运行时间与输出评价均为多项式。的输入包含样本或样本 oracle，输出是预测器而非一个可立即核对的 bit；“风险是否不超过阈值”往往依赖未知分布，未必能像判定答案那样直接多数表决。两者的失败概率都可研究放大，问题类型、量词与聚合规则却不同。

随机通信、查询与性质测试也沿用有界错误语言，但不因此成为 BPP 的同义模型。随机通信复杂度公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。把双方本地计算视为免费而计算交换 bit；随机查询复杂度公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。计算 oracle 访问，可能允许远超多项式的本地处理；性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。只保证成员与 $\epsilon$-far 两端，gap 内没有正确性要求。BPP 则对完整显式输入的每个实例要求多项式总时间和判定正确率。比较这些结论时，必须同时对齐输入可见性、资源单位、最坏输入量词和错误区域。

概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。说明阈值 $2/3,1/3$ 不是本质常数。包含关系上，$\mathrm{P}\subseteq \mathrm{RP}\subseteq \mathrm{BPP}$，ZPP公理库复杂性类 ZPPZero-error probabilistic polynomial time · ZPP可由零错误、期望多项式时间随机算法判定的语言类。也包含于 BPP，BPP 对补封闭且位于PP公理库复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。和多项式层级内。随机性是否真正扩展多项式时间能力仍未知；伪随机生成器研究试图把所需随机位替换为可枚举种子，并在适当困难性假设下去随机化到 P。