形式陈述

随机多项式时间类满足

$$\mathrm{P}\subseteq \mathrm{RP}\subseteq \mathrm{BPP}\subseteq \mathrm{PSPACE},\mathrm{RP}\subseteq \mathrm{NP}.$$

确定性算法可以忽略随机位，得到 $\mathrm{P}\subseteq \mathrm{RP}$；RP 算法经常数次重复把“是”实例的接受概率提高到 $2/3$ 以上且仍无假阳性，得到 $\mathrm{RP}\subseteq \mathrm{BPP}$。若 RP 算法接受，导致接受的随机串可作为 NP 证书。对 BPP 算法枚举全部多项式长随机串并用多项式位计数器统计接受比例，可在多项式空间内确定多数结果。

直觉

随机位既可以完全不用，也可以被当作证书或被穷举。后两种模拟会牺牲随机算法的时间优势，却分别把 RP 接到 NP、把 BPP 接到 PSPACE。

例子与边界

$\mathrm{RP}\subseteq \mathrm{NP}$ 使用“接受时绝不出错”的单边保证，不能照搬到 BPP；BPP 的某条接受随机串可能对应错误答案。枚举随机串通常需要指数时间，所以 $\mathrm{BPP}\subseteq \mathrm{PSPACE}$ 不会推出 $\mathrm{BPP}\subseteq \mathrm{P}$。这些包含是否严格均未知。

推论与应用

该结果把随机算法放回确定性与非确定性类图谱中：RP 算法给出可验证见证，BPP 算法至少不会超出多项式空间；更强的去随机化结论则需要额外结构或困难性假设。

参考资料

• 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。