Parity 不属于 AC⁰

AND 和 OR 常被少数固定值决定；PARITY 则保留每一个未赋值变量的影响。翻转任一自由比特必翻转答案，因此只要还有一个自由变量，受限 PARITY 就不可能是常量。

困难是让同一随机限制既简化全部必要的门，又留下自由变量。逐层“存在一份好限制”还不够：选择好限制会改变剩余变量的分布。下面先抽完一个明确的独立随机实验，再用并合界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。同时控制结构失败和没有自由变量的事件。

深度二的完整证书 ​

若一个 DNF 精确计算 PARITY，其每个可满足合取项必须包含全部 $n$ 个变量。否则在满足该项的赋值中，翻转一个未出现变量仍满足 DNF，却改变奇偶值，矛盾。因此每项至多覆盖一个奇赋值，而奇赋值有 $2^{n-1}$ 个，至少需要这么多项。

例如三变量 PARITY 的四项为

四个 AND 加一个 OR，共五门、深度二。CNF 对偶地需要覆盖全部偶赋值。高深度的中间门不必直接决定最终答案，所以不能直接复制这个项计数证明。

三次限制的一条可见轨迹 ​

取一个用于观察简化的深度三电路

它本来就不是八变量 PARITY。依次施加以下具体限制：

这条轨迹中 $F$ 最终成为常量，而八变量 PARITY 变成 $1\oplus h$，依然需要查询 $h$。例子展示两种函数对同一限制的不同反应；它不以某条罕见轨迹代替下文对任意小电路的统一概率论证。

一份具体的参数预算 ​

对假想的三层正规电路取 $d=3,M=16$。则 $k=\lceil {\log }_4(384)\rceil =5$，三次自由概率分别为

总自由概率为 $q=1/200000$。若 $n=400000$，期望留下两个自由变量。前两个结构阶段的失败概率合计至多 $2\cdot 16\cdot 4^{-5}=1/32$，最后使输出成为常量的失败概率至多 $1/4$，没有自由变量的概率至多 $e^{-2}$。故同时“结构成功、输出常量、仍有自由变量”的概率至少

这与计算 PARITY 矛盾。大数值来自为清晰而选的保守常数，不表示小规模情形没有更强下界。

一般 DAG 如何变成分层电路 ​

先去掉不通向输出的门，并给每个 AND/OR 门同时构造正值和反值：De Morgan 对偶门读取输入的相反轨道。这样至多有 $2S$ 个 AND/OR 门，NOT 全移到文字上，不需要把共享 DAG 展开成树。

若同类门直接相连，用结合律旁路这条边：例如上层 AND 直接读取下层 AND 的所有输入。保留下层门供其他扇出使用，删除重复边，重复直至每条门到门边都连接相反类型。门数和最长路径均不增加；线路可能增多，下面明确给它留预算。选择实际输出对应的轨道，并再次删除不通向该输出的门。

把输出放在第 $d$ 层。对其余门 $v$，令 $\ell (v)$ 为从 $v$ 到输出的最长门间路径边数，放在第 $d-\ell (v)$ 层。沿任意路径门型交替，所以从同一 $v$ 到输出的所有路径长度奇偶相同；这保证同层门型一致。对边 $v\to w$ 有 $\ell (v)\ge \ell (w)+1$，且层差为奇数，故可在跨层边上插入交替的一输入恒等门。文字到门的边也从第一层开始补齐。若原深度小于 $d$，这同样把短路径补至给定层数，且不增加到 $d$ 之外。

计数时把 $2n$ 个正负文字及两个常量端点都纳入候选节点。去重后线路数至多

每条边插入少于 $d$ 个门，所以可统一取保守界

这里保留线路造成的二次开销，避免把“每条线补门”误说成只按原门数线性增长。对于最终的固定深度指数下界，这个多项式开销足够。[1]

决策树如何换成相邻层需要的形式 ​

深度小于 $k$ 的决策树可同时写成宽度小于 $k$ 的 DNF 和 CNF。对每个一叶子，把根到叶路径上的回答写成合取项，再对这些项取 OR；对每个零叶子，把“不能完全沿这条路径走下去”写成析取子句，再对这些子句取 AND。每条路径长度小于 $k$，所以宽度受控。空叶集合对应常量零或一。

展开可能产生很多新底层门。因此整个降深过程保留的计数不变量是：

底层门的宽度至多 $k$；底层以上的门数至多 $M$。

每次 switching 只需为当前第二层的至多 $M$ 个根门分别控制失败概率，不需要对新底层的每一个展开项再作同样的并合界。

第一次限制：只把底层变窄 ​

抽第一份限制，自由概率 $p_0=1/20$。每个底层 OR 可看成宽度一 DNF，每个底层 AND 可看成宽度一 CNF。取 switching 阈值 $t=k$，每个门失败概率至多

对至多 $M$ 个底层门并合，第一次结构失败概率至多 $M{4}^{-k}$。

若底层是 OR，把其浅树改写为 $k$-CNF；CNF 顶部的 AND 与原第二层 AND 合并，新的底层仍是 OR，但每个 OR 子句宽度至多 $k$。原第二层以上的门没有增多，深度仍至多 $d$。底层 AND 情形对偶。这一步只控制宽度，还没有把整个电路降一层。

中间 $d-2$ 次限制：每次降低一层 ​

以下每份新限制的自由概率都取

固定此前的任意成功历史，当前第二层的每个根门连同它的底层输入，构成一个 $k$-CNF 或 $k$-DNF。新限制独立于历史，switching lemma 以 $t=k$ 给每个根门的条件失败概率至多

第二层根门至多 $M$ 个，因此该阶段条件失败概率至多 $M{4}^{-k}$。

例如当前是底层 OR、第二层 AND、第三层 OR。第二层的 $k$-CNF 经限制变成浅树，改写为 $k$-DNF，其顶部 OR 与原第三层 OR 合并。新的底层是 AND，宽度至多 $k$，底层以上只保留原第三层及更高层的门，总数仍至多 $M$；深度减少一。对偶情形相同。

重复 $d-2$ 次后，成功历史下只剩一份输出 $k$-CNF 或 $k$-DNF。任何中途已成为常量的电路可继续保持常量，后续随机实验仍照常抽取。

最后一次限制：只控制一个输出 ​

再以同一个 $p=1/(20k)$ 限制一次，但这次 switching 阈值取 $t=1$。因为只剩一个输出公式，不再需要对 $M$ 个门并合：

成功时决策树深度为零，即整个输出成为常量。这就是中间阶段取 $t=k$、最后取 $t=1$ 的区别；把最后也要求成深度小于 $k$，会迫使存活变量超过 $k$，损失这里想保留的 $d-1$ 指数。

在同一个随机实验中合并全部事件 ​

总共抽 $d$ 份限制：一份 $p_0$，随后 $d-1$ 份 $p$。每份只作用于当前仍自由的变量，固定值都是独立公平位。即使早期结构已经失败，也继续抽完这些限制；结构改写只用于分析，不改变随机实验。

每个变量最终自由当且仅当连续存活，概率为

不同变量使用独立随机选择，最终自由数严格服从 $X\sim \mathrm{Bin}(n,q)$。最终固定值仍公平，复合限制就是 ${\mathcal{R}}_q$。这是一条关于无条件实验的事实，不声称条件在此前结构成功后仍是同一二项分布。

设某一中间阶段为首次失败。条件在此前每一种成功历史，其失败概率都有上述统一界，故不条件化后该首次失败事件也至多 $M{4}^{-k}$。第一次控制宽度加上 $d-2$ 次降深，一共有 $d-1$ 个这样的阶段，合计至多

最后阶段首次失败至多 $1/4$。若 $n\ge 2\cdot {20}^d{k}^{d-1}$，则 $nq\ge 2$，且

再作一次并合界，同时结构成功、输出成为常量且 $X\ge 1$ 的概率至少

但原电路若计算 PARITY，其任意限制都计算剩余变量的奇偶或其否定。只要 $X\ge 1$，翻转一个自由位就改变输出，绝不可能是常量。这给出矛盾，证明有限参数界。

从有限参数界回到原门数 ​

因为 $k\le 1+{\log }_4(8dM)$，已证不等式推出

对固定 $d$，即 $M\ge \exp ({\mathrm{\Omega }}_d(n^{1/(d-1)}))$。结合 $M\le 10d(S+n+1{)}^2$，可得

当 $n$ 足够大，右端超过任意固定多项式，减去 $n+1$ 并适当缩小指数常数，得到形式陈述中的 $S\ge \exp \left(c_d{n}^{1/(d-1)}\right)$。小 $n$ 的门数由具体电路直接处理，不强行让同一个指数式覆盖零门可输出单个输入的退化情况。

门基、深度和一致性边界 ​

Parity 有线性规模、对数深度的二输入 XOR 树；每个二输入 XOR 可由常数多个 AND/OR/NOT 门实现，故这不违背常深下界。若直接把无界 XOR 加入门基，一个门就能计算；多数门模型 TC⁰ 也不受本证明的门型简化约束。

结论已排除更强的非一致电路族，因此也排除其 uniform 子类。它不推出 PARITY 需要超多项式的一般电路，也不解决 P 与 NP。推广到其他模门、带偏限制、平均错误或 multi-switching，需要相应的新引理和概率约定，不能仅换一个函数名。