Furst–Saxe–Sipser 1984：常数深度电路怎样算不出奇偶性

破除误解：多项式下界不是指数，随机限制也还不是切换引理#

第一层误解把标题听成「常数深度电路需要指数个门才能算奇偶」，或听成后来教材里那条 $\exp(\Omega(n^{1/(d-1)}))$ 已经印在 1984 年。定理 3.3 排除的是多项式规模：不存在深度固定、规模 $n^{O(1)}$ 的奇偶电路。推论 3.4 给出的定量形状是 $\Omega(n^{\log^{(k)}n})$，其中 $\log^{(k)}$ 是迭代 $k$ 次的对数，$k=3(d-2)$。这是超多项式，但离指数还隔着一层迭代对数。卢帕诺夫 1961 年已经证明深度 2 必须指数；本页要的是深度可以任意固定、只要不随 $n$ 增长。把 1984 年收成哈斯塔德的紧指数权衡，会把一次随机限制的塌缩收成一次切换引理。

第二层误解把第二节听成已经造出一座神谕，使相对化的多项式层次与多项式空间分开。定理 2.4 是条件句：若奇偶性对每个常数 $k$ 都不能由深度固定、规模 $O(n^{\log^k n})$ 的电路计算，则存在神谕 $A$ 使 $\mathrm{PSPACE}^A\neq\mathrm{PH}^A$。他们猜想这句更强的规模下界成立，但正文证明到的是迭代对数，还够不着定理 2.4 的假设。语言 $L^A=\{1^n\mid A$ 中长度为 $n$ 的串有奇数个$\}$ 属于 $\mathrm{PSPACE}^A$；若它落进某一层 $\Sigma_i^{P,A}$，则 $2^n$ 个变元上的奇偶会变成深度 $i+1$、准多项式规模的电路。一九七五年 留下「有没有神谕使层次无穷」的开放句；本页把这句话接到奇偶电路的规模，并没有把神谕构造写完。把条件句读成已经分离 $\mathrm{PH}$ 与 $\mathrm{PSPACE}$，会把一次归约收成一座神谕。

第三层误解把「随机限制」听成哈斯塔德切换引理，或听成把输入随机钉死之后电路就变成决策树。原文的限制是函数 $\rho:X_n\to\{0,1,*\}$：星号表示仍自由，0 与 1 表示钉死。分布对每个变元独立，取星号的概率是 $n^{-1/2}$，取 0 与取 1 平分剩下的质量。限制诱导新电路：与门只要有一个成员被钉成 0 就塌成常数 0，或门对偶。奇偶性在限制下仍是奇偶，见引理 3.2。证明走三步塌缩：先把第 1 层门的宽度压成与 $n$ 无关的常数，再把第 2 层压成常数，最后用分配律改写、合并相邻的或门，深度减一。哈斯塔德后来把「一层变成小决策树」钉成可计算的概率；1984 年还没有那条引理。把切换引理提前写进这十五页，会把一次存在性概率论证收成一条紧的深度–规模曲线。

第四层误解把后年的自然证明、代数化、概率可验证明焊进这一卷，或把阿吉泰的独立论文写成第四作者，或把可编程逻辑阵列听成芯片净表。拉兹博罗夫与鲁迪奇、阿伦森与维格森都不在页码 13 至 27 里。阿吉泰 1983 年从有限结构上的一阶公式出发，得到与常数深度电路等价的另一条奇偶下界，时间平行，署名不同。引言把常数深度电路写成可编程逻辑阵列的数学模型：与平面加或平面对应深度 2 的无界扇入；民间传说奇偶、乘法与传递闭包装不进小阵列。本页给出的是多项式面积下界的组合来源，不是布线图。

无界扇入电路、随机限制，以及奇偶性怎样拒绝多项式规模#

装置从分层电路开始。第 0 层是文字 $x_j$ 或 $\neg x_j$；第 $i$ 层是若干第 $i-1$ 层电路的非空集合，偶数层为与、奇数层为或。常数电路 0 与 1 单独存在。深度就是层号，规模是遗传地属于它的子电路个数。这样定义的电路与普通有向无环图等价，只是与或必须隔层交替、只连相邻层。任意深度 $d$、规模 $s$ 的电路可以改写成这种形状，深度仍是 $d$，规模至多 $4s+2n$。多出来的多半是扇入为 1 的平凡门；若只计导线，新规模大约 $2s$。门的扇入没有上界。这正是后来所称 $\mathrm{AC}^0$ 的组合骨架，只是 1984 年的正文还不使用这个类名。本页给出的是分层电路上的规模下界，不是把与或门的扇出、线长写成装配说明书。

$n$ 元奇偶函数是 $x_1+\cdots+x_n\pmod{2}$，或其否定。引理 3.2：任意限制作用在奇偶上，得到的仍是（更少变元上的）奇偶。因此不能指望靠钉死输入把目标变成常数——除非把自由变元钉光。卢帕诺夫已经证明深度 2 的奇偶电路规模指数；克拉普琴科对公式给出 $n^2$ 下界。本页考虑的限制更弱：深度固定、扇入无界、规模多项式。定理 3.3 是主定理：奇偶性不能由常数深度、多项式规模的电路计算。

证明用反证法。令 $d$ 是使多项式规模奇偶电路存在的最小深度。由卢帕诺夫，$d\ge 3$。第一步从规模至多 $n^k$ 的深度 $d$ 奇偶电路出发，按上述分布抽限制 $\rho$。失败事件有两件：星号少于 $\sqrt{n}/2$，或诱导电路里出现宽度大于常数 $c$ 的第 1 层门。切比雪夫不等式把第一件的概率压到 $O(n^{-1/2})$。第二件按第 1 层门是「宽」还是「窄」分开：宽门（宽度 $\ge c\ln n$）极容易被钉成常数，窄门则很难留下超过 $c$ 个星号。取 $c=8k$ 后，失败概率是 $o(1)$。于是存在限制，使剩下的自由变元至少 $\sqrt{n}/2$ 个，电路仍算奇偶，且第 1 层宽度被常数封顶。第二步对第 2 层做同类限制，归纳证明：若第 1 层宽度已是常数 $c$，则第 2 层以 $1-o(n^{-k})$ 的概率只依赖常数 $b_c$ 个输入；只依赖常数个输入的第 2 层可以改写成规模仍为常数的等价电路。第三步用分配律把这些第 2 层改写成或–与形状，规模至多 $a\cdot 2^a$，再合并现在相邻的两层或门，并用德摩根律对换与或，得到深度 $d-1$、规模仍多项式的奇偶电路，与 $d$ 的最小性矛盾。更细的记账把第一步的规模吹成平方，每重复一次第二步至多让第 1 层宽度三重指数增长，于是得到推论 3.4 的迭代对数。推论 3.5：多项式规模的奇偶电路深度必须是 $\Omega(\log^*n)$。推论 3.6：对任意 $k$ 与 $p\ge 2$，函数「等于 $k\pmod{p}$」同样进不了常数深度多项式电路。

第四节引入常数深度、多项式规模归约：若 $f$ 可以用常数深度多项式电路实现，电路里除了与、或、非之外还允许计算 $g$ 的门，就写 $f\le_{cp}g$。引理 4.1：若奇偶性可如此归约到 $g$，则 $g$ 自己也不能由常数深度多项式电路实现。多数票、二进制整数乘法、有向图的传递闭包都接到奇偶性上，因而分享同一条下界。封面仍是定理 3.3。可编程逻辑阵列在引言里是深度 2 的工程影子；一旦深度被允许固定但任意大，多项式面积仍然装不下这几件函数。本页证明这种装不下存在，不把阵列上的乘积项表写成攻击步骤。

第二节把电路接到迈耶–斯托克迈耶的多项式层次。相对化空间采用「询问必须装进多项式空间带」的口径；若允许指数长询问，分开 $\mathrm{PSPACE}^A$ 与 $\mathrm{PH}^A$ 会变得容易。把 $\Sigma_i^{P,A}$ 的句子改写成只问一次神谕的等价句子之后，接受条件变成一棵高度 $i+1$ 的与或树，叶子是长度为 $n$ 的神谕询问或其否定。这棵树正是 $2^n$ 个变元上的奇偶电路。因此准多项式规模的常数深度奇偶电路一旦存在，就会把 $L^A$ 推进某一层相对化层次。定理 2.4 把箭头反过来：更强的规模下界一旦成立，就可以对角化造出 $L^{A'}\notin\mathrm{PH}^{A'}$。1975 年已经知道有神谕使 $\Sigma_2$ 与 $\Pi_2$ 分开；再往上的层次，当时的技术不够。本页给出的是电路规模与神谕分离之间的桥梁，不是一座已经走完的神谕。

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

它证明了：奇偶性不能由常数深度、多项式规模、扇入无界的与或非电路计算；定量下界是深度 $d$ 上的 $\Omega(n^{\log^{(k)}n})$，其中 $k=3(d-2)$；多项式规模则迫使深度至少是迭代对数。模 $p$ 计数、多数票、整数乘法与传递闭包经由常数深度归约分享同一结论。随机限制是手续：以 $n^{-1/2}$ 的密度留下自由变元，浅层无界扇入以高概率塌成常数宽度，奇偶性在限制下不塌。它还证明：若奇偶性连准多项式规模的常数深度电路都没有，则存在神谕分开相对化的多项式空间与多项式层次。引言把方法论写清楚：要看见 $P$ 对 $NP$，必须分析计算的内部结构；常数深度电路是先被打开的一层。

它没有证明奇偶性需要指数规模，也没有证明 $P\neq NP$。迭代对数不是指数；$\mathrm{AC}^0$ 远在 $P$ 之下。定理 2.4 的神谕停在条件句里，姚期智 1985 年与哈斯塔德 1986年的指数下界才把假设补上，那些都不在这十五页里。自然证明、代数化、概率可验证明与交互式证明等于多项式空间同样不在。阿吉泰的独立路线属于有限模型论，不是本页封面。单调电路上的团下界是拉兹博罗夫 1985年的另一枚钉子。对照属于 电路复杂度 总览与 障碍 页。本页把「无界扇入的浅电路怎样看不见奇偶」写成一次随机限制。概念证据到此为止。定理 3.3 回答多项式规模不够；$L^A$ 回答同一句规模若再强一点，会怎样扰动相对化层次。两句都不是操作单。

跨域连接#

• 电路复杂度：总览把 $\mathrm{AC}^0$、随机限制与后来的切换引理画在同一张图上。图上的第一枚显式钉子以 1984 年的分层电路与定理 3.3 为准。把哈斯塔德的指数权衡提前读成本页，会把一次超多项式论证收成一条紧曲线。地图可以后写；本页只提供「钉死大多数输入之后，浅层与或会塌、奇偶不会塌」的手续。
• 贝克–吉尔–索洛维一九七五年论文：十年前的相对化说，黑箱模拟看不见 $P$ 对 $NP$ 的内部。本页把内部打开到常数深度，并证明打开之后奇偶仍然难。神谕世界里的 $L^A$ 把奇偶电路的规模译回层次能否与多项式空间分开；译法依赖 1975 年的询问机，对象却已经是门。把 1984 年听成又造了两座相反神谕，会把条件句收成定理 1 与定理 3 那一对。
• 库克一九七一年论文：库克把任意多项式非确定性计算编译成布尔公式。本页问的不是「公式可不可以满足」，而是「满足关系里最整齐的奇偶，浅电路算不算得出」。完全性给的是上界方向的归约；随机限制给的是下界方向的塌缩。把 SAT 听成奇偶，会把一次存在性编译收成一次模 2 求和。
• 拉兹博罗夫–鲁迪奇一九九七年论文：自然证明把「建设性且对随机函数成立」的下界技术标成一类。1984 年的随机限制正是后来被放进这类样本的早期成员：它对显式的奇偶有效，也对「看起来随机」的函数同样有效。障碍页管三道滤网的接力；本页停在滤网出现之前的那一次成功。把 1997 年读回 1984 年，会把一次组合塌缩收成一次密码学自我妨碍。
• 概率论：限制的存在性不靠构造某一枚钉死方案，而靠失败概率严格小于 1。切比雪夫管星号太少，宽门与窄门的分案管某一层太宽。概率方法在这里不是算法里的抛硬币，而是证明里的计数：只要随机对象以正概率满足性质，确定性对象就存在。把随机限制听成随机算法，会把一次存在性论证收成一次蒙特卡洛手续。
• 证明：相对化排除一类可在任意神谕下重放的证明；随机限制给出另一类必须打开门结构的证明。被证明的不是「奇偶没有电路」，而是「一类受深度与规模约束的电路不够」。概率被写进证明内部，结论对每张具体电路仍然确定。把「以高概率塌缩」听成「下界只对大多数电路成立」，会把一次反证法收成一次平均情形陈述。

参考文献#

• 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. —— 本文对象：常数深度多项式规模电路上的奇偶下界、随机限制、常数深度归约，以及与相对化多项式层次的条件联系。会议先行本：22nd Annual Symposium on Foundations of Computer Science, Nashville, 28–30 October 1981, pp. 260–270. DOI: 10.1109/SFCS.1981.35.
• 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. —— 第二节所依的相对化框架，以及层次低层的神谕分离。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 多项式时间与布尔公式之间的编译，用以对照本页的电路下界。
• A. R. Meyer & L. J. Stockmeyer, "The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space", Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, 1972, pp. 125–129. DOI: 10.1109/SWAT.1972.29. —— 多项式层次的来源，第二节的神谕问题由此提出。
• J. Hartmanis & R. E. Stearns, "On the Computational Complexity of Algorithms", Transactions of the American Mathematical Society 117, 1965, pp. 285–306. DOI: 10.2307/1994208. —— 用以标明对角化分开的是时钟层次，不是本页所挡的浅电路。
• O. B. Lupanov, "Implementing the algebra of logic functions in terms of bounded-depth formulas in the basis &, ∨, ¬", Doklady Akademii Nauk SSSR, 1961. —— 论文所引：深度 2 的奇偶电路规模指数。
• V. M. Khrapchenko, "Complexity of the realization of a linear function in the class of π-circuits", Matematicheskie Zametki 9, 1971, pp. 21–23. —— 论文所引：奇偶公式的平方规模下界。

延伸阅读#

• 与 电路复杂度 对读：总览管 $\mathrm{AC}^0$ 到 $\mathrm{ACC}^0$ 的战线；本页停在 1984 年的随机限制。
• 与 P vs NP 的证明障碍 对读：总览管三道障碍的接力；本页只提供后来被放进自然证明样本的那一次浅电路成功。
• 与 拉兹博罗夫–鲁迪奇一九九七年论文 对读：自然证明把随机限制收成一类技术；本页还没有那张滤网。
• 与 贝克–吉尔–索洛维一九七五年论文 对读：相对化要求打开内部；本页打开的是常数深度。
• 与 Miklós Ajtai, "$\Sigma^1_1$-Formulae on Finite Structures", Annals of Pure and Applied Logic 24(1), 1983, pp. 1–48 对读：独立的有限模型路线，不是本页署名。
• 与 哈斯塔德 1986 对读：切换引理把本页的超多项式界推到近似紧的指数权衡。