形式陈述

Sipser–Gács–Lautemann 定理给出

$$\mathrm{BPP}\subseteq {\mathrm{\Sigma }}_2^P\cap {\mathrm{\Pi }}_2^P,$$

因而

$$\mathrm{BPP}\subseteq \mathrm{PH}\subseteq \mathrm{PSPACE}.$$

先把 BPP 算法的错误率放大到指数小。对固定输入，把使算法接受的随机串视作布尔立方体中的集合；若输入为“是”，该集合很稠密，概率法保证存在多项式多个平移覆盖全部随机串；若输入为“否”，集合很稀疏，任意这些平移的并都无法覆盖全集。“存在一组平移，使所有随机串被覆盖”正是 ${\mathrm{\Sigma }}_2^P$ 谓词。BPP 对补封闭，再得到 ${\mathrm{\Pi }}_2^P$ 包含。

直觉

概率放大先把正确与错误输入变成“几乎覆盖全部随机串”与“只占极少随机串”。少量集合平移随后把统计差异转写成一层存在量词加一层全称量词。

例子与边界

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

推论与应用

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

参考资料

• Clemens Lautemann, “BPP and the Polynomial Hierarchy,” Information Processing Letters 17(4), 1983，pp. 215–217。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 7。