随机复杂度类包含关系

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

先看 $\mathbf{ZPP}\subseteq \mathbf{RP}\cap \mathbf{coRP}$。设零错误算法的期望运行时间至多为多项式 $p(n)$，不妨将其放大到处处满足 $p(n)\ge 1$，在 $2p(n)$ 步截断它。由Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。，超时概率至多为 $1/2$。超时时默认拒绝，就得到无假阳性的 RP 算法；默认接受，就得到无假阴性的 coRP 算法。

反过来，若同一个语言有 RP 和 coRP 算法，每轮分别用新的随机位运行两者。RP 算法一旦接受，就能确定输入属于语言；coRP 算法一旦拒绝，就能确定输入不属于语言。每种输入在每轮得到确定答案的概率都至少为 $1/2$，独立重试的轮数由成功概率至少 $1/2$ 的几何分布理路几何分布Geometric distribution独立同概率 Bernoulli 试验中等待首次成功所需试验次数的分布。控制，故期望至多两轮就能结束，且输出始终正确。这证明 $\mathbf{RP}\cap \mathbf{coRP}\subseteq \mathbf{ZPP}$。

$\mathbf{RP}\subseteq \mathbf{NP}$ 则来自证书解释：RP 的接受随机串长度为多项式，可以充当 NP 见证，零假阳性保证否实例没有这样的见证。BPP 允许假阳性，因而单条接受随机串不提供同样保证。

这些包含关系并未确定各类是否相等。常见的去随机化猜想是 $\mathbf{P}=\mathbf{BPP}$；另一方面，PP 允许指数级小的接受优势，普通的多项式次重复不能把这种优势放大为 BPP 所需的常数间隔。

这条包含链把 Las Vegas、单侧错误、双侧错误与多数接受模型放到同一组资源界下比较，便于由算法的运行时间和误差保证判断它给出了哪一种复杂度上界。

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