电路复杂度

破除误解：电路小并不等于有快速算法#

P/poly 是「多项式规模电路族」组成的类。P 包含于 P/poly，因为多项式时间图灵机可以展开成多项式电路。反过来不成立：电路族可以在每个 $n$ 上硬编码任意忠告（advice）。

Adleman 证明 BPP 也在 P/poly 里，随机性于是可以被非均匀性吞掉。因此「我画了一张小电路」不能直接翻译成「我有一段对所有 $n$ 都快的程序」。

密码学里的自然证明障碍，正是抓住了这点：若一种下界技术也能区分随机函数与伪随机函数，它会摧毁候选的伪随机发生器。

见 P vs NP 的证明障碍。

电路下界不是时间下界的简写，它是另一条、有时更硬的战线。另一个误解是把硬件里的逻辑门当成这里的电路。

芯片受扇出、布局、时钟限制；复杂度里的电路是有向无环图，门的扇入可以是常数或无界，边没有物理长度。

AC$^0$ 的「深度常数」是数学深度，不是纳米。

现场：奇偶函数进不了 AC⁰#

AC$^0$ 是常数深度、多项式规模、扇入无界的 AND/OR/NOT 电路。Furst、Saxe、Sipser（1984，会议版 1981）与 Ajtai 独立证明：奇偶函数（输入中 1 的个数模 2）不在 AC$^0$ 中。证明走的是随机限制：随机钉死大部分输入，电路以高概率塌成简单函数，而奇偶在限制下仍是奇偶。

Håstad 的切换引理把塌缩概率钉到可以算出精确的深度–规模权衡。这是少数「有名字的函数、有紧的下界」的成功。

它没有解决 P vs NP：AC$^0$ 远在 P 之下。它说明的是，某些下界技术在浅电路上有效，一进入对数深度或有 MOD 门的世界就失效。

Razborov（1985）对单调电路给出团函数的超多项式下界：不许用 NOT 时，找大团会很难。Alon 与 Boppana 加强了界。一旦允许否定，同样的方法就垮掉——单调性是证明的脚手架，不是问题的本质。

Smolensky（1987）把 MOD$_p$ 门加进 AC$^0$，证明 MOD$_q$（$p\neq q$ 为素数）仍算不了。ACC$^0$ 是允许任意模门的常数深度类；它是否包含 NEXP，在 2010 年前都是开放的。

核心：从自然证明到 Williams 的 NEXP ⊄ ACC⁰#

Razborov 与 Rudich（1997）的自然证明说：一大类「建设性且对随机函数成立」的下界技术，若强大到能分离 P 与 NP，就会破坏密码学需要的伪随机性。

电路下界因此被夹在中间：技术必须对显式函数有效，又不能对「看起来随机」的函数太有效。Ryan Williams 在 2011 年绕开了这条夹缝。

他不直接对 NP 完全函数做组合下界，而是证明：若 NEXP 有 ACC$^0$ 电路，则 NEXP 的非确定性时间可以被加速，与已有的层次定理冲突。

工具是电路可满足性算法——比穷举稍快的 SAT 求解，在计数指数时变成下界。这是「算法推出下界」的现代范式：你不必手搓随机限制，你让稍快的算法自己产生矛盾。

后续工作把类似技术推到 ACC$^0$ 的准多项式规模、以及部分 TC$^0$（多数票门）边界。P/poly 与 NP 的分离仍然没有。Williams 自己强调：ACC$^0$ 下界离 P vs NP 还有好几层均匀性与深度。

算术电路是平行的一条线。Valiant 的 VP vs VNP 把行列式与积和式（permanent）放在代数版本的 P vs NP 位置。Raz 对多层算术公式给出下界；积和式对行列式的单调或无限制公式深度，仍是开放问题。

布尔与算术两条线会借用多项式方法，但归约不自动翻译。

机制：随机限制怎样把浅电路切成决策树#

随机限制是 AC$^0$ 下界的发动机。对每个输入比特，以概率 $p$ 保持自由，否则均匀随机钉成 0 或 1。深度 1 的大扇入与门在限制后极容易变成常数 0：只要一个输入被钉死为 0。

或门对称地容易变成常数 1。Håstad 的切换引理说：经过一层合适的限制，浅层电路以高概率变成小深度决策树。

决策树再被吸收进下一层，深度就少一层。对奇偶函数，无论怎么限制，剩下的自由变量上仍是奇偶——它不会塌成常数，除非自由变量被钉光。

于是深度 $d$、规模 $s$ 的电路无法计算奇偶，除非 $s$ 对 $d$ 指数爆炸。这给出近似紧的权衡：奇偶的 AC$^0$ 电路规模必须是 $\exp(\Omega(n^{1/(d-1)}))$。

Yao 更早用类似限制处理了深度有界电路；Håstad 把概率钉到可以写进教科书的常数。关键工程含义是负面的：这套技术依赖「无界扇入的与或门很容易被钉死」。

一旦允许 MOD$_2$ 门，奇偶自己就是一个门，限制不再让电路变笨。这就是为什么 AC$^0$ 成功、ACC$^0$ 长期停住。公式（fan-in 2 的树）有另一套下界：Nechiporuk、Khrapchenko、Karchmer–Wigderson 通信游戏，给出的仍是超线性而非指数。

显式函数的一般电路下界，到 2020 年代仍常停在 $5n$ 或略高的线性倍数。

机制：多项式方法、MOD 门与单调脚手架#

Smolensky 把布尔函数看成有限域 $\mathbb{F}_p$ 上的多项式。常数深度、带 MOD$_p$ 的电路，能计算的函数可被低次多项式逼近。MOD$_q$（$q\neq p$ 为素数）与所有低次多项式的距离都大。

维数计数完成下界：多项式空间的维度不够塞进目标函数。这是线性代数，不是门的图画。Razborov 更早对 MOD$_2$ 用过类似近似。

方法的边界同样清楚：同一素域上的 MOD 门，近似次数不再帮忙。单调电路是另一副脚手架。不许用否定时，团的指示函数必须「看见」足够多的边组合。

Razborov 用单调近似来挡住这些组合；Alon–Boppana 把界推到 $\exp(\Omega(k^{1/3}))$ 一类规模，针对 $k$-团。Tardos 给出一个单调函数，其单调电路指数大、一般电路却多项式小。

因此单调下界不能直接搬到 P vs NP：否定会拆掉证明用的格。Valiant 的 VP / VNP 把战场换到代数。行列式有多项式规模算术电路；积和式被相信没有。

若 VNP 不包含于 VP，代数版的 P ≠ NP 就成立——仍未证明。布尔归约与代数归约不自动互译：把 SAT 写成多项式，次数和系数会把规模吹爆。

两条线共用「低次对象逼近不了目标」这一句，对象一个是 $\mathbb{F}_2$ 上的多项式，一个是特征零上的行列式。

机制：电路 SAT 稍快，层次定理就变成下界#

Williams 的策略是把上界算法倒过来用。假设 NEXP 有多项式规模的 ACC$^0$ 电路。那么对指数长的输入，验证一个非确定性计算，可以先猜一张小电路，再问这张电路是否可满足。

若 ACC$^0$-SAT 比穷举快一点——比如 $2^n/n^{\omega(1)}$——加速会把 NEXP 的时间层次压扁，与已知的层次定理冲突。因此 NEXP 不能有 ACC$^0$ 电路。

2011 年的突破不在于发明新的随机限制，而在于给 ACC$^0$ 找到了这种「稍快」的 SAT 算法。

工具包括快速矩阵乘法味道的求值、以及 Beigel–Tarui 把 ACC$^0$ 写成准多项式的对称函数加 SYM+ 电路。后续论文把规模从多项式推到准多项式，并把技术推向 TC$^0$ 的弱片段。

这套范式的代价是：你得到的下界，恰好卡在你能加速的那个电路类上。对一般 P/poly，没有足够快的电路 SAT 算法；一旦有，许多分离会一起掉下来，目前没人做到。

它也解释了与自然证明的关系：算法推出的下界不必「对随机函数建设性地成立」，因此不一定触发 Razborov–Rudich 的伪随机破坏。

Allender、Williams 等人反复强调：ACC$^0$ 仍只是常数深度。对数深度的 NC$^1$、以及 P 本身，中间还隔着 TC$^0$ 是否等于 NC$^1$ 这类开放问题。把 2011 年读成「P vs NP 已有组合进展」，会把层次差了好几层的类叠在一起。

线性规模下界是另一条几乎不依赖深度限制的战线。对显式函数，已知的一般电路下界长期停在 $3n$、$4n$、$5n$ 这种把加法器或对称函数拆开的倍数。

Iwama、Lachish、以及后来的工作以「门」为单位推进，一年可能只多一个 $n$ 的系数。它对 P vs NP 没有威胁，但说明：不限制深度时，组合方法目前只能碰到线性。

密码学把「没有小电路」写成假设，而不是写成已证定理；电路复杂度同时给证明者和假设提供者打工。

工程现场：深度、扇入与并行预算#

香农的计数可以写成工程尺。$n=6$ 时已有 $2^{64}$ 个布尔函数；规模 $s$ 的电路大约 $s^{O(s)}$ 种。要覆盖所有函数，$s$ 必须到 $\Omega(2^n/n)$。非显式下界因此是指数。显式下界到 2020 年代仍常停在 $5n$。五十年的缺口就卡在「几乎所有」变成「这一条」。

把 AC$^0$ 读成「硬件很浅所以算不了奇偶」，会立刻碰到扇入。数学上的无界扇入 AND 在硅片上是一棵树，深度变成 $\Theta(\log n)$。复杂度类里的深度不计这棵树；芯片里的延迟必须计。

并行算法更关心 NC。NC$^i$ 是多项式规模、深度 $O(\log^i n)$、扇入有界的电路。矩阵乘法、排序的平行版本，目标是 $\mathrm{polylog}$ 深度和多项式处理器。

若问题是 P 完全的，NC 算法在标准假设下不存在，多核只能把常数改善。这和 计算复杂性理论 里「P 等于易」的口号会打架：对并行预算，P 内部仍有不可能。

电路 SAT 的工程味道更直。Williams 用的「略快于 $2^n$」并不是工业 SAT 求解器 的 CDCL。后者吃的是有结构的 CNF；前者必须对最坏情况的 ACC 电路成立，加速只是 $2^{n-\Omega(n^\delta)}$ 这种亚指数缝。

把 Kissat 的跑分当成电路下界，类型又错了。下界要的是对所有输入都成立的算法改进，不是工业均值。线性规模下界的工程含义几乎为零。$5n$ 个门挡不住任何实际综合预算。它的价值全在证明技术：无深度限制时，我们连 $n\log n$ 都推不动。

量子计算理论 有自己的电路。BQP 是否包含于 P/poly 仍开放；量子查询下界不自动给出经典门数下界。把量子加速读成「经典电路一定很大」是类型错误。

Håstad 切换引理的定量形状决定了后续所有浅电路结果。限制密度 $p$ 太小，奇偶被钉死，下界变弱；$p$ 太大，电路不塌缩。引理给出的是一条可计算的概率曲线，不是一句「随机钉死就行」。

多项式方法能处理 MOD 门，却处理不了同样的深度–规模曲线，所以两套工具并存。公式与电路的差别也是工程尺。公式禁止共享子计算，fan-out 为 1，于是 Andreev 函数能把公式规模推到 $n^{3-o(1)}$。同一函数的电路规模下界仍是线性。综合器里的公共子表达式删除，正是在把公式往电路推；复杂度纪录提醒：共享一旦被禁止，下界会立刻跳一档。

代价与争议#

电路下界的成功几乎都发生在「加了限制的模型」：常数深度、单调、有限扇入、线性尺寸。一拿掉限制，已知的显式下界往往掉到 $4n$ 或 $5n$ 这种线性倍数，对 P vs NP 没有威胁。

Allender 等人长期维护「线性电路下界」的纪录，进展以门计算。非均匀性也让障碍更滑。即使 NP 不包含于 P，仍可能 NP 包含于 P/poly——那将意味着 SAT 有多项式电路，只是找不到均匀算法。

Karp–Lipton 定理说：若 NP ⊆ P/poly，则多项式层次塌到第二层。密码学更不希望 SAT 有小电路。电路复杂度于是同时服务于「证明难」和「假设没有小电路」。

与物理极限的类比要小心。Landauer 原理限制的是擦除一比特的能量，不直接给出 AC$^0$ 下界。把热力学写成复杂度证明，通常是比喻。

真正的物理约束见 计算的物理极限；电路类是离散数学。

硬件工程师关心的扇出、线延迟、功耗，也不会翻译成 AC$^0$ 的组合深度。一张深度 4、扇入无界的电路，在硅上可能根本布线不成；复杂度下界仍然成立，只是对象不是芯片净表。

自然证明障碍还留下一条工程提醒：若你的下界技术对随机函数也有效，它可能已经强到能区分伪随机发生器。硬度换随机性的正向用法见 Nisan–Wigderson 1994：足够硬的函数可以做成生成器，去骗多项式时间测试。指数电路硬度把均匀 $P=\mathrm{BPP}$ 收成条件句，见 Impagliazzo–Wigderson 1997。

电路下界论文因此会主动声明「不自然」：要么不建设性，要么对随机函数失败。这不是谦虚，是避免把密码学的候选发生器一并拆掉。

TC$^0$ 与 ACC$^0$ 的下界进展也说明：加一种更强的门，旧技术就停。多数票门能算加法，于是「浅层电路很弱」这句话必须带上允许的门集。读论文标题里的类名，比读「我们证明了电路下界」这句摘要重要。P vs NP 仍然隔着均匀性、深度和门的种类好几层；把 Williams 的 NEXP 结果说成即将解决千年问题，是把最远的一次航行当成已经上岸。

跨域连接#

• 证明：切换引理和自然证明都是关于证明技术的元定理。前者给出可计算的塌缩概率，后者指出一类证明若太「自然」就会破坏伪随机。Williams 的路线则把「稍快的算法」写成反证法的燃料。电路复杂度因此不只生产下界，还生产「哪些证明策略从一开始就走不通」的地图，和 P vs NP 障碍文是同一条反思链：先问方法会不会自毁，再问结论是否成立。
• 线性代数：多项式方法把布尔函数看成有限域上的多项式，再用次数和维数来挡浅电路。Smolensky 的 MOD 门下界、以及后来的近似次数界，本质是线性空间里的维数计数：低次多项式张成的子空间塞不进目标函数。算术电路里的行列式，同样是代数复杂度的线性代数对象。电路看起来像门，论证往往在向量空间里完成。
• 信息哲学：非均匀电路把「忠告」写成可以随 $n$ 变化的额外比特。这逼问一条认识论上的缝：知道一张表，与知道生成这张表的规则，是不是同一种知识。P/poly 把这道缝变成复杂度类。Karp–Lipton 进一步说：若 SAT 只存在于表里、不存在于均匀算法里，多项式层次会塌。哲学上的「知道」在这里有两种可分开的数学化。
• 热力学定律：可逆计算与门的擦除代价常被拉来解释「为什么计算要耗能」。那条物理账约束的是实现，不是 AC$^0$ 的组合深度。Landauer 界限按比特擦除计能量，不按与门扇入计深度。把热力学定律读成电路下界，会把两种完全不同的「不可能」叠在一起；能借的只是「不可逆操作必有代价」这一层类比，证明仍得在有向无环图上做。

参考文献#

• Shannon, C. E. "The Synthesis of Two-Terminal Switching Circuits." Bell System Technical Journal 28(1):59–98, 1949.
• Furst, M., Saxe, J. B. & Sipser, M. "Parity, Circuits, and the Polynomial-Time Hierarchy." Mathematical Systems Theory 17:13–27, 1984.
• Håstad, J. "Almost Optimal Lower Bounds for Small Depth Circuits." Proceedings of STOC, 1986; 见其博士论文与后续专著。
• Razborov, A. A. "Lower Bounds on the Monotone Complexity of Some Boolean Functions." Doklady Akademii Nauk SSSR 281:798–801, 1985.
• Smolensky, R. "Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity." Proceedings of STOC, 1987.
• Razborov, A. A. & Rudich, S. "Natural Proofs." Journal of Computer and System Sciences 55(1):24–35, 1997.
• Williams, R. "Non-Uniform ACC Circuit Lower Bounds." IEEE Conference on Computational Complexity, 2011; Journal of the ACM 61(1), 2014.
• Valiant, L. G. "Completeness Classes in Algebra." Proceedings of STOC, 1979.
• Ajtai, M. "$\Sigma^1_1$-Formulae on Finite Structures." Annals of Pure and Applied Logic 24(1):1–48, 1983.

延伸阅读#

• Arora, S. & Barak, B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 第十四章。
• Allender, E. 等关于电路下界纪录的综述与公开笔记（持续更新线性规模下界）。