AC⁰

形式陈述 ​

$A{C}^0$ 电路使用无界 fan-in 的 AND、OR 门与 NOT 门；按常用正规形，NOT 只直接作用于输入。电路族 $\{C_n\}$ 属于非一致 $A{C}^0$，若存在常数 $d,c$，使每个 $C_n$ 有 $n$ 个输入、深度公理库电路规模与深度Circuit size and depth分别计数门数和最长输入到输出路径长度的电路资源度量。至多 $d$、大小至多 $n^c$。常数 $d,c$ 可以依赖整族，却不能随 $n$ 增长。

无界 fan-in 表示一个门可同时读取随 $n$ 增长的多个输入；它让 $n$ 位 AND 或 OR 在一层完成。NOT 门移到输入层不改变该类，因为 De Morgan 律可以逐层对偶 AND/OR。若额外要求 direct-connection language 可在 $O(\log n)$ 时间查询，得到 DLOGTIME-uniform $A{C}^0$；若不加要求，默认是非一致公理库电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。版本，二者的标签不能省略。

直觉 ​

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

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

例子与边界 ​

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

$$\underset{i=1}{\overset{n}{\bigwedge }}((x_i\wedge y_i)\vee (\mathrm{\neg }{x}_i\wedge \mathrm{\neg }{y}_i)),$$

它具有常数深度和线性大小，并可按规则统一生成。这个例子展示了无界顶层 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，而不是只比较缩写。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Ch. 14, circuit complexity.
• Johan Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987, Chs. 1–3.