伪随机种子枚举与 BPP 去随机化

生成器把指数大的随机带空间压缩成一小张种子表。确定性模拟不必猜哪一个种子会给出正确答案，而是把种子全部跑完，看接受的比例。

这张表必须同时保留每个固定输入的接受概率间隙。只为某几个已测输入挑一批“看起来不错”的随机带，没有证明对其他输入也有效。

枚举算法与正确性 ​

确定性模拟器计算整数

并在 $N_x/2^{d(M)}>1/2$ 时接受。若 $x\in L$，由式 (1)

若 $x\notin L$，则

两边都与阈值保持明确间隙。枚举后统计的是一个精确有理数，完全可以比较整数 $2N_x$ 与 $2^d$，不需浮点近似概率。

时间为

种长对数、$M$ 对 $n$ 多项式、$T_G$ 对 $M,2^d$ 多项式，三者合起来才得到总体多项式时间。单独说“种子短”或“生成器能算”都不够。

一张小种子表能说明什么 ​

取测试 $C(r_1,r_2,r_3)=r_1\vee r_2\vee r_3$。真均匀输入使其接受概率为 $7/8$。映射

的全部四个输出为 $000,011,101,110$，其中三个被接受，接受比例为 $3/4$，与真均匀差 $1/8$。在这个测试上，正向测试及其补测试仍位于 $1/2$ 的正确两侧。

但这不是式 (1) 对所有小电路的证明。检测三位奇偶是否为零的电路，对生成器总接受，对真均匀只接受一半。这张表能保住 OR 的多数结论，却能完全改变另一种测试的行为。去随机化需要对目标算法所有固定输入对应的测试统一保证。

对数、平方对数与平方根种长 ​

若 $d(M)=c{\log }_{2}M$，种子数是 $M^c$。若 $d(M)=c({\log }_{2}M{)}^2$，种子数是 $M^{c{\log }_{2}M}$，通常只是准多项式。若 $d(M)=\sqrt{M}$，枚举仍需 $2^{\sqrt{M}}$，不能称为多项式时间。

类似地，生成器可以比它要欺骗的规模 $M$ 测试花更多时间，只要该时间仍为 $M$ 的固定多项式。去随机化不要求生成器本身快到被那一测试预算识破不了；它只要求规定资源内的测试无法利用输出分布差异。

为什么普通密码学安全不能直接代入 ​

若一个密码学 PRG 的种长为 $k$，普通安全性只约束 $\mathrm{poly}(k)$ 时间的攻击。把 $k$ 取成 $\log n$ 后，待模拟算法可能用 $n^{10}=2^{10k}$ 时间，已经超出该安全定义覆盖的资源。

因此“取一个安全流密码、把种子设成对数长、全部枚举”并没有证明 P=BPP。需要足够强的指数安全假设，或直接构造满足式 (1) 的复杂性生成器。量词中的规模单位不能在换参数时丢掉。

NW 构造公理库Nisan–Wigderson 生成器Nisan–Wigderson generator · NW generator以小交集设计复用种子位，通过下一位预测与固定外部坐标重建困难函数，逐项核算交集真值表造成的电路规模损失。把一个平均困难函数转成限制电路测试的生成器；它的种长由集合设计决定，求值时间由硬函数决定。本页则在生成器保证已经成立后，给出完整的确定性模拟。

这个论证同样适用于需要近似某个有界接受比例的场景，只需使伪随机误差小于目标间隙。若任务要求搜索一个见证或输出复杂对象，必须另行说明怎样把相关判定或验证流程接入，不能把单比特接受概率证明直接当成全部搜索步骤。