Sipser–Gács–Lautemann 定理

该定理先用概率放大把正确与错误输入变成“好种子几乎覆盖全部随机串”与“好种子只占极少随机串”，再把 BPP 的随机种子集合改写为组合覆盖问题：是实例的高密度好种子通过少量平移可覆盖整个随机空间，是否存在这些平移可由一层存在量词加一层全称量词表达。于是随机多项式时间被置于多项式层级第二层附近，而不必假设 $P=BPP$；证明的精髓是把统计差异和概率存在性压成短确定证书与全称检查。

该结论是无条件包含，不等于已经证明 $\mathrm{BPP}=\mathrm{P}$。它依赖有界错误与多项式随机位；若成功偏差只有指数小，概率放大和覆盖论证都不能在多项式资源内直接使用。结论也比朴素的 $\mathrm{BPP}\subseteq \mathrm{PSPACE}$ 更精细。

先把 BPP 错误放大到极小，使是实例的坏种子集合很稀。选择多项式个平移 $z_1,\dots ,z_k$，希望对每个随机串 $r$，至少某个 $r\oplus z_i$ 是好种子；概率法保证存在这样的平移组，验证“覆盖所有 $r$”形成 $\mathrm{\exists }{z}_1\cdots z_k\mathrm{\forall }r$ 的谓词。

定理给出 $BPP\subseteq {\mathrm{\Sigma }}_2^P\cap {\mathrm{\Pi }}_2^P$（常见表述），不是 $BPP=P$。覆盖论证依赖先行放大和种子长度多项式，不能直接对任意微小偏差概率算法套用。

随机多项式时间不会超出多项式层级，因此即使随机性增加了 P 的能力，其位置仍受第二层量词结构约束。该结果是去随机化与复杂度层级研究之间的核心桥梁。

它以 BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。 和 概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。 为起点，把随机类嵌入 多项式层级公理库多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。，进而显然包含于 PSPACE公理库复杂度类 PSPACEComplexity class PSPACE可由确定性图灵机在多项式空间内判定的语言类。。该结果也是“随机性似乎不会把可判定能力推得过高”的重要无条件证据。