Sipser–Gács–Lautemann 定理

形式陈述

Sipser–Gács–Lautemann 定理给出

\mathrm{BPP}\subseteq\Sigma_2^P\cap\Pi_2^P,

因而

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

证明先用独立重复放大把长度 $n$ 输入上的错误降到 $\varepsilon=2^{-n}$ 。这只需 $O(n)$ 次重复；设放大后的随机位数为多项式 $M=M(n)$ ，接受种子集为 $S_x\subseteq\{0,1\}^M$ 。取 $k=M+1$ 个平移。对充分大的 $n$ ，同时有 $k\varepsilon<1$ 与 $2^M\varepsilon^k<1$ ；有限个小长度可单独硬编码答案。

若 $x\in L$ ，均匀独立选择 $z_1,\ldots,z_k\in\{0,1\}^M$ 。对固定 $r$ ，所有 $r\oplus z_i$ 都不在 $S_x$ 的概率至多 $\varepsilon^k$ 。对全部 $2^M$ 个 $r$ 使用并集界，未覆盖某个点的概率至多 $2^M\varepsilon^k<1$ ，故成功概率为正，由概率方法可知存在覆盖全部立方体的一组平移。

若 $x\notin L$ ，则 $|S_x|\le\varepsilon2^M$ ；不论如何选择这 $k$ 个平移，它们的并至多有 $k\varepsilon2^M<2^M$ 个点，无法覆盖全集。因此

x\in L\iff \exists z_1,\ldots,z_k\ \forall r\in\{0,1\}^M: \bigvee_{i=1}^k A(x,r\oplus z_i)=1.

存在串总长 $kM$ 与全称串长度 $M$ 都是多项式；内层只是确定性地计算 $k$ 次已固定随机位的算法，没有增加量词层。于是 $L\in\Sigma_2^P$ 。BPP 对补封闭，对补语言再用同一证明便得 $L\in\Pi_2^P$ 。

直觉

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

例子与边界

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

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

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

推论与应用

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

它以 BPP 和概率放大为起点，把随机类嵌入多项式层级，进而显然包含于 PSPACE。该结果也是“随机性似乎不会把可判定能力推得过高”的重要无条件证据。

参考资料

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。

形式陈述 ​

形式陈述