Razborov 1985：单调电路怎样看不见团

破除误解：超多项式不是指数，单调下界也还不是 P 对 NP#

第一层误解把标题听成「团需要指数个单调门」，或听成阿隆–博帕纳那条 $\exp(\Omega((m/\log m)^{1/3}))$ 已经印在 1985 年的四页里。定理 2 给出的是两条渐近：团规模 $s$ 固定、$m\to\infty$ 时，单调复杂度至少是 $\Omega(m^{s}/(\log m)^{2s})$；取 $s$ 随 $m$ 对数增长时，下界形状是 $m^{c\log m}$（$c>0$）。变元数 $n=m(m-1)/2$，于是对输入长度而言这是超多项式，还不是指数。枚举所有 $s$ 顶点子集、对每团取边的与再取或，给出显然上界 $2\binom{m}{s}$。阿隆与博帕纳在 Combinatorica 第 7 卷页码 1 至 22 修改论证、把团检测推进到指数，页码也不是 303 至 308。把 1985 年收成 1987 年的指数形状，会把一次格上距离收成一次向日葵引理。

第二层误解把这四页听成 1987 年 Combinatorica 第 7 卷页码 303 至 308，或听成把《数学札记》里逻辑积和式的完整证明一并算进《报告》。封面页码是 798 至 801。逻辑积和式是定理 3 已经印出的第二个例子：完全证明被作者明文推到同年札记，不是这四页的附录。把两份焊在一起，会把一篇院士通讯收成另一卷的长文。本页只读已印行的《报告》：正则格、团的定理 2、逻辑积和式的定理 3 及其对普拉特问题的回答。

第三层误解把「团是 NP 完全的，单调电路又必须很大」听成已经证明 $P\neq NP$，或听成只要把非门加回去、同一条距离还会在一般电路上成立。短讯开头引用萨维奇 1972 年的观察：若某条 NP 语言对应的一般电路复杂度满足 $(\log L_{f_{m}})/\log n_{m}\to\infty$，则 $P\neq NP$。那条箭头对准的是含非门的组合复杂度 $L_{f}$，不是单调复杂度 $L_{f}^{+}$。作者写明 $L_{f}^{+}\ge L_{f}$，所以单调下界更好下手，也正因为更好下手，它推不出那条箭头。定理 3 把这一点写成本文内部的对照：逻辑积和式就是二分图是否有完美匹配，霍普克罗夫特–卡普已经给出多项式时间算法，短讯把它写成一般电路 $O(m^{5})$；同一函数的单调复杂度仍是 $m^{c\log m}$。普拉特 1975 年问过：一般复杂度与单调复杂度的缝能不能大到超多项式。定理 3 给出肯定回答。把缝听成 $P$ 对 $NP$ 的分离，会把一次基底限制收成一次对非确定性时间的判决。

第四层误解把近似格听成切换引理，或听成自然证明已经宣布单调下界作废，或听成一份课堂演练单。1984 年的随机限制钉死输入、让浅层与或塌成常数；本页的门不受深度限制，缺的是非门。格的并与交并不等于布尔或与布尔与，距离计算的是要把多少次近似误差补回去才能碰到目标函数。一九九七年 明文把单调模型写成宽广性对不上的例外：没有「随机单调函数」的好定义，不能把这四页收进对 $\mathrm{P/poly}$ 的自然证明样本。浅电路上的奇偶下界仍然成立，单调团下界也仍然成立，两条都不自动爬到一般电路。本页给出的是已测量的格距离，不是操作单。

单调与或、正则格，以及团怎样拒绝小电路#

装置从基底开始。布尔函数 $f$ 的组合复杂度 $L_{f}$ 是用与、或、非实现它所需的最少门数。若 $f$ 还是单调的——输入按坐标增大时输出不会从 1 掉成 0——就可以问只用与、或、不许用非的单调复杂度 $L_{f}^{+}$。显然 $L_{f}^{+}\ge L_{f}$。此前对「可构造」序列（对应一条 NP 语言）最好的一般电路下界，短讯引用保罗 1977 年的 $2.5n$；最好的单调下界引用韦格纳 1982 年的 $n^{2}/\log n$。本页要构造两条可构造序列，使 $L_{f}^{+}\ge n_{m}^{c\log n_{m}}$。可构造在这里有精确意思：接受语言可被非确定图灵机在输入长度的多项式时间内识别。团与逻辑积和式都满足这一条。本页给出的是这两条函数上的单调规模下界，不是把与或门的扇出写成装配说明书。

函数被改写成单调集合，便于把门说成格运算。令 $R$ 是 $n$ 个变元对应的有限底集，$B_{n}$ 是其幂集。每个输入对应于 $R$ 的一个子集 $E$，$f$ 取值 1 的那些 $E$ 组成集合 $A(f)$。与对应交，或对应并。$f$ 单调，当且仅当 $A(f)$ 对超集封闭。$P_{+}(B_{n})$ 是全部单调家族。正则格 $\mathfrak{M}\subseteq P_{+}(B_{n})$ 有两条：它必须包含常数 0、常数 1 以及每个变元 $A(x_{i})$；作为包含关系下的偏序集，它必须是格。格中的并 $\sqcup$ 与交 $\sqcap$ 不必等于集合的并与交。误差集 $\delta^{-}$ 量出「格的并比集合的并多出来的那些输入」，$\delta^{+}$ 量出「集合的交比格的交多出来的那些输入」。函数 $f$ 到格 $\mathfrak{M}$ 的距离 $\rho(f,\mathfrak{M})$ 是最少的 $t$，使得某个格元素加上 $t$ 份这类误差就能从上下夹住 $A(f)$。定理 1：对任意单调 $f$ 与任意正则格，$L_{f}^{+}\ge\rho(f,\mathfrak{M})$。句子要按字面读：小电路走不出与格距离很远的函数。本页把它写成已印行的比较，不把它写成给新函数选格的演练。

第一个例子是团。令顶点集 $V=\{v_{1},\ldots,v_{m}\}$，变元对应可能的边，故 $n=m(m-1)/2$。对每个顶点子集 $W$，令 $E_{W}$ 为 $W$ 内部的全部边。函数 $f_{m,s}$ 在图 $(V,E)$ 上取值 1，当且仅当存在规模恰好 $s$ 的 $W$ 使 $E_{W}\subseteq E$，也就是图含有至少 $s$ 个顶点的团。加边不会拆掉已有的团，所以 $f_{m,s}$ 单调。卡普 1972 年已经把判定版本放进多项式完全表；短讯要的不是完全性，而是单调电路必须看见多少边组合。所用的正则格 $\mathfrak{M}_{m,s}$ 由「封闭」的顶点集族生成。候选集是规模至多 $s-1$ 的顶点子集。一条强迫关系 $W_{1},\ldots,W_{r}\vdash W_{0}$ 判定若干小集合是否共同推出一个新的小集合；对任意家族取最小封闭扩张，再把封闭家族映成「至少包含该家族里某一个 $E_{W}$ 的那些图」。引理 1 核对：这样得到的对象是正则格，格运算就是先做集合运算再取封闭。引理 2 限制封闭家族里极小元的个数。引理 3 把 $(s-1)$ 部完全图送进来：每个把 $V$ 涂成 $s-1$ 色的函数 $h$ 给出图 $E_{h}$，边只出现在不同颜色之间。这类图不含 $s$ 团，必须被 $f_{m,s}$ 拒绝。若强迫关系成立，则绝大多数 $E_{h}$ 会同时包含被强迫的那些小团边集。引理 4 把计数收成距离下界 $\rho(f_{m,s},\mathfrak{M}_{m,s})\ge m^{s}(s^{3}e^{8}\ln m)^{-2s}$。定理 1 于是把同一条界交给单调电路规模。定理 2 写出渐近：固定 $s$ 时是 $\Omega(m^{s}/(\log m)^{2s})$；对数增长的 $s$ 给出 $m^{c\log m}$。封闭与着色在这里是证明内部的计数，不是一份给新图性质调参数的手册。

第二个例子已经印在同一份短讯里，却常被单独抽走。$m\times m$ 布尔矩阵的逻辑积和式是 $\bigvee_{\sigma\in S_{m}}\bigwedge_{i=1}^{m}x_{i,\sigma(i)}$：存在一个置换，使对应位置全为 1。图论翻译是二分图两侧各 $m$ 个顶点时是否存在完美匹配。霍普克罗夫特与卡普 1973 年的匹配算法把一般电路放到多项式；定理 3 仍给出单调下界 $m^{c\log m}$。作者写明：定理 1 与定理 3 的完整证明将刊于《数学札记》第 37 卷。因此逻辑积和式的封面句属于这四页，展开的格构造属于札记邻居。普拉特问题在这里得到肯定答案：同一函数可以一般电路小、单调电路超多项式大。非门一旦被允许，匹配会走另一条路；团在一般电路上的规模仍然未知，若对团也证明超多项式的 $L_{f}$，才会经萨维奇那条备注碰到 $P$ 对 $NP$。本页没有走完那一步。本页证明单调与或看不见团的超多项式距离，不把格上的封闭手续写成攻击步骤。

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

它证明了：存在正则格，使团函数 $f_{m,s}$ 到该格的距离至少是 $m^{s}(s^{3}e^{8}\ln m)^{-2s}$，因而任何单调电路的规模至少这么大。固定 $s$ 时界为 $\Omega(m^{s}/(\log m)^{2s})$；对数增长的 $s$ 给出超多项式 $m^{c\log m}$。逻辑积和式作为第二条可构造序列，单调复杂度同样至少 $m^{c\log m}$，而一般电路已有多项式上界。定理 1 把任意单调函数的单调电路规模接到它与某个正则格的距离。方法论上的句子是：与、或可以在格里被近似，近似会留下可数的误差；团的 $s$ 团与 $(s-1)$ 部图被这些误差隔得很开，小电路凑不够次数。它回答普拉特：一般复杂度与单调复杂度的缝可以超多项式。

它没有证明 $P\neq NP$，也没有证明一般电路上的超多项式下界。$\mathrm{AC}^{0}$ 上的奇偶下界属于 1984 年与 1986 年，不在页码 798 至 801。指数形状的单调团下界属于阿隆–博帕纳 1987 年页码 1 至 22，不是本页，也不是同一卷页码 303 至 308。带素数模门的浅电路下界属于拉兹博罗夫与斯莫伦斯基后来的另一条线。自然证明、代数化、概率可验证明都不在。陶尔多什 1988 年把「多项式时间、单调却指数难」写得更干净，仍是后年邻居。对照属于 电路复杂度 总览与 障碍 页。本页把「不许用非的与或怎样用格距离看不见团」写成一次已印行的比较。概念证据到此为止。定理 2 回答团的单调规模；定理 3 回答同一套距离对已在 $P$ 里的匹配仍然大。两句都不是操作单。

跨域连接#

• 电路复杂度：总览把浅电路、模门、单调与一般电路画在同一张图上。图上的单调钉子以 1985 年这四页的格距离为准；指数加强属于阿隆–博帕纳，不能提前读进《报告》。地图可以后写；本页只提供「与或被换成格运算之后，团与 $(s-1)$ 部图之间剩下一条可数的缝」这一枚钉子。
• 弗斯特–萨克斯–西普塞尔一九八四年论文：那十五页打开的是常数深度，手续是随机限制，目标是奇偶。本页打开的是单调基底，手续是正则格，目标是团。弗斯特文末把本页标成另一枚钉子，时间只隔一年，装置不相交。把 1985 年读成 1984 年在团上的重放，会把一次钉死输入收成一次格上封闭。
• 拉兹博罗夫–鲁迪奇一九九七年论文：自然证明把「建设性且对随机函数成立」的下界技术标成一类，并写明单调模型缺少可用的宽广性。1985 年的格距离正是后来被放进那条例外的早期成员：它利用单调性，不要求对随机真值表也密。障碍页管三道滤网的接力；本页停在滤网出现之前、已经成功的那一次单调论证。把 1997 年读回 1985 年，会把一次组合距离收成一次密码学自我妨碍。
• 库克一九七一年论文：库克把任意多项式非确定性计算编译成布尔公式。团的完全性要等到卡普次年的表。本页假定团已经是一条 NP 语言，问的不是「公式可不可以满足」，而是「满足关系里这条最整齐的图性质，单调电路算不算得出」。完全性给的是上界方向的归约；格距离给的是下界方向的比较。把 SAT 听成团，会把一次存在性编译收成一次边组合。
• 图论：团与图尔兰型的完全多部图是图论里的一对经典反例：一边是尽量密的子图，一边是被染色切开、因而不含更大团的图。拉兹博罗夫把这对立面收进电路：单调电路若太小，近似误差就填不满两者之间的缝。图论供给的是组合对象；本页供给的是这些对象上的门数。把单调下界听成又一条极值定理，会把一次电路规模收成一次边数。
• 证明：相对化排除一类可在任意神谕下重放的证明；随机限制给出必须打开浅层门的证明；本页给出必须丢掉非门、改在格里记账的证明。被证明的不是「团没有电路」，而是「一类不许用非的电路不够」。距离写在证明内部，结论对每张具体单调电路仍然确定。把「格上近似」听成「下界只对大多数电路成立」，会把一次比较收成一次平均情形陈述。

参考文献#

• A. A. Razborov, "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR 281(4), 1985, pp. 798–801. English: Soviet Mathematics Doklady 31(2), 1985, pp. 354–357. —— 本文对象：正则格与距离、团函数的定理 2、逻辑积和式的定理 3，以及对普拉特问题的肯定回答。
• A. A. Razborov, "Lower bounds on monotone complexity of the logical permanent", Matematicheskie Zametki 37(6), 1985, pp. 887–900. English: Mathematical Notes 37(6), 1985, pp. 485–493. DOI: 10.1007/BF01157687. —— 短讯所指向的定理 1 与定理 3 完整证明，邻居不是封面。
• Noga Alon & Ravi B. Boppana, "The monotone circuit complexity of Boolean functions", Combinatorica 7(1), 1987, pp. 1–22. DOI: 10.1007/BF02579196. —— 后年把本页的超多项式界推进到指数；同卷第 303–308 页是另一份相关长文邻居，不得与 1985 年《报告》焊成一篇。
• A. E. Andreev, "On a method for obtaining lower bounds for the complexity of individual monotone functions", Doklady Akademii Nauk SSSR 282, 1985. English: Soviet Mathematics Doklady 31, 1985, pp. 530–534. —— 同年独立的单调下界，不是本页署名。
• M. Furst, J. B. Saxe & M. Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Mathematical Systems Theory 17, 1984, pp. 13–27. DOI: 10.1007/BF01744431. —— 浅电路上的奇偶下界，用以标明本页是另一枚钉子。
• 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. —— 切换引理，装置不是单调格。
• A. A. Razborov & S. Rudich, "Natural Proofs", Journal of Computer and System Sciences 55(1), 1997, pp. 24–35. DOI: 10.1006/jcss.1997.1494. —— 后年把单调模型写成自然证明的例外。
• 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. —— 多项式时间与布尔公式之间的编译，用以对照本页的电路下界。
• Richard M. Karp, "Reducibility among Combinatorial Problems", in Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. —— 团进入多项式完全表的出处。
• John E. Hopcroft & Richard M. Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal on Computing 2(4), 1973, pp. 225–231. DOI: 10.1137/0202019. —— 定理 3 所依的一般算法上界。
• Vaughan R. Pratt, "The Power of Negative Thinking in Multiplying Boolean Matrices", SIAM Journal on Computing 4(3), 1975, pp. 326–330. DOI: 10.1137/0204027. —— 短讯所引：与或电路对与或非电路的缝；定理 3 给出超多项式回答。
• Ingo Wegener, "Boolean functions whose monotone complexity is of size $n^{2}/\log n$", Theoretical Computer Science 21(2), 1982, pp. 213–224. DOI: 10.1016/0304-3975(89)90084-4. —— 短讯所引：此前最好的单调下界。
• John E. Savage, "Computational Work and Time on Finite Machines", Journal of the ACM 19(4), 1972, pp. 660–674. DOI: 10.1145/321724.321731. —— 短讯所引：一般电路超多项式则 $P\neq NP$ 的备注。

延伸阅读#

• 与 电路复杂度 对读：总览管单调脚手架与一般电路的裂隙；本页停在 1985 年的格距离。
• 与 弗斯特–萨克斯–西普塞尔一九八四年论文 对读：浅电路钉子是奇偶；本页是团。
• 与 哈斯塔德 1986 对读：切换引理不在这四页里。
• 与 拉兹博罗夫–鲁迪奇一九九七年论文 对读：自然证明把单调模型写成例外；本页还没有那张滤网。
• 与 P vs NP 的证明障碍 对读：总览管三道障碍的接力；本页只提供后来被标成「单调例外」的那一次成功。
• 与 Éva Tardos, "The gap between monotone and non-monotone circuit complexity is exponential", Combinatorica 8, 1988, pp. 141–142 对读：后年把定理 3 的缝推到指数，对象仍不是 1985 年《报告》。