Nisan–Wigderson 1994：E 里足够硬的函数怎样冒充 BPP 测试者的硬币

破除误解：硬度换成随机性不是已经证明 P 等于 BPP#

第一层误解把标题听成「因此 $P=\mathrm{BPP}$」，或听成已经给出一台对所有长度通用、且不依赖任何硬度假设的确定性多项式时间机器。原文给的是条件句。定理 2 按硬度强弱分成三档：若 $\mathrm{DTIME}(2^{O(n)})$ 里有对多项式规模电路难近似的函数，则 $\mathrm{BPP}$ 掉进所有 $2^{n^{\varepsilon}}$ 时间类的交；若难近似的规模升到 $2^{n^{\varepsilon}}$，模拟时间降到 $2^{(\log n)^{c}}$；若硬度本身达到 $2^{\varepsilon n}$，才得到 $\mathrm{BPP}=P$。三句话都带着「若」。把最强那一档听成无条件定理，会把一次硬度—随机性权衡收成一次已经完成的去随机化。本页没有、也不声称已经裁决 $P$ 对 $\mathrm{BPP}$。

第二层误解把 1994 年的期刊与 1988 年的 FOCS 焊成一次印刷，或把后年 STOC 上的加强本读成同一篇的第二版页码。会议文本是十页摘要；期刊把发生器、组合设计、与 $\mathrm{EXPTIME}$ 中难近似性的等价写完整，并修正了原会议论证里关于定理 1 逆方向的一处错误——戈德赖希指出后，作者借用巴拜–福特瑙–尼桑–维格德森的思路补上。先行与展开不是同一印刷。1993 年《计算复杂性》上的巴拜–福特瑙–尼桑–维格德森文本，以及 1997 年 STOC 的因帕利亚佐–维格德森文本，都是邻居：前者把某些模拟结论加强，后者把最坏情形下界送进 $P=\mathrm{BPP}$。把四份封面收成一句「尼桑–维格德森定理」，会把一次平均情形装置收成一次最坏情形放大。

第三层误解把这里的发生器听成姚期智、布卢姆–米卡利或因帕利亚佐–列文–卢比那种多项式时间可计算的密码学发生器。引言把分野写在第一页：密码学发生器必须自身跑在多项式时间里，假设因此强到单向函数；去随机化只要求发生器「足够快」，快到枚举种子的代价仍可接受。本页把这种发生器称作 quick：运行时间允许是种子长度的指数，输出只须骗过规模与输出长度相当的电路。因帕利亚佐–列文–卢比证明单向函数与多项式时间发生器等价；本页证明 $\mathrm{EXPTIME}$ 中的难近似性与 quick 发生器等价。两套等价共享「硬度可以冒充硬币」这句话，假设强度与发生器效率却不是同一档。把本页听成又一份密钥流说明书，会把一次复杂度类内部的模拟收成一次对部署系统的构造。

第四层误解把阿德尔曼的忠告、西普塞尔–加奇把 $\mathrm{BPP}$ 送进多项式层次、或常数深度上无条件的奇偶发生器，焊进页码 149 至 167 的封面。阿德尔曼吞掉的是非均匀性：好硬币存在，不必可构造。层次论证给出的是无条件的量词上界，不把 $\mathrm{BPP}$ 收进 $P$。哈斯塔德的奇偶下界在第三节被用来无条件地骗过常数深度电路，那是同一套设计在已有下界上的应用，不是把「$\mathrm{E}$ 里有硬函数」写成已经证明的事实。

快速发生器、近乎不相交的设计，以及一条难近似函数怎样拉长种子#

装置从两个参数开始。发生器 $G:\ell\to n$ 把长度为 $\ell$ 的种子拉成 $n$ 比特；任何规模为 $n$ 的电路，把真随机串与 $G$ 的输出当成输入时，接受概率之差小于 $1/n$。quick 的意思是：$G$ 本身落在 $\mathrm{DTIME}(2^{O(\ell)})$ 里。去随机化的手续在引理 2.1：先用发生器冒充原先算法的硬币，再用穷举种子做多数票。若原先随机算法跑 $t$ 步，模拟时间就是 $2^{O(\ell(t^{2}))}$。种子短，枚举才多项式；种子若只短到 $n^{\varepsilon}$，枚举就是亚指数。发生器不必比测试者更快，这正是它与密码学发生器分道的地方。本页只使用这条资源会计，不把穷举写成产品里的轮数表。

硬度必须是平均情形的。函数 $f$ 称为 $(\varepsilon,S)$-硬，当且仅当任何规模 $S$ 的电路与 $f$ 的符合率都离 $1/2$ 不到 $\varepsilon/2$。$H_{f}(m)$ 取使 $f$ 在长度 $m$ 上为 $(1/h,h)$-硬的最大 $h$。引言里的「不能被规模 $s(n)$ 的电路近似」，只要求小电路犯一个不可忽略的错误；姚期智的异或引理再把这种弱间隙放大成 $H_{f}$ 所要的强间隙。被放大的是符合率与电路规模之间的权衡，不是一份把多个实例异或进协议的装配说明书。定理 1 的等价从这里开始：$\mathrm{EXPTIME}$ 里存在不能被规模 $s(\ell^{c})$ 近似的函数，当且仅当存在硬度 $s(\ell^{c})$ 的函数，当且仅当存在 quick 的 $s(\ell^{c})$-延伸器，当且仅当存在 quick 的发生器 $G:\ell\to s(\ell^{c})$。证明下界与构造发生器，在这条刻度上是同一句话的两面。

多比特来自组合设计，而不是来自反复把单向函数作用在种子上。一族子集 $\{S_{1},\ldots,S_{n}\}$，每个大小为 $m$、两两交至多 $k$，称为 $(k,m)$-设计。种子 $x$ 的各坐标按这些子集切开，第 $i$ 个输出比特是 $f$ 在 $S_{i}$ 所标明的那一段上的值。引理 2.4：若 $H_{f}(m)\ge n^{2}$，且设计取 $k=\log n$，则 $G(x)=f_{A}(x)$ 骗得过规模 $n$ 的电路。论证走混合：若某电路能区分 $G$ 与均匀分布，则存在某一比特，在前面比特已经按发生器填好、后面比特仍真随机时，可被预测出 $1/n^{2}$ 的优势。因为两两相交小，前面那些比特各自只依赖当前输入块里的 $\log n$ 个坐标，于是可以被规模线性于 $n$ 的公式替掉。预测电路因此变成对 $f$ 本身的近似，规模不超过 $n^{2}$，与硬度假设矛盾。混合回答的是间隙从字符串搬到函数上的存在性；它不指出该攻击哪一个具体方案，也不给出可部署的预测器。

设计本身要短。引理 2.5：对 $\log n\le m\le n$，存在 $n\times\ell$ 的 $(\log n,m)$-设计，$\ell=O(m^{2})$，且可在对数空间里算出来。构造把 $\{1,\ldots,m^{2}\}$ 看成有限域 $\mathrm{GF}(m)$ 上的点对，取次数不超过 $\log n$ 的多项式 $q$，令 $S_{q}=\{(a,q(a))\}$。每个集合大小为 $m$，两条不同多项式的图像至多交 $\log n$ 个点，这样的多项式至少有 $n$ 条。当 $m=O(\log n)$ 时，引理 2.6 把 $\ell$ 收到 $O(\log n)$：贪心选取即可，存在性靠切尔诺夫界，计算是 $n$ 的多项式时间。种子长度于是可以短到对数，枚举种子才成为确定性多项式时间。有限域上的图像是组合证据，不是一份实现域算术的代码。

定理 2 把等价换成模拟。函数取在 $\mathrm{DTIME}(2^{O(n)})$ 里，也就是后来课堂所写的 $\mathrm{E}$。对多项式电路难近似，给出亚指数模拟。对 $2^{n^{\varepsilon}}$ 规模难近似，给出准多项式模拟。硬度 $2^{\varepsilon n}$ 配上引理 2.6 的短设计，给出 $\mathrm{BPP}=P$。印刷对单侧错误的 $\mathrm{RP}$ 陈述，并声明双侧的 $\mathrm{BPP}$ 同样成立。姚期智 1982 年从单向置换推出过同一档亚指数模拟，假设却强到 $\mathrm{NP}\cap\mathrm{coNP}$ 的难近似。本页把假设降到指数时间里的平均情形电路硬度。并行类与常数深度是同一套装置的平移：若 $\mathrm{PSPACE}$ 对 $\mathrm{NC}$ 难近似，则 $\mathrm{RNC}$ 可被亚多项式空间模拟；把 $f$ 换成奇偶、把哈斯塔德下界直接接进设计，则随机 $\mathrm{AC}^{0}$ 无条件掉进准多项式时间与 $(\log n)^{c}$ 空间。随机神谕上，$\mathrm{almost}\text{-}\mathrm{NP}=\mathrm{AM}$，$\mathrm{almost}\text{-}\mathrm{PH}=\mathrm{PH}$。用发生器还可以另给出 $\mathrm{BPP}\subseteq\Sigma_{2}^{\mathrm{P}}\cap\Pi_{2}^{\mathrm{P}}$ 的证明，与西普塞尔–加奇的量词论证不是同一条路。这些推论都停在类的包含，不是操作单。

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

它证明了：对每个合理的规模函数 $s$，指数时间里的难近似性与 quick 伪随机发生器等价。平均情形硬度可以沿组合设计被复制成许多几乎独立的比特，从而骗过比该硬度更小的电路。硬度越强，种子越短，对 $\mathrm{BPP}$ 的确定性模拟越快；强到指数，模拟就停在 $P$。常数深度上，已知的奇偶下界使同一发生器不再需要未证假设。方法论上的句子是：证明电路下界与构造「足够快」的发生器，是同一枚钉子的两面；去随机化不要求发生器自己成为多项式时间算法。

它没有证明 $P=\mathrm{BPP}$，也没有证明 $P\neq\mathrm{BPP}$。$\mathrm{E}$ 里是否存在对指数规模电路难近似的函数，仍是假设。它没有把最坏情形的指数电路下界放大成平均情形硬度——那是 1997 年因帕利亚佐–维格德森的工作。它没有证明单向函数存在，也没有构造多项式时间的密码学发生器；与因帕利亚佐–列文–卢比的等价相比，本页假设更弱、发生器更慢。它没有给出阿德尔曼那种无条件的 $\mathrm{BPP}\subseteq\mathrm{P/poly}$，也没有把 $\mathrm{BPP}$ 无条件送进 $P$。它没有给出 $\mathrm{SAT}$ 的超多项式电路下界，也没有打开一般电路的自然证明。概率可验证明、交互式证明等于多项式空间，以及把发生器写成密钥流的步骤，都不在这十九页里。对照属于 计算复杂性 地图、电路复杂度 总览与 随机算法 总览。本页把「一条难近似函数怎样沿近乎不相交的子集冒充硬币」写成一次条件句。$H_{f}$ 回答的是测试者允许多大优势；设计回答的是为何多比特仍能把优势送回单比特。两句都不是操作单。

跨域连接#

• 随机算法：总览管蒙特卡洛、拉斯维加斯与误差放大在素数检测上的形状，并已经写过「尼桑与维格德森 1994 年」这句垫底。本页把那句话展开成发生器与设计：随机算法页问的是抛真硬币时错误如何被压下去；本页问的是，若指数时间里有对小电路难近似的函数，假硬币能否骗过同一类测试者。把总览里的米勒–拉宾轮数表读成本页封面，会把一次算法可靠性收成一次硬度—随机性权衡。
• 阿德尔曼一九七八年论文：十六年前的并集把可放大的随机性送进非均匀电路。每个长度存在一条对所有等长输入都诚实的硬币，却不必有一台机器把它写出来。本页要的是可构造的短种子：发生器本身可算，枚举才给出均匀算法。两页合读才分清「随机性可以被忠告替换」与「随机性可以被硬度替换」。把 1994 年听成已经无条件去掉硬币，会把一次条件句收成一次存在性计数。
• 平均情况复杂性：五个世界问的是随机实例是否仍然难；本页问的是难函数能否冒充硬币。发生器要的硬度是符合率意义上的平均情形，不是最坏情形下「存在一个难输入」。列文的分布—问题对，与 $H_{f}$ 的电路—符合率对，刻度不同，共用的是「只在最坏点上难不够」。本页不把单向函数的候选写成实例生成步骤，更不提供如何抽样去攻一个系统。
• 密码学基础：公钥体系里的发生器必须自身高效，对手与发生器处于同一多项式时间档，假设因此强到单向函数。本页的测试者是 $\mathrm{BPP}$ 算法展开成的电路，发生器被允许慢到种子的指数——慢，是因为去随机化本来就要枚举种子。相信「有足够硬的指数时间函数」与相信「有单向函数」，是两档不同的工作假说。本页不把设计、混合或异或放大写成拆密钥、消锁或去攻一个系统的步骤。
• 概率论：混合论证把「整段输出可区分」提升成「某一比特可预测」，再用近乎独立的坐标把预测送回对 $f$ 的优势。切尔诺夫界在引理 2.6 里只用来证明短设计存在，并不把存在性收成一次随机抽样实验。概率提供间隙；复杂性把间隙花在电路规模与种子长度上。把优势听成可以在实验里测到的频率，会把一次归约收成一次测量。
• 证明：条件句把「什么样的下界算数」写成数学对象。一份只证明「存在难近似函数则存在发生器」的论证，并不自动给出那条函数，也不自动给出确定性素数检测。被排除的不是证明的可能性，而是把平均情形硬度、最坏情形下界与非均匀存在混为一谈的那一类跳跃。把「课堂相信 $P=\mathrm{BPP}$」听成「1994 年已经证明」，会把一次权衡收成一次已完成的定理。

参考文献#

• 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. —— 本文对象：quick 伪随机发生器与 $\mathrm{EXPTIME}$ 难近似性的等价，以及定理 2 对 $\mathrm{BPP}$ 的三档模拟。
• Noam Nisan & Avi Wigderson, "Hardness vs. randomness", Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 24–26 October 1988, pp. 2–11. DOI: 10.1109/SFCS.1988.21916. —— 期刊论文的会议前身，十页摘要，不是本页封面。
• 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. —— 无条件的非均匀邻居：随机多项式时间具有小电路。
• 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. —— 单向置换上的硬度—随机性权衡，以及后文所用的异或放大。
• Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits", SIAM Journal on Computing 13(4), 1984, pp. 850–864. DOI: 10.1137/0213053. —— 多项式时间发生器的先行构造，用以标明本页放宽了运行时间。
• Russell Impagliazzo, Leonid A. Levin & Michael Luby, "Pseudo-random Generation from One-way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 12–24. DOI: 10.1145/73007.73009. —— 单向函数与多项式时间发生器的等价，与定理 1 对照。
• 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, 1997, pp. 220–229. DOI: 10.1145/258533.258590. —— 后年邻居：把假设从平均情形难近似收到最坏情形指数电路。
• Johan Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits", Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 6–20. DOI: 10.1145/12130.12132. —— 第三节无条件常数深度发生器所接的奇偶下界。
• 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. —— 期刊文本用来修正定理 1 逆方向、并加强部分模拟的邻居。

延伸阅读#

• 与 随机算法 对读：总览管真硬币上的误差放大；本页停在假硬币如何骗过 $\mathrm{BPP}$ 测试者。
• 与 阿德尔曼一九七八年论文 对读：非均匀存在对均匀可构造。
• 与 平均情况复杂性 对读：随机实例是否仍难，与难函数能否冒充硬币。
• 与 密码学基础 对读：多项式时间发生器的假设更强，本页的 quick 发生器更慢。
• 与 电路复杂度 对读：下界战例在那边展开，难近似性在这边变成发生器。
• 与 卡普–利普顿一九八〇年论文 对读：非均匀上界的结构代价是层次坍缩；本页的均匀发生器代价是一条硬度假设。
• 与 证明 对读：被给出的是条件句，不是无条件的 $P=\mathrm{BPP}$。