Razborov–Rudich 1997：自然证明怎样把电路下界挡在伪随机函数门外

破除误解：自然证明不是不可判定，电路下界也没有从此作废#

第一层误解把标题听成「$P$ 对 $NP$ 不可判定」，或听成已经证明这个问题没有证明。原文构造的不是一条哥德尔式的不可证句子。被排除的是一类手续：先写出布尔函数的某种组合性质 $C_n$，再证明凡具有该性质的函数都需要超多项式规模电路，最后核验 SAT 或另一条 $NP$ 里的显式函数也具有该性质。若 $C_n$ 还满足构造性与宽广性，它就会与「存在足够硬的伪随机发生器」相冲突。换一套既不可高效检验、又只被可忽略比例的函数满足的论证，障碍并不自动生效。把 1997 年收成「这个问题没有数学答案」，会把一次对证明技术的分类说成一次不完备性定理。引言里提到的 ZFC 独立性是对照，不是本页给出的定理。

第二层误解把「自然证明被挡住」听成八十年代的电路下界从此作废，或听成所有下界都必须相对化。弗斯特–萨克斯–西普塞尔一九八四年论文 把奇偶函数推出常数深度多项式规模电路，姚期智与哈斯塔德随后收紧深度–规模权衡；拉兹博罗夫与斯莫伦斯基把带素数模门的浅电路再推开一截。这些证明仍然成立，而且第三节把它们写成自然的，或可以自然化的。被挡住的是把同一套「对随机函数也宽广、对真值表也可判定」的性质加强到足以分离 $P$ 与 $\mathrm{P/poly}$。浅电路上的成功，并不自动给出一般电路上的超多项式下界。把「自然」听成「错误」，会把一次方法论分类收成一次对已发表定理的否定。

第三层误解把构造性听成「必须在 $n$ 的多项式时间内判定 $n$ 元函数」，或把宽广性听成「几乎所有函数都难，因此我们已经证完」。构造性的输入是长度为 $2^n$ 的真值表，时间界是这张表的多项式，也就是 $2^{O(n)}$。对输入长度 $n$ 而言这是指数，对组合学家手中的对象而言却是「可算的」。宽广性要求至少 $2^{-O(n)}$ 比例的函数落入某条子性质 $C_n^*$，不是要求几乎全部函数都难——香农式计数已经知道几乎全部函数需要指数电路，那条计数本身恰恰被他们当作非自然论证的样本：它给不出可判定的大子集。若硬度假设为真，这样的构造性大子集根本不存在。把香农计数听成本页的定理，会把「随机函数很难」收成「SAT 很难」。

第四层误解把伪随机函数听成一次对部署系统的攻击说明书，或把单调电路下界、无限制的对角化一并焊进「全部作废」。戈德赖希、戈德瓦塞尔与米卡利把长度翻倍的发生器铺成一棵深度为 $n$ 的二叉树，短种子于是给出一整张 $n$ 元函数真值表；本页只用这个对象说明：有用性迫使伪随机函数落在 $C_n$ 之外，宽广性又迫使随机函数以不可忽略的概率落在 $C_n$ 之内，于是性质本身就是统计检验。检验如何从函数层回到字符串层，是第四节的归约，不是操作单。单调模型是明文写出的例外：性质往往可行，却没有「随机单调函数」的好定义，宽广性对不上。计数与对角化预存于组合下界之前，本页对它们的前途不置可否。概念证据到此为止。

自然组合性质、有用性，以及伪随机函数生成器#

装置从 $n$ 元布尔函数的集合 $F_n$ 开始。每个 $f_n\in F_n$ 被看成长度为 $2^n$ 的真值表。组合性质是一族子集 $\{C_n\subseteq F_n\}$。它称为自然的，当且仅当存在子性质 $C_n^*\subseteq C_n$ 同时满足两条：构造性——「真值表是否落入 $C_n^*$」属于 $\mathrm{P}$（以真值表长度为输入）；宽广性——$|C_n^*|\ge 2^{-O(n)}\cdot|F_n|$。性质对 $\mathrm{P/poly}$ 有用，当且仅当凡属于 $C_n$ 的函数序列都具有超多项式电路规模：对任意常数 $k$，充分大的 $n$ 上规模大于 $n^k$。一份证明被称为对 $\mathrm{P/poly}$ 自然，是指它或多或少显式地给出了这样一条有用的自然性质。性质的定义是精确的；证明是否「写在期刊里」稍滑，但第四节的否定句一律读成「不存在这样的自然组合性质」。参数化版本把构造性放进类 $\Gamma$、有用性对准类 $\Lambda$、宽广性写成密度 $\delta_n$。默认取值是 $\Gamma=\mathrm{P}$、$\Lambda=\mathrm{P/poly}$、$\delta_n=2^{-O(n)}$。已知的非单调下界往往还能把 $\Gamma$ 收到 $\mathrm{NC}^2$ 甚至 $\mathrm{AC}^0$，密度收到接近 $1$。否定结果对准的参数更宽：准多项式规模电路上的构造性仍然不够。

第三节把已有证明写成自然的，或经过自然化的。奇偶函数不在 $\mathrm{AC}^0$ 里的论证，取 $C_n$ 为「不存在留下适当数目自由变元、却把函数钉成常数的限制」。有用性就是原文的塌缩；宽广性是一次计数；构造性更落在 $\mathrm{AC}^0$ 里：枚举全部 $2^{O(n)}$ 条限制，对每一条用深度 $2$ 的电路检查是否仍非常值，再取合取。于是弗斯特–萨克斯–西普塞尔、姚期智与哈斯塔德都是 $\mathrm{AC}^0$-自然的。对 $\mathrm{AC}^0[q]$（$q$ 为素数幂）的下界，拉兹博罗夫的框架几乎直接是秩：把函数映到矩阵空间，取秩大的那些。求秩在 $\mathrm{NC}^2$ 里。斯莫伦斯基证明奇偶不能被 $\mathrm{AC}^0[3]$ 小电路计算，表面上像在用一条只对奇偶成立的多项式恒等式，又像在用非构造的计数。自然化把性质改成：乘上 $f_n$ 之后，低次多项式空间与其自身的和足够高维。检验变成一张从真值表可算的矩阵是否满秩或维数过门槛；再利用「$f_n$ 与奇偶乘 $f_n$ 至少有一个过门槛」，宽广性落到至少一半。这是全文最费手续的一次自然化。感知机弱次数、安德烈耶夫公式规模与收缩因子、内积函数的偏差、开关–整流网络上的最小覆盖，都被写成 $\mathrm{P}$-、$\mathrm{AC}^0$-或 $\mathrm{TC}^0$-自然。本页证明这些下界可以自然化，不把限制、秩或线性规划写成装配说明书。

第四节是封面。定理 4.1：不存在对 $\mathrm{P/poly}$ 的 $\mathrm{P/poly}$-自然下界证明，除非每个多项式时间可计算的长度翻倍发生器 $G_k:\{0,1\}^k\to\{0,1\}^{2k}$ 都只有硬度 $H(G_k)\le 2^{k^{o(1)}}$。硬度 $H(G_k)$ 是使某规模 $S$ 的电路以优势 $1/S$ 区分 $G_k$ 的输出与真随机 $2k$ 比特串的最小 $S$。特别地，若存在 $2^{n^\varepsilon}$-硬的函数族，就不存在对 $\mathrm{P/poly}$ 的 $\mathrm{P/poly}$-自然证明。论证把发生器按戈德赖希–戈德瓦塞尔–米卡利的方式铺成伪随机函数：种子沿输入比特走下深度 $n$ 的二叉树，叶子上读出函数值。有用性迫使这些函数全部落在 $C_n$ 之外；宽广性迫使真随机函数以 $2^{-O(n)}$ 的间隙落在 $C_n$ 之内。性质因此是规模 $2^{O(n)}$ 的检验。再沿树的内部结点做一次混合，把函数上的间隙交给某一层的字符串发生器。$\varepsilon$ 任意，故硬度不能高于 $2^{k^{o(1)}}$。混合是存在性归约，不是一份对具体密码方案的步骤清单。定理 4.4 把构造性放宽到准多项式规模电路，结论不变；拉兹博罗夫在有界算术片段里的观察是：那里的超多项式电路下界一旦可证，往往会自然化，再与本节合在一起就变成相对那些理论的独立性——仍依赖同一硬度假设，不是 ZFC 独立性。

没有硬度假设，离散对数仍给出一条无条件句。把布卢姆–米卡利的硬比特 $B_{p,g}$ 看成约 $\log p$ 个变元的布尔函数。定理 4.5：对任意半指数的规模函数 $t(n)$，不存在对 $\mathrm{SIZE}(t(n))$ 有用、又满足 $\mathrm{P/poly}$-构造性与宽广性的性质，使无穷多个 $B_{p,g}$ 落入其中。半指数的意思是 $t$ 的二次迭代比指数长得更快，$2^{n^\varepsilon}$ 是，$2^{(\log n)^C}$ 不是。推论 4.6 把对象收到 $\bigcup_{\varepsilon>0}\mathrm{SIZE}(2^{n^\varepsilon})$。维格森指出的要点是：离散对数的最坏情形与平均情形多项式等价，因此「对显式函数有用」本身就会把发生器的硬度压到与 $t$ 不相容的地方。定理 4.2 与 4.3 则完全不谈密码假设：尼桑给出对常数深度、$2^{O(n)}$ 规模电路伪随机、自身却落在 $\mathrm{AC}^0[2]$ 里的函数族；于是不存在对 $\mathrm{AC}^0[2]$ 的 $\mathrm{AC}^0$-自然下界。与第三节合读：足够证明奇偶不在 $\mathrm{AC}^0$ 里的自然性，先天写不出拉兹博罗夫–斯莫伦斯基那一档。自然证明按组合性质的复杂度自己排成层次。第五节给宽广性一条形式证据：公式规模的形式复杂度测度若在一个函数上取到大值 $t$，则至少四分之一的函数上至少为 $t/4$；逼近模型导出的测度同样如此。构造性没有平行的定理，经验来自第三节。本页给出的是归约与不存在性，不是操作单。

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

它证明了：已知的非单调显式电路下界都可以写成自然证明，或经自然化后落入 $\mathrm{AC}^0$、$\mathrm{NC}^2$、$\mathrm{TC}^0$ 或 $\mathrm{P}$ 的构造性档。若存在对 $\mathrm{P/poly}$ 有用的 $\mathrm{P/poly}$-自然性质，则每个多项式时间的长度翻倍发生器都不够 $2^{n^\varepsilon}$-硬。离散对数的硬比特不能被任何同时宽广、构造、且对半指数规模有用的性质无穷多次抓住。$\mathrm{AC}^0$-自然性质写不出对 $\mathrm{AC}^0[2]$ 的下界。形式复杂度测度自动满足宽广性。方法论上的句子是：一条既对随机函数宽广、又对真值表几乎可行的性质，一旦强到能挡住一般电路，就会变成伪随机函数的检验。要证明 SAT 需要超多项式电路，必须牺牲宽广性或构造性。

它没有证明 $P\neq NP$，也没有证明 $P=NP$。硬度假设不是定理。它没有给单调下界配上平行的宽广性定义，也没有判决对角化与纯计数的前途。代数化、概率可验证明、交互式证明等于多项式空间，以及后来用电路可满足性算法推出的 $\mathrm{NEXP}$ 对 $\mathrm{ACC}^0$ 下界，都不在这十二页里；对照属于总览页。有界算术里的自然化是引言中的应用指针，封面仍是第四节对伪随机发生器的归约。本页把「什么样的组合下界算自然」写成可检验的两条，再把第三条有用性接到一条被广泛相信的密码学原语上。$C_n^*$ 回答构造性与宽广性怎样被写成对真值表的谓词；$G_k$ 回答为何这样的谓词不能太有用。两句都不是操作单。

跨域连接#

• 电路复杂度：总览把浅电路、模门、单调与一般电路画成一张下界地图。地图上的成功战例，正是本页第三节要自然化的对象；地图上「为什么一般电路走不动」的那一格，以 1997 年的三条性质为准。把奇偶不在 $\mathrm{AC}^0$ 里读成本页封面，会把一次限制塌缩收成一次对伪随机函数的归约。
• 贝克–吉尔–索洛维一九七五年论文：二十年前的神谕把黑箱对角化挡在门外，于是目光转向电路。本页表明：转向之后最顺手的组合手续，仍会被另一道滤网拦住。相对化问的是同一句话在两座世界里能否同时成立；自然性问的是性质对随机函数是否太宽、对真值表是否太易判定。两道滤网排除的技术类不相交。
• 密码学基础：单向函数与伪随机发生器是「平均情形下仍然难」的原语，比最坏情形的 $P\neq NP$ 更强。本页把这条更强的信念写成对下界技术的限制：若发生器真有 $2^{n^\varepsilon}$ 硬度，自然证明就到不了 $\mathrm{P/poly}$。相信命题为真的理由，与挡住最顺手证法的理由，在这里是同一条假设。本页不把发生器的构造写成攻击步骤。
• 证明：数学把证明看成从公理出发的有穷推理链。复杂性把「哪一类推理链算数」再写成数学对象。自然证明排除的不是证明的可能性，而是同时满足构造性、宽广性与有用性的那一类组合论证。把障碍听成「不要再证明」，会把一次分类收成一次禁令。
• 库克一九七一年论文：完全性把 SAT 钉成 $NP$ 里的显式代表，电路下界若能挡住 SAT，也就挡住整类。本页假定这个代表已经存在，问的是挡住它的组合性质会不会太自然。库克要的是多项式归约上的钉子；本页要的是钉子上的下界证明会不会自己变成伪随机检验。
• 哥德尔不完备定理：引言把「对 ZFC 独立」列为另一种「问题很难」的技术答案，并声明本页走的是第三条路：已知方法太弱。后年在有界算术片段里的自然化，才把电路下界相对那些弱理论写成独立性，而且仍要借用第四节的硬度假设。不要把十二页读成一条算术不完备定理。

参考文献#

• Alexander A. Razborov & Steven Rudich, "Natural Proofs", Journal of Computer and System Sciences 55(1), 1997, pp. 24–35. DOI: 10.1006/jcss.1997.1494. —— 本文对象：自然组合性质的构造性、宽广性与有用性，已知非单调下界的自然化，以及定理 4.1 至 4.5。
• Alexander A. Razborov & Steven Rudich, "Natural Proofs", Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Montreal, 1994, pp. 204–213. DOI: 10.1145/195058.195134. —— 期刊论文的会议前身。
• T. Baker, J. Gill & R. Solovay, "Relativizations of the P =? NP Question", SIAM Journal on Computing 4(4), 1975, pp. 431–442. DOI: 10.1137/0204037. —— 引言所引的相对化障碍，用以标明本页挡住的是另一类手续。
• Merrick Furst, James B. Saxe & Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Mathematical Systems Theory 17, 1984, pp. 13–27. DOI: 10.1007/BF01744431. —— 第三节所自然化的 $\mathrm{AC}^0$ 奇偶下界。
• 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. —— 奇偶下界的深度–规模收紧，同属 $\mathrm{AC}^0$-自然。
• Roman Smolensky, "Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity", Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 77–82. DOI: 10.1145/28395.28404. —— 第三节最详细的一次自然化。
• Oded Goldreich, Shafi Goldwasser & Silvio Micali, "How to Construct Random Functions", Journal of the ACM 33(4), 1986, pp. 792–807. DOI: 10.1145/6490.6503. —— 定理 4.1 把发生器铺成伪随机函数时所依的构造。
• 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. —— 硬度定义与离散对数硬比特 $B_{p,g}$ 的来源。
• Noam Nisan, "Pseudorandom Bits for Constant Depth Circuits", Combinatorica 11(1), 1991, pp. 63–70. DOI: 10.1007/BF01375474. —— 定理 4.2 所用、对 $\mathrm{AC}^0$ 伪随机而自身在 $\mathrm{AC}^0[2]$ 中的发生器。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 用以标明 SAT 作为显式 $NP$ 代表的来源，不是本页的归约口径。

延伸阅读#

• 与 P vs NP 的证明障碍 对读：总览管三道障碍的接力；本页停在 1997 年的自然性质与伪随机函数。
• 与 电路复杂度 对读：下界战例在那边展开，自然化与挡板在这边。
• 与 贝克–吉尔–索洛维一九七五年论文 对读：相对化挡住黑箱对角化，自然证明挡住宽广而可判定的组合性质。
• 与 密码学基础 对读：单向函数与发生器的信念，在本页变成对下界技术的限制。
• 与 弗斯特–萨克斯–西普塞尔一九八四年论文 对读：$\mathrm{AC}^0$-自然的样本，以及它为什么写不出模二门上的下一档。
• 与 证明 对读：被排除的是证明技术的一个类，不是证明的可能性。