Impagliazzo 1995：略微难的问题怎样收成一块几乎乱猜的硬核分布

破除误解：硬核不是某一指定比特，也不是已经可抽样的攻击分布#

第一层误解把标题里的 hard-core 听成戈德赖希–列文的硬核谓词，或听成「函数输出里藏着的那一位」。1989 年猜的是原像与公开向量的模二内积。本页猜的是整段判定本身：输入来自某一块支撑时，小电路对 $f(x)$ 的符合率能否离开 $1/2$ 很远。谓词版把硬度集中到一比特上。分布版把硬度集中到一块实例上。把两句话焊成「硬核定理」，会把一次密码学归约收成一次平均情形测度。

第二层误解把 1995 年听成已经证明 $P=\mathrm{BPP}$，或听成 1997 年那十页的会议前身。因帕利亚佐–维格德森一九九七年论文要把最坏情形的指数电路下界变成平均情形上的指数小优势，中间需要一次「略微难变成常数难」的部分放大。本页提供的正是这一截：输入长度不必胀成多项式，两两独立已经够把成功概率从 $1-n^{-2}$ 压到常数。指数小优势、短种子发生器、以及「若 $\mathrm{E}$ 需要指数电路则 $P=\mathrm{BPP}$」，都还在后两年。把本页听成已经去掉硬币，会把一次测度集中收成一次去随机化。

第三层误解把本页听成姚期智异或引理的第二版页码，或听成必须把 $k$ 个独立实例并成长输入才能放大。1982 年的异或把新函数写在更长的输入上：$k$ 取多项式时，长度胀破，指数电路下界在新长度上只剩亚指数。本页走另一条路。先在原来的立方体里找出一块密度为 $\delta$ 的核，核上已经接近乱猜；再论证，只要样本之间有足够的有限独立性，异或值就会撞上那块核。新证明是应用，不是把封面改挂到 1982 年。独立取样与 $k$ 元独立，在这里是证明用掉的随机性会计，不是一份把多个实例焊进协议的装配说明。

第四层误解把硬核集合听成一份可有效枚举的难实例名单，或听成已经给出对部署系统的抽样器。原文给出的是存在性：在对多数票封闭的非均匀模型里，轻度平均情形硬度迫使这样一块核存在。极小极大把「对每一个密分布都有电路表现好」翻成「存在一堆电路，它们的多数票在几乎所有点上都好」，从而与原先的 $\delta$ 失败率矛盾。多数票是证明策略，用来说明间隙可以从均匀分布搬到一块支撑上。它不指出该查询哪一个具体方案，也不给出可部署的预测器。后来提升法把对偶写成弱学习与强学习的互逆，那是后年的算法邻居，不是页码 538 至 545 的封面。

密度、多数票，以及只要求有限独立的异或#

装置从两种符合率开始。

均匀分布上的轻度硬度说：任何规模至多为 $s$ 的电路，与布尔函数 $f$ 相符的比例至多是 $1-\delta$。失败不必发生在「同一个」$\delta$ 块上。先验上完全可能每条电路各错各的，错位互相错开，立方体里没有一块对所有小电路都难的区域。本页要排除的，正是这种错位散开的图景。

硬核集合 $H\subseteq\{0,1\}^n$ 的密度至少为 $\delta$，意思是 $|H|\ge\delta\cdot 2^n$。硬核分布 $D$ 的密度至少为 $\delta$，意思是每个点的质量至多 $1/(\delta 2^n)$：质量不能在少数点上堆成尖峰，否则「几乎乱猜」只是在几个特例上成立。均匀分布限制在密度 $\delta$ 的集合上，就是这类分布的顶点；一般的密分布是它们的凸组合。标题写 distribution，摘要写 set of inputs，课堂两种说法都指这一档测度约束。

在这块支撑上，非常硬的意思是：规模略小于 $s$ 的电路，符合率至多 $1/2+\varepsilon$。$\varepsilon$ 是优势，不是一份可以在实验里直接读出的频率表。规模必须略降，因为证明要把若干条弱电路做多数票，多数票自身也占门数。原文声明：论证对任何在多数票下封闭的非均匀模型成立，布尔电路是最常用的例子，不是唯一的计算预算。

证明走对偶。若这样的密分布不存在，则对每一个密度 $\delta$ 的分布，都有一条规模较小的电路在其上取得超过 $\varepsilon$ 的优势。把电路当成博弈的一方、把密分布当成另一方，冯·诺伊曼的极小极大定理交换量词：存在一个电路上的分布，使得无论对方选哪一块密支撑，期望优势都还在。于是，除了至多 $\delta$ 比例的点，这个电路分布都在「算对」$f$。对这些点做多数票，得到一条对几乎所有输入都好的电路，规模仍受控，与均匀分布上的 $\delta$ 失败矛盾。多数票回答的是间隙如何从「每条电路各错各的」收成「存在一块大家一起错的核」。它不是查询日程。

核一旦存在，异或引理就有一条新的读法。把 $k$ 个样本上的函数值异或起来。只要其中至少有一个落入硬核，这一比特对小电路就接近一次公平抛硬币；再与其余比特异或，整体仍然接近抛硬币。均匀独立样本会以大约 $1-(1-\delta)^k$ 的概率撞上核。这是 1982 年那条放大的一份新证明：弱间隙不必靠把输入切成可穷举的碎块来集中，测度自己已经集中过了。本页同时写出亲戚：样本不必真正独立，$k$ 元独立已经够让「撞上核」的概率会计走通。两两独立是 $k=2$ 的特例，恰好够把逆多项式的失败率放大到常数间隙。一九九七年论文的定理 5 要的就是这一截部分放大，然后才用线性种子走完指数级的剩余路程。有限独立在这里是随机性预算，不是一份发生器的种子表。

它因此改写了 1990 年代中期的两种平均情形语言。一种语言把「略微难」写成均匀分布上的符合率缺口，发生器要的却是几乎不可预测。另一种语言用异或把缺口搬到更长的输入上，胀幅却会毁掉指数下界。八页把两句话收成：缺口可以先在原来的长度上被收成一块核，有限独立的异或再把核上的乱猜送回函数值。尼桑–维格德森一九九四年论文要的平均情形难近似，仍然比这块常数间隙更强；本页只负责从 $\delta$ 走到常数，不负责把优势压到 $2^{-\Omega(n)}$。对照属于计算复杂性地图与电路复杂度总览：一边问类的包含，一边问门数与符合率。两句都不是操作单。

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

它证明了：均匀分布上对规模 $s$ 只是 $\delta$-难的判定，必有一块密度至少为 $\delta$ 的硬核；在核上，规模略小的电路优势可被压到任意给定的 $\varepsilon$。论证不依赖电路的特殊代数结构，只要求非均匀模型对多数票封闭。它证明了姚期智异或引理的一份新论证，以及样本只需 $k$ 元独立的亲戚。方法论上的句子是：轻度平均情形硬度不是各条电路错位散开的幻觉，失败可以被收成一块公共的核；放大不必先把输入变长。

它没有证明单向函数存在，也没有裁决 $P$ 对 $NP$，更没有证明 $P=\mathrm{BPP}$。$\mathrm{E}$ 是否需要指数电路，仍是后年条件句里的假设。它没有给出任何显式函数的超多项式电路下界，也没有打开一般电路的自然证明。它没有构造多项式时间的密码学发生器，也没有给出戈德赖希–列文那种内积硬核谓词。五个世界的组织框架在同年另一份会议录里，不在页码 538 至 545。它没有把硬核集合写成可有效抽样的名单，也没有把多数票或有限独立写成去攻一个系统的配方。后年用提升法改写参数、用更紧的规模损失重证硬核引理，都是邻居，不是把这八页再印一遍。

对照属于计算复杂性地图、电路复杂度总览与平均情况复杂性总览。本页把「略微难怎样变成一块几乎乱猜的核」写成一次存在性翻译。密度回答的是核有多大；多数票回答的是为何错位不能永远散开。两句都不是操作单。

跨域连接#

• 戈德赖希–列文一九八九年论文：那八页把任意单向函数的求逆率集中到填充后的内积比特上，hard-core 是谓词。
• 本页把均匀分布上的失败率集中到一块密度为 $\delta$ 的实例支撑上，hard-core 是分布。
• 谓词版问的是函数值已经给出之后哪一比特仍不可预测；分布版问的是哪些输入让整段判定都接近乱猜。
• 把两份封面收成一句「硬核定理」，会把一次密码学归约收成一次测度集中。
• 因帕利亚佐–维格德森一九九七年论文：那十页要把最坏情形指数电路下界放大成指数小优势，定理 5 先调用本页的部分放大。
• 两两独立的样本把 $1-n^{-2}$ 的成功概率降到常数 $2/3$，输入长度只胀常数倍，指数才保住。
• 没有 1995 年的核，1997 年就还缺一截从「略微难」到「常数难」的钉子；没有 1997 年的去随机异或，本页走不到 $P=\mathrm{BPP}$。
• 把本页听成已经证明随机多项式时间等于 $P$，会把一次测度引理收成一次条件句。
• 姚期智一九八二年论文：十二页用独立实例的异或把弱不可预测写成几乎乱猜，封面是陷门与发生器。
• 本页给出同一条异或引理的新证明，并把独立性降到 $k$ 元独立；放大发生在已经找出的核上，而不必先把输入切碎。
• 年的发生器仍吃单向置换，本页不构造发生器。
• 把八页听成陷门函数的修订版，会把一次电路符合率论证收成一次密码学迭代。
• 平均情况复杂性：五个世界问的是随机实例是否仍然难，以及难能不能换成单向函数。
• 本页问的是更细的一刀：均匀分布上已经有 $\delta$ 的失败时，失败能否被收成一块对所有小电路都接近乱猜的核。
• 列文的分布—问题对，与密度 $\delta$ 的硬核分布，共用「只在最坏点上难不够」；同年那份五个世界讲义是组织框架，不是把这八页再印一遍。
• 本页不把硬核支撑的候选写成实例生成步骤，更不提供如何抽样去攻一个系统。
• 尼桑–维格德森一九九四年论文：那十九页把平均情形难近似与快速发生器写成等价，最强一档要求优势已经指数小。
• 本页只负责从逆多项式缺口走到常数间隙，发生器要的更碎的不可预测仍须另做放大。
• 没有 1994 年的设计，核上的乱猜不会自动变成短种子；没有 1995 年的核，平均情形假设就还停在「错位可能散开」。
• 两页都不是产品里的种子表。
• 电路复杂度：总览管下界战例、自然证明与常数深度。
• 本页不证明任何显式函数需要超多项式电路；它只说，一旦均匀分布上已经有 $\delta$ 的失败，多数票封闭的模型里就存在一块更硬的核。
• 门数在那边是对象，在这边是多数票之后必须略降的预算。
• 把本页听成已经给出 $\mathrm{SAT}$ 的电路下界，会把一次符合率翻译收成一次下界。
• 密码学基础：总览把单向函数写成原语树的根，硬核谓词是树上的一枚比特。
• 本页处理的是判定问题的平均情形测度，不假设求逆任务，也不交出可有效抽样的难实例发生器。
• 相信「均匀分布上略微难」与相信「有单向函数」，强度不同，可利用的方向也不同。
• 本页不把密分布、多数票或有限独立写成拆密钥、消锁或去攻一个系统的步骤。
• 随机算法：总览管真硬币上的误差如何被独立重复压下去。
• 本页的硬币出现在证明内部：极小极大里的混合策略、多数票、以及 $k$ 元独立样本的存在性会计。
• 随机算法页问的是抛真硬币时算法是否可靠；本页问的是假想的弱电路一旦对每个密分布都好，均匀分布上的 $\delta$ 失败会不会被多数票吞掉。
• 把多数票读成对线上系统的查询轮数，会把一次存在性翻译收成一次操作单。
• 证明：八页证明的是翻译手续存在：轻度平均情形硬度可被改写成一块几乎不可预测的核，有限独立的异或再把核送回函数值。
• 证书是对偶与多数票，不是一张已列出的难实例表，也不是一台可部署的抽样器。
• 被排除的不是证明的可能性，而是把硬核谓词、五个世界、异或引理封面与 $P=\mathrm{BPP}$ 焊成同一定理的那一类跳跃。

参考文献#

• Russell Impagliazzo, "Hard-Core Distributions for Somewhat Hard Problems", Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, 23–25 October 1995, pp. 538–545. DOI: 10.1109/SFCS.1995.492584. ISBN: 0-8186-7183-1. —— 本文对象：均匀分布上的轻度硬度收成密度为 $\delta$ 的硬核集合/分布，以及异或引理在 $k$ 元独立样本上的新证明。
• 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. —— 封面陷阱：硬核谓词，不是硬核分布。
• 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. —— 异或引理的原封面；本页给出新证明，并不把 1982 年再印一遍。
• 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. —— 后年邻居：定理 5 使用本页的部分放大，再走完去随机异或。
• Noam Nisan & Avi Wigderson, "Hardness vs Randomness", Journal of Computer and System Sciences 49(2), 1994, pp. 149–167. DOI: 10.1006/jcss.1994.1039. —— 前年邻居：平均情形难近似与快速发生器；本页只把缺口收到常数间隙。
• Russell Impagliazzo, "A Personal View of Average-Case Complexity", Proceedings of the 10th Annual Structure in Complexity Theory Conference, 1995, pp. 134–147. DOI: 10.1109/SCT.1995.514853. —— 同年另一份印刷：五个世界，不是硬核分布。
• Thomas Holenstein, "Key Agreement from Weak Bit Agreement", Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 664–673. DOI: 10.1145/1060590.1060689. —— 后年邻居：用更紧的参数重证硬核引理，不是本页封面。

延伸阅读#

• 与 戈德赖希–列文一九八九年论文 对读：硬核谓词对硬核分布。
• 与 因帕利亚佐–维格德森一九九七年论文 对读：部分放大如何被接进 $P=\mathrm{BPP}$ 条件句。
• 与 姚期智一九八二年论文 对读：异或引理的原封面与本页的新证明。
• 与 平均情况复杂性 对读：五个世界是同年另一份组织框架。
• 与 尼桑–维格德森一九九四年论文 对读：常数间隙还不够发生器最强一档。
• 与 电路复杂度 对读：多数票封闭的模型里，符合率如何变成核上的优势。
• 与 证明 对读：被给出的是存在性翻译，不是可抽样的难实例名单。