Håstad 1986：切换引理怎样把浅电路收成近乎最优的下界

破除误解：指数权衡不是第一次成功，切换也还不是随机限制本身#

第一层误解把标题听成「哈斯塔德最先证明奇偶不在 $\mathrm{AC}^0$ 里」，或听成随机限制发明于 1986 年。一九八四年 的定理 3.3 已经排除多项式规模；推论 3.4 给出 $\Omega(n^{\log^{(k)}n})$，其中 $k=3(d-2)$。那是超多项式，离指数还隔着迭代对数。卢帕诺夫 1961 年更早已证明深度 2 必须指数。本页要收紧的是：深度固定为任意常数 $d$ 时，规模下界走到 $\exp(\Omega(n^{1/(d-1)}))$。把第一次塌缩记在伯克利这十五页，会把一次随机限制的存在性论证收成一条切换引理。

第二层误解把会议录十五页听成 1987 年那本 MIT Press 专著，或听成把博士论文六十八页附近的材料一并算进 STOC。封面页码是 6 至 20。专著标题是 Computational Limitations of Small-Depth Circuits，属于同一工作的书册邻居：它把学位论文写开，不是这十五页的第二封面。把两份焊在一起，会把会议论文的篇幅收成一本小书。本页只读已印行的 STOC 文本：切换引理，以及奇偶的近乎最优下界。

第三层误解把同一署名的 2001 年论文读回 1986 年，或把概率可验证明写成这里的装置。2001 年的对象是不可近似性：随机赋值已能期望满足 Max-3SAT 的 7/8 子句，任何多项式算法若还想更好，就会迫使 $P=NP$。那条缝钉在概率可验证明上，与无界扇入电路的随机限制不是同一套手续。本页至多把它标成后年邻居，不把它打开。把 7/8 听成奇偶的深度–规模曲线，会把一次近似硬度收成一次电路塌缩。

第四层误解把切换引理听成「把输入随机钉死之后电路就变成决策树」这句口号，或听成自然证明已经宣布这套技术作废，或听成一份课堂演练单。1984 年的限制已经会让宽与门变成常数；切换引理多出来的那一截，是把还活着的一层改写成小深度决策树，从而换成相反的正规形，让相邻的同型门合并、深度减一。概率被钉成 $(O(pt))^s$ 这一形状，而不是一句「失败概率小于 1」。一九九七年 后来说：这类对随机函数也宽广、对真值表也可判定的论证，一旦强到对准一般电路，就会与伪随机发生器冲突。浅电路上的成功仍然成立，只是不能沿同一条自然性质爬到 $P$ 对 $\mathrm{P/poly}$。本页给出的是已测量的塌缩曲线，不是操作单。

切换引理：限制密度、与或门的塌缩，以及奇偶性怎样活下来#

装置仍从无界扇入的分层与或电路出发。第 0 层是文字；相邻层交替为与、或；深度是层数，规模是门的个数。这正是后来所称 $\mathrm{AC}^0$ 的组合骨架。底部一层若是宽度至多 $t$ 的与项再取或，就是宽度 $t$ 的析取范式；对偶地，宽度 $t$ 的合取范式是或项再取与。卢帕诺夫已经知道：深度 2 的奇偶电路规模指数。真正卡住后来者的，是深度可以任意固定、扇入没有上限。1984 年用一次较稀的限制把最底层宽度压成常数，再靠分配律把深度减一；失败概率够用来排除多项式规模，却不够写出 $\exp(\Omega(n^{1/(d-1)}))$。

切换引理对准的是这一层正规形。限制 $\rho$ 对每个变元独立：以概率 $p$ 留下星号（仍自由），剩下的质量由 0 与 1 平分。$p$ 就是限制密度。与门只要看见一个被钉成 0 的输入就塌成常数 0；或门对偶，一个 1 就塌成常数 1。宽门因此极容易死掉。窄门死不掉时，自由文字变少，宽度被进一步切开。哈斯塔德把「切开之后还剩下什么」钉成决策树：以至少 $1-(O(pt))^s$ 的概率，限制后的函数具有深度至多 $s$ 的决策树。深度 $s$ 的决策树既可以写成宽度 $s$ 的析取范式，也可以写成宽度 $s$ 的合取范式。于是一层或-与可以换成一层与-或。相邻两层一旦变成同型，就合并成一层，电路深度减一。这就是「切换」：不是把电路拆掉，而是把活着的一层翻到对偶形状。哈斯塔德后来的讲义把常数写成 $(5pt)^s$；不同整理本会把 5 改成 7 或 10，形状不变。本页要的是这条可计算的曲线，不是某一页上的最佳常数。

决策树为什么能切换，只需看到形状。树的每一条通向 1 的路径是一项宽度至多 $s$ 的与；这些项取或，就是宽度 $s$ 的析取范式。通向 0 的路径对偶地给出合取范式。同一函数于是同时拥有两种小宽度正规形，相邻层才能合并。1984 年用分配律硬把常数宽度的第 2 层展开，规模吹成平方、宽度按三重指数涨，所以只剩迭代对数。切换把展开代价收进失败概率 $(O(pt))^s$，规模不再被分配律炸掉。本页把它写成已印行的形状，不把它写成给新函数选宽度的演练。

奇偶性拒绝同一套塌缩。任意限制作用在 $x_1+\cdots+x_n\pmod{2}$ 上，得到的仍是剩下那些自由变元上的奇偶——除非自由变元被钉光。小深度决策树要算奇偶，必须问遍几乎全部剩下的比特：宽度不到剩余变元个数的析取范式，会漏掉一半奇偶输入。因此，只要限制结束时还留下足够多的星号，奇偶就不能被那棵小树计算。密度 $p$ 太小，星号被钉光，目标自己先死，下界变弱；$p$ 太大，与或门不切换，深度减不下来。一层切换之后，期望剩下约 $pn$ 个自由变元。把同一手续重复约 $d-2$ 次，每次把密度再按 $n^{-1/(d-1)}$ 这一量级收紧，最后仍希望留下 $\Omega(n^{1/(d-1)})$ 个星号：够让奇偶活着，又够让最后一层宽度下界变成指数。十五页的定量选择落在这一算术上。规模为 $S$ 的电路有 $S$ 个门要同时切换成功；失败概率对门数做并，于是 $S$ 必须走到 $\exp(\Omega(n^{1/(d-1)}))$，否则存在一条限制使整张电路塌成算不出奇偶的小树。这是密度与深度之间已经印行的账，不是一份给新电路类调参数的手册。

上界几乎从对面咬过来。把 $n$ 个输入切成大约 $n^{1/(d-1)}$ 大小的块，对每块用深度 $d-1$ 的电路算局部奇偶，再在顶上用一层无界扇入把块奇偶加起来。块的规模按同一指数递归展开，总规模是 $\exp(O(n^{1/(d-1)}))$。深度 2 时两边都是指数，与卢帕诺夫一致。标题里的「几乎最优」要按字面读：指数的底数与上界构造里的常数不必相同，深度的分母 $d-1$ 已经对齐。把标题听成「常数因子也最优」，会把一条指数形状的咬合收成一条数值恒等式。姚期智 1985 年已经用更重的限制手续得到指数形状；本页把手续收成切换，并把曲线收到与上界同一指数。

无界扇入是这套塌缩能成立的几何条件。与门的扇入一旦被钉成常数，随机钉死一个输入就很难把整扇门变成常数 0，切换概率不再按 $(O(pt))^s$ 掉下去。模 2 门更直接：奇偶自己就是一门，限制之后仍是一门。这就是后来 $\mathrm{ACC}^0$ 长期停住的预告，只是 1986 年的正文还不必使用这个类名。本页测量的是与或基底上的浅电路，不是模门世界里的另一条战线。1984 年的条件句——若奇偶连准多项式常数深度电路都没有，则存在神谕分开相对化的多项式空间与多项式层次——至此才有足够强的规模假设。神谕构造是同一条下界的去向，不是另一篇封面。本页证明浅层无界扇入看不见奇偶的指数权衡，不把限制抽样写成攻击步骤。

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

它证明了：计算 $n$ 元奇偶的深度 $d$、无界扇入与或非电路，规模至少 $\exp(\Omega(n^{1/(d-1)}))$；存在规模 $\exp(O(n^{1/(d-1)}))$ 的同样深度电路，故权衡近乎最优。切换引理给出手续的概率核：宽度 $t$ 的一层正规形，在密度 $p$ 的随机限制下，以 $1-(O(pt))^s$ 的概率变成深度 $s$ 的决策树，因而可以换成对偶正规形。奇偶在限制下不改类型，所以不能靠钉死输入把目标变成常数。它把 1984 年的超多项式界推进到指数，并把姚期智已得到的指数形状收成可写进常数的切换。多数票、整数乘法与传递闭包若能由常数深度电路接到奇偶，就会分享同一条指数；1984 年已经写下这类归约。本页不必重写那张归约表，封面仍是奇偶的权衡。

它没有证明 $P\neq NP$，也没有证明一般电路上的超多项式下界。$\mathrm{AC}^0$ 远在 $P$ 之下。一旦允许模 2 门，奇偶自己就是一个门，限制不再让电路变笨。单调电路上的团下界、带素数模门的 $\mathrm{AC}^0[p]$ 下界，分别属于拉兹博罗夫 1985 年与斯莫伦斯基 1987 年，不在页码 6 至 20。自然证明、代数化、概率可验证明都不在。2001 年那篇不可近似性论文是后年邻居，装置不同。1987 年专著与博士论文是篇幅更长的同一工作邻居，不是本页封面。对照属于 电路复杂度 总览与 障碍 页。本页把「浅层与或怎样在随机限制下切换、奇偶怎样拒绝切换」写成一次已印行的概率曲线。概念证据到此为止。

跨域连接#

• 弗斯特–萨克斯–西普塞尔一九八四年论文：第一次随机限制证明奇偶进不了常数深度多项式电路，定量停在迭代对数。本页不抢那一次存在性成功，只把同一条限制改写成可计算的切换概率，让深度–规模曲线走到指数。把 1986 年读成 1984 年的会议版，会把超多项式与近乎最优叠成一句。
• 电路复杂度：总览把 $\mathrm{AC}^0$、随机限制与切换引理画在同一张图上。图上的指数钉子以这十五页的权衡为准；多项式排除仍以 1984 年为准。地图可以后写；本页只提供「一层正规形以 $(O(pt))^s$ 的失败概率变成小决策树」这一枚钉子。
• 拉兹博罗夫–鲁迪奇一九九七年论文：自然证明把「建设性且对随机函数成立」的下界技术标成一类。切换引理正是后来被放进 $\mathrm{AC}^0$-自然样本的成员：它对显式奇偶有效，也对「看起来随机」的函数同样有效。障碍页管三道滤网的接力；本页停在滤网出现之前、已经成功的那一次浅电路论证。把 1997 年读回 1986 年，会把一次组合切换收成一次密码学自我妨碍。
• 贝克–吉尔–索洛维一九七五年论文：相对化说，黑箱模拟看不见 $P$ 对 $NP$ 的内部。1984 年把内部打开到常数深度，并留下一句更强的规模条件；本页把条件补成指数，神谕分离才有足够燃料。打开的仍是门，不是 1975 年那一对相反神谕。把切换引理听成又造了两座神谕，会把电路塌缩收成定理 1 与定理 3。
• 概率论：限制的存在性不靠指出某一枚钉死方案，而靠失败概率被乘方压到门数之下。独立坐标上的 $p$-星号分布是概率核；并界把「某一扇门没切换」译成规模下界。概率方法在这里不是算法里的抛硬币，而是证明里的计数：随机对象以正概率满足性质，确定性对象就存在。把随机限制听成随机算法，会把一次存在性论证收成一次蒙特卡洛手续。
• 证明：相对化排除一类可在任意神谕下重放的证明；切换引理给出另一类必须打开门结构、并且把失败概率写成显式函数的证明。被证明的不是「奇偶没有电路」，而是「深度与规模同时受约束的无界扇入电路不够」。概率写在证明内部，结论对每张具体电路仍然确定。把「以高概率切换」听成「下界只对大多数电路成立」，会把一次反证法收成一次平均情形陈述。

参考文献#

• Johan Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits", Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, 28–30 May 1986, pp. 6–20. DOI: 10.1145/12130.12132. —— 本文对象：切换引理，以及奇偶性在无界扇入浅电路上近乎最优的深度–规模权衡。
• 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. —— 随机限制的第一次成功：常数深度多项式规模电路上的奇偶下界，定量为超多项式。
• Miklós Ajtai, "$\Sigma^1_1$-Formulae on Finite Structures", Annals of Pure and Applied Logic 24(1), 1983, pp. 1–48. —— 独立的有限模型路线，时间平行，不是本页署名。
• Andrew C. Yao, "Separating the Polynomial-Time Hierarchy by Oracles", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 1–10. DOI: 10.1145/22145.22146. —— 已得指数形状的前行本；本页把手续收成切换。
• 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. —— 相对化框架；更强的奇偶规模下界被用来补 1984 年的条件神谕。
• 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. —— 后年把切换引理这一类浅电路论证标成自然证明样本。
• Johan Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987. —— 学位论文专著邻居，不是本页封面。
• Johan Håstad, "Some Optimal Inapproximability Results", Journal of the ACM 48(4), 2001, pp. 798–859. DOI: 10.1145/502090.502098. —— 后年邻居：Max-3SAT 的 7/8 紧界，装置不在本页。

延伸阅读#

• 与 弗斯特–萨克斯–西普塞尔一九八四年论文 对读：第一次随机限制停在超多项式；本页把切换写成指数权衡。
• 与 电路复杂度 对读：总览管 $\mathrm{AC}^0$ 到 $\mathrm{ACC}^0$ 的战线；本页停在 1986 年的切换引理。
• 与 拉兹博罗夫–鲁迪奇一九九七年论文 对读：自然证明把本页收成一类技术；本页还没有那张滤网。
• 与 P vs NP 的证明障碍 对读：总览管三道障碍的接力；本页只提供后来被放进自然证明样本的那一次浅电路成功。
• 与 计算复杂性理论 对读：2001 年不可近似性在那张地图的近似章节；不要把 7/8 读回这十五页。