复杂度类 BPP

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

设 $X_i$ 是第 $i$ 次运行出错的指示变量，则 $\mathbb{E}{X}_i\le 1/3$。多数失败要求 $\sum X_i\ge k/2$，比均值至少高 $k/6$；Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。给出概率至多 $e^{-k/18}$。对整数 $n\ge 2$ 与固定 $c>0$，选择足够大的奇数 $k\ge 18c\ln n$ 即得错误至多 $n^{-c}$。每次运行都受 $p(n)$ 限制，总时间为 $O(kp(n))$；这里连最坏随机串上的时间也受控制，并非只证明期望运行快。若接受概率仅为 $1/2+2^{-n}$，多项式次样本无法稳定分辨。这足以通过PP理路复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。 的严格多数门槛，却不满足 BPP 算法所需的可放大间隙；同一个语言是否另有 BPP 算法仍须单独判断。

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

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

随机通信、查询与性质测试也沿用有界错误语言，但不因此成为 BPP 的同义模型。随机通信复杂度理路随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。把双方本地计算视为免费而计算交换 bit；随机查询复杂度理路确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity以决策树和量词定义确定性、允许错误与零错误查询成本，用 OR、奇偶与带间隔多数解释随机化的作用。计算 oracle 访问，可能允许远超多项式的本地处理；性质测试理路性质测试模型Property testing model · Property testing明确 oracle、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。只保证成员与 $\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以每个固定输入上的期望时间和零错误保证定义，并通过截断重启证明 ZPP 等于 RP 与 coRP 的交。也包含于 BPP，BPP 对补封闭且位于PP理路复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。和多项式层级内。

随机性是否真正扩展多项式时间能力仍未知。短种子枚举理路伪随机种子枚举与 BPP 去随机化PRG-based derandomization把固定输入下的随机带判决视为有限规模电路，枚举能欺骗它的对数种子并验证接受概率间隙，分别计算种长、安全资源与生成器求值时间。要求种长对算法电路规模为对数、生成器能高效求值，且伪随机保证覆盖该规模的测试。NW 构造理路Nisan–Wigderson 生成器Nisan–Wigderson generator · NW generator以小交集设计复用种子位，通过下一位预测与固定外部坐标重建困难函数，逐项核算交集真值表造成的电路规模损失。用小交集设计复用困难函数的输入，再把区分器重建成预测该函数的小电路。

IW 定理理路Impagliazzo–Wigderson 困难性—随机性定理Impagliazzo–Wigderson theorem在E中存在逐充分大长度的指数非一致电路下界这一明确假设下，经局部列表译码式困难性放大、NW设计和种子枚举推出P=BPP，并逐项对齐参数。给出一个明确的充分条件：若单指数时间类 E 中存在在所有充分大长度都需要指数规模电路的语言，则经困难性放大与上述构造可得 P=BPP。这里必须保留困难性和资源条件，普通密码学 PRG 的存在本身不会自动提供所需的对数种长保证。