Impagliazzo–Wigderson 困难性—随机性定理

一张函数真值表可能只有很少位置难算，大部分位置都容易猜。先把真值表编码，使原来的每一个位置能从编码中许多相关位置恢复；再使用接近半数错误仍能局部列表恢复的结构。这样，一个能在编码表大部分位置略胜随机猜测的小电路，就会反过来帮助恢复原表的每个位置。

由于原表来自 E 中的函数，完整真值表虽指数大，却仍能在指数时间构造。最后只在对数长度上调用这个硬函数，指数求值时间便转成了待模拟任务规模的多项式。

先明确所用的放大桥梁 ​

下面使用文献中由局部列表译码建立的现代放大版本。[2, Theorems 7.61–7.62] 在指数最坏情形困难的假设下，可统一构造一族函数 $h_{\ell }$，其输入长度 $r=O(\ell )$、求值时间 $2^{O(\ell )}$，并存在常数 $\delta >0$，使足够大 $\ell$ 上所有规模至多 $2^{\delta \ell }$ 的电路，其均匀输入正确率至多

不同长度的编码和填充按该放大定理统一安排。这里引用的是完整放大定理，而不是在本页重新证明高阶编码的局部列表译码构造；后面的 NW 参数与确定性模拟将全部展开。

这条桥梁的机制可以沿反方向检查。把原函数的 $2^{\ell }$ 位真值表当消息，经可局部列表译码的码展开。若小电路在编码表上有超过允许的预测优势，便把它当作一个带大量错误的接收词 oracle。列表译码公理库列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。产生少量候选局部解码器，其中一个能恢复原表每个指定位置。

非一致归约可以硬连正确候选的编号。把每位置恢复失败率放大到远小于 $2^{-\ell }$ 后，由并合界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。对全部 $2^{\ell }$ 个位置作并集，存在一份固定随机币同时恢复整张原表。于是获得计算原函数的确定性小电路，与最坏情形下界冲突。

为什么要局部解码？若恢复一个原函数值之前先读完整指数长接收词，就无法从一个小平均预测电路得到足够小的最坏情形电路。为什么允许列表？预测优势可能仅略高于 $1/2$，唯一纠错半径通常不够；候选编号作为非一致建议补上歧义。放大定理精确控制这些开销，才能保留指数硬度。

把输出规模M代入全部参数 ​

希望欺骗规模 $M$ 的电路，并产生 $M$ 位输出。取

其中固定常数 $K$ 选得足够大。对式 (1)，可要求 $\delta K>4$。于是 $h_{\ell }$ 的可抵抗电路规模至少为 $M^4$ 量级，预测优势上界至多为 $M^{-4}$，而输入长 $r=O(\log M)$。

使用 NW 的 $(r,a)$-设计，取 $a=\lceil {\log }_{2}M\rceil$。把长度常数取足够大，并在需要时补上不参与计算的输入位，可保证 $r\ge a$；额外输入位不会削弱平均困难性，因为任何利用它们的预测电路都可固定一组补位而保留平均优势。相应显式设计的种长为

在 NW 重建中，规模 $M$ 的区分器加上各交集真值表，需要

规模，最终严格小于放大后保留的 $M^4$ 级预算。若要求 PRG 区分误差为 $1/M$，下一位归约所需排除的预测优势为 $1/M^2$；式 (1) 的 $M^{-4}$ 级上界足够强。因此对充分大 $M$，得到能以误差 $1/M$ 欺骗规模 $M$ 电路的生成器。

计算一次输出需 $M$ 次 $h_{\ell }$ 求值，其时间为

全部种子共有 $2^d=M^{O(1)}$ 个，枚举总成本仍为 $M$ 的固定多项式。这里的多项式次数可依赖原困难函数与常数 $c$，定理并没有给一个实用的小常数模拟器。

最后一步才是P=BPP ​

对任意 BPP 算法，把其每个固定输入对应的随机带电路规模和随机位数，都包进某个 $M=\mathrm{poly}(n)$。当 $M$ 足够大时，$1/M<1/12$，于是可直接调用短种子枚举定理公理库伪随机种子枚举与 BPP 去随机化PRG-based derandomization把固定输入下的随机带判决视为有限规模电路，枚举能欺骗它的对数种子并验证接受概率间隙，分别计算种长、安全资源与生成器求值时间。，按接受比例相对 $1/2$ 的位置作出确定判断。

有限多个不足阈值的输入长度可以用固定有限表处理，不影响多项式时间类别。于是 BPP 包含于 P；反向包含由确定算法不使用随机位即可得到。

三种看似相近却不够的假设 ​

若只知道函数在无穷多个长度很难，构造出的生成器可能也只在相应长度安全，不能据此给对每个长度都正确的 P 算法。若只知道存在某个 EXP 函数的困难下界，输入缩到 $\ell =O(\log M)$ 后的求值时间可能是 $2^{(\log M{)}^k}$，不再多项式。

仅有一个最坏情形困难函数，也不能绕过放大：函数在绝大多数输入上恒为零时，平均预测几乎免费。NW 的输入要求和定理最初的假设确有实质距离。

这一定理解释了两类研究之间的联系：足够强的显式电路下界可以提供可枚举的伪随机性；随机算法的确定性模拟则不必以破解密码学原语为前提。它没有证明计算困难与随机性在所有模型、所有安全尺度上都等价。

原始 Impagliazzo–Wigderson 工作使用去随机化 XOR 放大，将扩张图游走与近乎不交集合组合起来。[1] 此处用局部列表译码版本表达放大桥梁，便于把编码、重建与预算分开；两者不能仅凭同一结论就混称为同一个逐步构造。