形式陈述

语言 $L$ 属于 $\mathrm{BPP}$，若存在概率多项式时间算法 $A$，使对所有输入 $x$，

$$x\in L⟹\text{Pr}[A(x)=1]\ge \frac{2}{3},$$$$x\notin L⟹\text{Pr}[A(x)=1]\le \frac{1}{3}.$$

两侧都有错误，但与 $1/2$ 保持常数间隙。独立运行奇数次并取多数，由 Chernoff 界可把错误概率降为 $e^{-\mathrm{\Omega }(k)}$；因此 $2/3,1/3$ 可替换为任意固定、可放大的有界误差常数。

直觉

BPP 算法每次可能答错，但正确答案在随机运行中有稳定多数。多数投票把微弱但固定的可靠性放大为极高置信度。

例子与边界

只要求成功概率 $1/2+2^{-n}$ 不足以在多项式次重复中放大到常数，因为偏差太小。BPP 是最坏输入上的概率保证，不是“对某个输入分布平均准确”。算法使用的随机位和运行时间都必须由输入长度的多项式界定。

推论与应用

有 $\mathrm{P}\subseteq \mathrm{RP}\subseteq \mathrm{BPP}$，且 BPP 对补封闭。随机性是否真正扩展多项式时间能力仍未知；伪随机生成器与去随机化研究试图证明在适当困难性假设下 $\mathrm{BPP}=\mathrm{P}$。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 7。
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995，Ch. 1。