AC⁰

$A{C}^0$ 允许每一层聚合大量 bit，但只允许固定轮数的信息组合。无界扇入带来宽度，常数深度限制传播轮次；多项式规模则阻止把指数真值表全部铺开。它是小深度并行计算的基本模型，也是研究“哪些全局模式无法由少数局部聚合层表达”的试验场。

与 bounded-fan-in 的 $N{C}^0$ 相比，无界门是关键差别；与允许多数门的 $T{C}^0$ 相比，门基又更弱。只比较“都是常数深度”会遗漏真正决定表达能力的 fan-in 和门类型。

$n$ 位 OR 由一个无界扇入 OR 门计算，大小与深度都是常数。两个 $n$ bit 字符串相等可写成

忽略输入文字上的 NOT 层时，先用 $2n$ 个 AND 门计算两个同值情形，再用 $n$ 个 OR 门求逐位相等，最后用一个无界 AND 汇总，共 $3n+1$ 个门、三层深度。若把 NOT 也计门和层，只多出 $O(n)$ 个门及一层，因此仍是常数深度和线性大小，并可按规则统一生成。这个例子展示了无界顶层 AND 如何一次汇总所有逐位比较，而不是暗示任意全局函数都同样容易。

奇偶函数 $\mathrm{PARITY}(x)=x_1\oplus \cdots \oplus x_n$ 不属于非一致 $A{C}^0$；这是需要 switching lemma 等工具证明的电路下界，不是从定义直接看出的事实。若深度允许增长为 $O(\log n)$，用二输入 XOR 树即可计算 parity；因此把“常数”悄悄改成对数会跨出本类。

允许任意真值表门也会使定义失效：一个超级门就能计算任意函数。门基必须固定为 AND/OR/NOT，且大小、深度与一致性约定同时给出。DLOGTIME-uniform 结论也不能无标记地套到任意非一致族上。

$A{C}^0$ 用于刻画极浅布尔电路、数据库一阶查询和有限模型论中的局部表达能力。它的显式下界说明，即使电路可以使用多项式多个无界门，常数层数仍无法组合出某些简单描述的全局性质。

该类建立在布尔电路理路布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。的门图之上，由规模、深度和一致性三组参数共同确定。比较 $A{C}^0$、$N{C}^0$、$AC{C}^0$ 或 $T{C}^0$ 时，应逐项核对门基、fan-in、深度和 uniformity，而不是只比较缩写。

PARITY 的完整下界证明理路Parity 不属于 AC⁰Parity not in AC0 · AC0 parity lower bound逐层核算独立随机限制、决策树转换与失败概率，在保留自由变量的同一实验中证明 PARITY 的常深电路指数下界。允许共享子电路的 DAG，明确处理推入 NOT、再次裁剪、交替分层和线路补门；再以底层宽度与非底层门数为不变量，逐次核算随机限制的失败概率。最终得到每个固定深度的指数规模界，而非只对公式树或一致电路成立。