Impagliazzo–Wigderson 1997：E 的指数电路硬度怎样把 BPP 收成 P

破除误解：指数电路硬度不是已经证明 P 等于 BPP#

第一层误解把标题听成「因此 $P=\mathrm{BPP}$」，或听成已经给出一台对所有长度通用、且不依赖任何硬度假设的确定性多项式时间机器。原文给的是条件句。定理 2：若 $\mathrm{E}$ 里存在布尔函数 $f$，其长度 $n$ 片段的最坏情形电路复杂度 $S(f_n)=2^{\Omega(n)}$，则 $\mathrm{BPP}=P$。「若」没有被删掉。

$\mathrm{E}$ 里是否真有对指数规模电路困难的函数，1997 年没有裁决，此后也没有被本页所覆盖的十页裁决。

把最强那一档听成无条件定理，会把一次硬度—随机性权衡收成一次已经完成的去随机化。本页没有、也不声称已经裁决 $P$ 对 $\mathrm{BPP}$。第二层误解把 1997 年的 STOC 与 1994 年的 JCSS 焊成一次印刷，或把本页读成尼桑–维格德森发生器的第二版页码。

1994 年的定理 3 已经写明：若 $\mathrm{E}$ 里有对规模 $2^{\Omega(n)}$ 电路优势只有 $2^{-\Omega(n)}$ 的函数，则 $P=\mathrm{BPP}$。

缺口在平均情形。最坏情形的指数电路下界，只保证存在一些难输入，不保证随机输入上也难预测。姚期智的异或引理可以把「略微难」放大成「几乎不可预测」，代价是把 $k$ 个独立实例并在一起。

$k$ 取多项式时，输入长度胀成原来的多项式倍，指数硬度在新长度上只剩亚指数，模拟时间就停在准多项式。

1994 年因此留下一句「几乎 $P=\mathrm{BPP}$」。

本页去随机的正是这一步放大：实例不必真正独立，种子长度只需线性，指数在新长度上仍是指数。把两份封面收成一句「尼桑–维格德森定理」，会把一次平均情形装置收成一次最坏情形放大。

第三层误解把阿德尔曼的非均匀上界听成本页的均匀算法，或把这里的发生器听成姚期智、布卢姆–米卡利那种多项式时间可计算的密码学发生器。阿德尔曼吞掉的是非均匀性：好硬币存在，不必可构造。本页若假设成立，枚举短种子的手续本身落在 $P$ 里。密码学发生器必须自身跑在多项式时间里，假设因此强到单向函数。去随机化只要求发生器「足够快」，快到枚举种子的代价仍是多项式。把本页听成又一份密钥流说明书，会把一次复杂度类内部的模拟收成一次对部署系统的构造。第四层误解把概率可验证明、交互式证明，或一份「怎样做伪随机数」的产品手册，焊进页码 220 至 229。十页处理的是电路下界、异或放大与发生器延伸率。

它不打开证明系统的缝隙，也不把扩张图游走或近乎不相交的子集写成可以拿去攻一个系统的配方。同期独立的安德烈耶夫、克莱门蒂与罗利姆把相近结论写成：若 $\mathrm{E}$ 里有函数的电路规模达到 $\Omega(2^{n}/n)$，则 $P=\mathrm{BPP}$。假设略弱于本页的 $2^{\Omega(n)}$，是邻居，不是把这十页再印一遍。

E、电路下界、发生器缺口，以及被去随机的异或引理#

装置从时间类开始。

$\mathrm{E}$ 是 $\mathrm{DTIME}(2^{O(n)})$：输入长度 $n$ 上，确定性时间只允许 $2$ 的线性指数。

它比 $\mathrm{EXPTIME}=\mathrm{DTIME}(2^{n^{O(1)}})$ 窄。输入一旦胀成 $n^{c}$，原先 $2^{\Omega(n)}$ 的电路下界在新长度上变成 $2^{\Omega(N^{1/c})}$，不再是对新长度的指数。本页坚持把放大的输入胀幅压在常数倍，正是为了让 $\mathrm{E}$ 里的指数下界在放大之后仍对 $\mathrm{E}$ 说话。最坏情形电路复杂度 $S(f)$ 是算出 $f$ 的最小门数。

$S(f_n)=2^{\Omega(n)}$ 只说：没有规模 $2^{\Omega(n)}$ 的电路能在每一个输入上算对。

发生器要骗过的测试者，问的却是随机输入上的符合率。成功概率 $\mathrm{SUC}_{s}(f)$ 是规模至多 $s$ 的电路与 $f$ 相符的最大概率。布尔情形再写成优势 $\mathrm{ADV}_{s}(f)=2\mathrm{SUC}_{s}(f)-1$。优势指数小，才叫对电路几乎不可预测。

尼桑–维格德森已经证明：这种几乎不可预测、且自身落在 $\mathrm{E}$ 里的函数，配上近乎不相交的子集设计，就能给出种子足够短的快速发生器，从而 $P=\mathrm{BPP}$。缺口是：最坏情形下界怎样变成这种优势。巴拜–福特瑙–尼桑–维格德森 1993 年用随机自归约，从 $\mathrm{EXP}$ 完全函数的最坏情形硬度挤出「略微不可预测」。本页把同一思路收紧到 $\mathrm{E}$：定理 4 说，若 $S(f)=2^{\Omega(n)}$，则存在 $h\in\mathrm{E}$，在规模 $2^{\Omega(n)}$ 的电路上成功概率至多 $1-n^{-2}$，输入长度只胀常数倍。略微难还不够。

姚期智 1982 年的异或引理把 $k$ 个独立实例的函数值异或起来：若单实例上电路会以不可忽略的概率失败，则异或值对稍小的电路几乎就是一次公平抛硬币。要让优势掉到 $2^{-\Omega(n)}$，$k$ 须到 $n$ 的多项式。独立取样要 $kn$ 个随机比特，新输入长度是原来的多项式倍。指数于是被胀破，尼桑–维格德森发生器只能给出准多项式模拟。这就是 1994 年到 1997 年之间那道「几乎」的缝。本页的技术句子是：在非均匀电路模型里，异或引理并不真正需要实例两两独立。

定理 9：对任意 $0<\gamma<1$，存在线性种子的多项式时间发生器 $G:\{0,1\}^{cn}\to(\{0,1\}^{n})^{n}$，把成功概率至多 $2/3$ 的函数送成对规模 $2^{\Omega(n)}$ 电路优势只有 $2^{-\Omega(n)}$ 的直接积。种子 $O(n)$ 比特，产生 $n$ 个长度为 $n$ 的实例。输入长度只胀常数倍，指数还在。再交给 1994 年的发生器，枚举种子就成为确定性多项式时间。这条 $G$ 不是从单向函数迭代出来的密钥流。

它是两台已知发生器的异或：一台沿扩张图上的随机游走取样，一台沿近乎不相交的子集切开种子。

游走提供逐步混合，用来替换「几乎独立」；子集设计提供坐标之间的小交集，用来把预测优势送回单实例。质量由一份新的异或引理证明来担保。证明先走直接积：电路若能同时猜对许多个 $g(x_i)$，就可被改写成对单个 $g$ 的预测器。戈德赖希–列文的硬核谓词再把「猜对整段输出」收成「猜对一个内积比特」，异或是内积的布尔特例。因帕利亚佐 1995 年的硬核分布给出部分放大：两两独立的样本已能把 $1-n^{-2}$ 的成功概率降到常数 $2/3$。本页从常数硬度出发，再用线性种子走完剩下的指数级放大。新证明被写成一场猜牌。荷官把 $k$ 张写着 $0$ 或 $1$ 的牌扣在桌上，并保证它们以至少 $p$ 的概率全是 $1$。随机翻开除一张以外的全部牌，玩家决定要不要赌剩下那张是 $1$。「全对」对应直接积电路在某一串实例上全部猜中；其余牌面被当成对手任意填写。玩家看见 $t$ 张 $0$，就以 $2^{-t}$ 的概率接受赌注。期望收益几乎就是 $p$。于是，能以概率 $p$ 猜对全部 $k$ 个值的电路，几乎能以同一优势猜对单个值。这与「单实例上存在一块常数比例的硬核」矛盾。博弈回答的是间隙从 $k$ 元组搬回单点的存在性。它不指出该攻击哪一个具体方案，也不给出可部署的预测器。

扩张图游走与子集设计，只被用来满足这份证明真正用到的两条随机性：实例之间足够混合，以及坐标交叠足够小。本页证明这种替换存在，不把图上的步数表或有限域上的多项式表写成装配说明书。

它证明了什么，没有覆盖什么#

它证明了：若 $\mathrm{E}$ 里存在最坏情形电路复杂度 $2^{\Omega(n)}$ 的布尔函数，则 $P=\mathrm{BPP}$。

随机性不能把计算加快超过多项式，除非非均匀性已经把指数时间里的某个问题加快超过多项式。

它证明了姚期智异或引理的一份去随机版本：在电路模型里，产生许多实例不必消耗与实例数成正比的独立硬币。线性种子足够把常数硬度放大到指数小优势。与 1994 年合读，硬度—随机性权衡从「几乎 $P=\mathrm{BPP}$」走到 $P=\mathrm{BPP}$，假设停在最坏情形的指数电路下界。

方法论上的句子是：直接积可以去随机；证明下界与构造足够快的发生器，仍是同一枚钉子的两面。它没有证明 $P=\mathrm{BPP}$，也没有证明 $P\neq\mathrm{BPP}$。

$\mathrm{E}$ 是否需要指数电路，仍是假设。

它没有给出任何显式函数的 $2^{\Omega(n)}$ 电路下界，也没有打开一般电路的自然证明。它没有证明单向函数存在，也没有构造多项式时间的密码学发生器。与因帕利亚佐–列文–卢比的等价相比，本页假设更弱、发生器更慢。它没有给出阿德尔曼那种无条件的 $\mathrm{BPP}\subseteq\mathrm{P/poly}$，也没有把 $\mathrm{BPP}$ 无条件送进 $P$。它没有把扩张图游走或子集设计写成密钥流步骤。

概率可验证明、交互式证明等于多项式空间，以及后来因帕利亚佐–维格德森 2001 年在均匀假设下刻画 $\mathrm{BPP}$ 模拟的那篇，都不在这十页里。

对照属于 计算复杂性 地图、电路复杂度 总览与 随机算法 总览。

本页把「最坏情形指数下界怎样沿被去随机的异或变成短种子」写成一次条件句。猜牌回答的是直接积为何不必真独立。两句都不是操作单。

跨域连接#

• 尼桑–维格德森一九九四年论文：那十九页把平均情形难近似与快速发生器写成等价，并把 $P=\mathrm{BPP}$ 留在「优势已是指数小」那一档。
• 本页补上从最坏情形指数电路走到那一档的放大，且不把输入胀成多项式。
• 没有 1994 年的设计，线性种子放大之后仍没有短发生器可接；没有 1997 年的去随机异或，1994 年的最强一档就还差一条平均情形假设。
• 把两页焊成一次印刷，会把一次缺口收成一次重印。
• 随机算法：总览管蒙特卡洛、拉斯维加斯与误差放大在素数检测上的形状，并已经写过「因帕利亚佐与维格德森 1997 年」这句垫底。
• 本页把那句话展开成条件句：若指数时间对电路足够硬，原先要抛真硬币的多项式算法可以被枚举短种子替换。
• 随机算法页问的是抛真硬币时错误如何被压下去；本页问的是假硬币在何种硬度下够用。
• 把总览里的米勒–拉宾轮数表读成本页封面，会把一次算法可靠性收成一次电路下界权衡。
• 阿德尔曼一九七八年论文：十九年前的并集把可放大的随机性送进非均匀电路。
• 每个长度存在一条对所有等长输入都诚实的硬币，却不必有一台机器把它写出来。
• 本页要的是可构造的短种子：发生器本身可算，枚举才给出均匀的 $P$ 算法。
• 两页合读才分清「随机性可以被忠告替换」与「随机性可以被最坏情形硬度替换」。
• 把 1997 年听成已经无条件去掉硬币，会把一次条件句收成一次存在性计数。
• 电路复杂度：总览管下界战例、自然证明与常数深度。
• 本页不证明任何显式函数需要指数电路；它只说，一旦 $\mathrm{E}$ 里出现这种下界，随机多项式时间就会塌向 $P$。
• 下界在那边是对象，在这边是发生器的燃料。
• 把本页听成已经给出 $\mathrm{SAT}$ 的超多项式电路，会把一次条件句收成一次下界。
• 密码学基础：公钥体系里的发生器必须自身高效，对手与发生器处于同一多项式时间档，假设因此强到单向函数。
• 本页的测试者是 $\mathrm{BPP}$ 算法展开成的电路，发生器被允许慢到种子的指数——慢，是因为去随机化本来就要枚举种子。
• 相信「$\mathrm{E}$ 需要指数电路」与相信「有单向函数」，是两档不同的工作假说。
• 本页不把游走、子集或异或放大写成拆密钥、消锁或去攻一个系统的步骤。
• 平均情况复杂性：五个世界问的是随机实例是否仍然难；本页问的是最坏情形下界能否被放大成平均情形不可预测。
• 异或引理处理的正是这条缝：难输入不必占满整个立方体，只要硬核有常数比例，去随机的直接积就能把优势压到指数小。
• 列文的分布—问题对，与 $\mathrm{SUC}_{s}$ 的电路—符合率对，刻度不同，共用的是「只在最坏点上难不够」。
• 本页不把硬核分布的候选写成实例生成步骤，更不提供如何抽样去攻一个系统。
• 计算复杂性：总览把 $P$、$\mathrm{BPP}$ 与 $\mathrm{E}$ 画在同一张资源地图上。
• 本页给出地图上一条最有名的条件边：指数时间对电路的最坏情形硬度，足以把有界错误随机性收进确定性多项式时间。
• 边的两端都还开放。
• 把「课堂相信 $P=\mathrm{BPP}$」听成「1997 年已经证明」，会把一次权衡收成一次已完成的定理。
• 证明：条件句把「什么样的下界算数」写成数学对象。
• 一份只证明「存在指数电路下界则存在短种子发生器」的论证，并不自动给出那条函数，也不自动给出确定性素数检测。
• 猜牌是证明策略，用来说明直接积的间隙可以在非独立样本上被读回单点。
• 被排除的不是证明的可能性，而是把最坏情形下界、平均情形硬度与非均匀存在混为一谈的那一类跳跃。

参考文献#

• Russell Impagliazzo & Avi Wigderson, "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma", Proceedings of the 29th Annual ACM Symposium on Theory of Computing, May 1997, pp. 220–229. DOI: 10.1145/258533.258590. ISBN: 0-89791-888-6. —— 本文对象：从 $\mathrm{E}$ 的指数电路下界推出 $P=\mathrm{BPP}$，以及异或引理的去随机。
• Noam Nisan & Avi Wigderson, "Hardness vs Randomness", Journal of Computer and System Sciences 49(2), October 1994, pp. 149–167. DOI: 10.1006/jcss.1994.1039. —— 前年邻居：快速发生器与平均情形难近似的等价；本页补上最坏情形到平均情形的线性胀幅放大。
• László Babai, Lance Fortnow, Noam Nisan & Avi Wigderson, "BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs", Computational Complexity 3, 1993, pp. 307–318. DOI: 10.1007/BF01275486. —— 从最坏情形挤出略微不可预测的先行手续。
• Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 异或引理与单向置换上的硬度—随机性权衡。
• Russell Impagliazzo, "Hard-Core Distributions for Somewhat Hard Problems", Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995, pp. 538–545. DOI: 10.1109/SFCS.1995.492584. —— 两两独立样本上的部分放大，本页定理 5 的来源。
• Oded Goldreich & Leonid A. Levin, "A Hard-Core Predicate for all One-Way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32. DOI: 10.1145/73007.73010. —— 把直接积收成布尔异或的硬核谓词。
• Leonard Adleman, "Two Theorems on Random Polynomial Time", Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978, pp. 75–83. DOI: 10.1109/SFCS.1978.37. —— 无条件的非均匀邻居：随机多项式时间具有小电路。
• Alexander E. Andreev, Andrea E. F. Clementi & José D. P. Rolim, "A New General Derandomization Method", Journal of the ACM 45(1), 1998, pp. 179–213. DOI: 10.1145/273865.273933. —— 同期独立邻居：从略弱的 $\Omega(2^{n}/n)$ 电路下界走向相近的去随机结论。

延伸阅读#

• 与 尼桑–维格德森一九九四年论文 对读：平均情形发生器对最坏情形放大。
• 与 随机算法 对读：总览管真硬币上的误差放大；本页停在假硬币何时够用。
• 与 阿德尔曼一九七八年论文 对读：非均匀存在对均匀可构造。
• 与 电路复杂度 对读：下界战例在那边展开，指数下界在这边变成发生器燃料。
• 与 密码学基础 对读：多项式时间发生器的假设更强，本页的快速发生器更慢。
• 与 平均情况复杂性 对读：随机实例是否仍难，与最坏情形如何被放大成难预测。
• 与 计算复杂性 对读：$P$ 与 $\mathrm{BPP}$ 在资源地图上的那条条件边。
• 与 证明 对读：被给出的是条件句，不是无条件的 $P=\mathrm{BPP}$。