随机复杂度类包含关系

这些类的包含关系主要由允许误差的方向和阈值强弱逐步放宽：P 不出错也不依赖随机性；ZPP 只允许运行时间随机，保持零错误；RP/coRP 只在一侧出错；BPP 允许双侧常数误差；PP 最后只保留“略多于一半”的严格多数。这些箭头是语义放松，并不表示已知严格；随机性是否给 P 增添能力仍是去随机化的核心问题。

$\mathbf{RP}\subseteq \mathbf{NP}$ 使用“接受时绝不出错”的单边保证，不能照搬到 BPP；BPP 的某条接受随机串可能对应错误答案。PP 不是 bounded-error 类，其接受优势可以指数级小。图中除 $\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{coRP}$ 外，不应把普遍相信的严格性或去随机化猜想写成已证等号。

把形式陈述中的交集关系展开，可另写单侧链 $P\subseteq ZPP\subseteq RP\subseteq BPP\subseteq PP$，并保留 $ZPP=RP\cap coRP$。RP 算法是 BPP 算法，因为否实例错误率为 $0$、是实例可放大到至少 $2/3$；BPP 又属于 PP，因为其接受概率在是、否两侧跨越 $1/2$。

不能把 $RP\subseteq NP$ 与上链混为同一理由：RP 的某个接受随机串可作为 NP 证书，依赖零假阳性。PP 的微小多数无法通过普通放大转回 BPP，故最后一个包含远非等价。

该链把 Las Vegas、单侧错误、双侧错误与多数接受模型放进同一图谱。更强的去随机化结论或严格分离需要额外结构、困难性假设或尚未解决的复杂度突破。

该图连接 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。、RP公理库复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。、ZPP公理库复杂性类 ZPPZero-error probabilistic polynomial time · ZPP可由零错误、期望多项式时间随机算法判定的语言类。、BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。 与 PP公理库复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。。概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。 固化常数阈值，Sipser–Gács–Lautemann 把 BPP 放入 PH，伪随机生成器则研究这些包含何时能坍缩到 P。