Parity 不属于 AC⁰

形式陈述 ​

令

$${\mathrm{PARITY}}_n(x_1,\dots ,x_n)=x_1\oplus \cdots \oplus x_n.$$

对任意固定深度 $d\ge 2$，存在只依赖 $d$ 的常数 $c_d>0$，使计算 ${\mathrm{PARITY}}_n$ 的深度 $d$、无界 fan-in AND/OR/NOT 电路大小至少为

$$\exp \left(c_d{n}^{1/(d-1)}\right).$$

因此不存在多项式规模常深电路族计算 parity，即 $\mathrm{PARITY}\notin$ 非一致 $AC^0$公理库AC⁰AC0 · AC^0 · Constant-depth unbounded-fan-in circuits由多项式规模、常数深度、无界扇入 AND/OR 门电路族计算的布尔函数类。。门基、无界 fan-in、固定深度和非一致模型都是结论的一部分；定量指数的常数取决于所用 switching lemma 版本。

证明骨架采用逐层随机限制。先把 NOT 推到输入层，使电路交替为 AND/OR 层。对底层应用switching lemma公理库Håstad switching lemmaHåstad's switching lemma · Switching lemma说明窄 CNF 或 DNF 在独立随机限制后，以指数高概率退化为浅决策树的结构定理。：选择足够小的自由概率 $p$，让每个底层子公式以高概率变成浅决策树；对至多 $S$ 个门作 union bound，若 $S$ 小于目标指数界，可同时简化整层。把浅树展开并吸收到上一层，重复 $d-1$ 次，最终受限电路以高概率成为深度小于剩余自由变量数的决策树或常量。另一方面，限制仍以高概率留下许多自由变量，而 parity 在固定其余变量后仍等于这些自由变量的 parity 或其否定，必须查询每个自由变量。两种结论矛盾，从而推出大小下界。

直觉 ​

浅 AND/OR 公式在随机固定后会迅速塌缩，因为一个决定性输入就能杀死或满足整扇门。Parity 对每个尚未固定的变量仍敏感：翻转任一自由 bit 都翻转输出，因此无法被少量查询或常量替代。随机限制让“电路易塌缩、parity 不塌缩”的差异变成下界。

证明不是说 parity 直观上“全局”所以很难；关键是同一个 restriction 同时简化所有多项式多个门，并保留足够自由变量。规模阈值正来自 switching 失败概率与 union bound 的平衡。

例子与边界 ​

深度二的 DNF 若精确计算 parity，每个满足项必须固定全部 $n$ 个变量：只要某项留下一个变量自由，该项就会同时接受一对奇偶性相反的输入。因此需要为 $2^{n-1}$ 个奇 parity 赋值各放一个完整项，得到指数大小。高深度情形不能直接复用这一计数，switching lemma 负责把受限多层电路逐步降到类似局面。

Parity 有大小 $O(n)$、深度 $O(\log n)$ 的二输入 XOR 树，所以结论不排除对数深度。若把 XOR 直接加入门基，一个无界 XOR 门甚至一层即可计算；带多数门的 $T{C}^0$ 也不受本定理约束。下界针对常深 AND/OR/NOT，不是“所有常深电路”。

一致性不是此下界的漏洞：定理已经排除更强的非一致电路族，自然也排除其 uniform 子类。但它不推出 parity 需要超多项式一般电路，也不解决 $P$ 与 $NP$。

推论与应用 ​

Parity 下界是显式函数常深电路下界的基准，展示了随机限制、结构简化和敏感函数之间的证明范式。类似方法可处理某些 $MO{D}_q$ 与近似下界，但门基改变后需要新的技术。

它也说明 $A{C}^0$ 的无界 fan-in 并未消除常数深度限制：OR、AND 可一层汇总全部 bit，仍无法在固定层数内组合出 parity 的模二依赖。

参考资料

• Johan Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987, Chs. 3–4.
• Merrick Furst, James B. Saxe, and Michael Sipser, “Parity, Circuits, and the Polynomial-Time Hierarchy,” Mathematical Systems Theory 17, 1984, pp. 13–27.