Nisan–Wigderson 生成器

把每个 $f(z{|}_{S_i})$ 都使用独立种子当然最简单，但需要 $m\ell$ 位随机性。设计允许不同输出共享坐标，只控制共享不要太多。

假设有人能从前面若干输出预测第 $i$ 个输出。若把 $S_i$ 之外的种子位全部固定，其余输出对当前未知片段只依赖各自与 $S_i$ 的小交集。于是我们不必真的计算那些可能很难的 $f$：把小交集上的所有答案做成表即可。预测器连同这些表，就会变成计算 $f$ 的小电路。

图中每条“曲线”实际是有限域中的五个离散点；红圈表示共同坐标，虚线不是新增坐标。

用有限域多项式做小交集集合 ​

在有限域公理库有限域Finite field · Galois field底层集合有限的域。 ${\mathbb{F}}_5$ 上，以 ${\mathbb{F}}_5^2$ 的25个点为坐标全集。对每个次数至多二的多项式 $p$，令

每个集合有5点，共有 $5^3=125$ 个不同多项式。两多项式之差非零且次数至多二，所以两集合至多相交两点。得到 $d=25,\ell =5,a=2,m=125$ 的接线图。

例如 $p=0$ 与 $p=x$ 只在 $x=0$ 处相交；$p=x$ 与 $p=x^2$ 在 $x=0,1$ 处相交。把25位种子放到网格上，每个输出沿相应曲线读取5位，再交给 $f$。

这展示了真伸长的接线：25位种子可以指定125个输出。但它不是一组密码安全参数。如果 $f$ 取五位奇偶，则每个输出都是种子位的线性组合，整个输出落在维数至多25的线性空间里，能用线性代数轻易识别。好的设计不能补救一个容易预测的 $f$。

从区分器到困难函数预测电路 ​

假设一个规模 $t$ 的电路 $D$ 以优势超过 $\epsilon$ 区分 $G_f(U_d)$ 与 $U_m$。由下一位定理公理库下一位不可预测性与伪随机性Next-bit unpredictability · Yao next-bit theorem用前缀混合把整串区分器变成下一位预测器，明确随机位置的均匀算法版本及输出长度造成的优势损失。及其前缀混合公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。证明，存在一个位置 $i$，其下一位预测优势超过 $\epsilon /m$。

先取非一致版本，固定合适的补位、补后缀随机币和区分方向。这些可作为电路常量。现在把种子分为目标片段 $u=z{|}_{S_i}$ 和外部坐标 $w=z{|}_{[d]\setminus S_i}$。对 $w$ 平均仍有该预测优势，所以存在某个固定值 $w^{\ast }$ 保持优势。

固定 $w^{\ast }$ 后，对每个 $j<i$，前面第 $j$ 个输出变成

它只随 $S_j\cap S_i$ 上至多 $a$ 个未知坐标变化。把这至多 $2^a$ 个输入的答案硬连进电路，便可用 $O(a{2}^a)$ 个有界扇入门计算 $f_j$。这一小表在证明里可以非一致地存在；归约并没有声称能有效发现 $w^{\ast }$ 或计算所有难函数表值。

把 $f_1(u),\dots ,f_{i-1}(u)$ 喂给下一位预测器，得到规模至多

的电路，在均匀 $u$ 上以超过 $1/2+\epsilon /m$ 的概率计算 $f(u)$。式 (2) 使其规模不超过 $s$，与平均困难性假设矛盾。这完成了输出间相关性如何被转换为明确重建成本的证明。

种长与求值时间还要分开 ​

生成一次输出需要读取设计并计算 $m$ 次 $f$，所以求值成本为约 $m{T}_f(\ell )$，另加接线开销。去随机化中允许 $T_f(\ell )=2^{O(\ell )}$；若 $\ell =O(\log m)$，它仍是输出长度 $m$ 的多项式。这与密码学要求生成器对种长多项式时间的口径不同。

上面的多项式图设计方便看清结构，全集大小为 ${\ell }^2$。在本文所用的 $1\le a=\gamma \log m\le \ell$ 范围内，更紧的显式设计可达到 $d=O({\ell }^2/a)$，其中 $\gamma >0$ 固定；取整只改变常数。[2, Lemma 7.22] 当 $\ell =\mathrm{\Theta }(\log m)$，这个改进将种长从平方对数降到对数，决定了枚举种子最后是准多项式还是多项式时间。

NW 直接使用的是“均匀输入上近乎不能猜”的强平均困难性。仅知道某个输入最难，不能直接代入式 (2)：一个函数可以只在极少点困难，其余输入几乎总为零。

Impagliazzo–Wigderson 定理公理库Impagliazzo–Wigderson 困难性—随机性定理Impagliazzo–Wigderson theorem在E中存在逐充分大长度的指数非一致电路下界这一明确假设下，经局部列表译码式困难性放大、NW设计和种子枚举推出P=BPP，并逐项对齐参数。中的困难性放大负责把明确的最坏情形电路下界转成适合此处的平均困难性；种子枚举公理库伪随机种子枚举与 BPP 去随机化PRG-based derandomization把固定输入下的随机带判决视为有限规模电路，枚举能欺骗它的对数种子并验证接受概率间隙，分别计算种长、安全资源与生成器求值时间。负责把已经得到的短种子生成器转成确定性算法。这三步承担不同任务，任何一项都不能只靠名称相近省掉。