复杂性类 ACC⁰

MOD 门一次读取全部输入，却保留的不是“有没有”或“是否全有”，而是汉明重量绕固定周期的位置。它为常深电路增加一种真正全局的周期感：无论输入多长，一层门都能分辨总数是否落在某个模剩余类。AC⁰ 无法计算 parity，恰说明仅靠 AND/OR 的固定轮聚合不能恢复这种周期结构。

固定模数是定义的核心。若允许 $m=m(n)$ 随长度任意变化，门本身可能携带越来越复杂的计数规则，所得模型不是标准 ACC⁰。相反，同一固定 $m$ 的门在任意大 fan-in 上工作，强度来自无界汇总，而不是为每个输入长度换一个新模数。

对八位输入 $11011110$，汉明重量是 $6$，所以按本页约定 ${\mathrm{MOD}}_6$ 门输出 $1$；把最后一位改为 $1$ 后重量为 $7$，输出 $0$。${\mathrm{MOD}}_2$ 直接判定偶重量，其否定就是 parity，因此 parity 属于 ACC⁰。结合parity 不属于 AC⁰公理库Parity 不属于 AC⁰Parity not in AC0 · AC0 parity lower bound证明任何多项式规模、常数深度、无界扇入 AND/OR/NOT 电路族都不能计算奇偶函数。，得到无条件严格包含 $A{C}^0⊊AC{C}^0$。

这条例子不能推广为“所有计数都在 ACC⁰”。多数函数是否属于非一致 ACC⁰ 仍是著名开放问题；允许 majority 后才按定义进入 TC⁰。Razborov–Smolensky 多项式法能分离若干互素模数的 $A{C}^0[p]$ 类，却不能处理 ACC⁰ 中任意复合模门的全部组合。特别是从 ${\mathrm{MOD}}_q\notin A{C}^0[p]$ 不能推出 ${\mathrm{MOD}}_q\notin AC{C}^0$。

门输出余数等于零或非零、是否同时允许多个固定模数，都只造成常数层模拟；深度若随 $n$ 增长、模数若随 $n$ 增长或规模若超多项式，则会越出本类。uniform 算术结论也不得无标签套给任意非一致族。

$AC{C}^0\subseteq T{C}^0$ 来自 threshold 电路的常深计数能力：固定模数的余数可由多项式规模多数门网络求出。再结合 $T{C}^0\subseteq N{C}^1$，得到 ACC⁰ 的一般上界；目前两处是否严格都未知。与 AC⁰ 相比，MOD 门又使 switching lemma 的直接逐层简化失效，迫使下界研究转向低次多项式、相关界和算法方法。

Ryan Williams 通过比穷举更快的 ACC⁰-Circuit-SAT 算法与时间层级论证，证明 $NEXP⊈AC{C}^0$。这是一项一般非一致 ACC⁰ 下界，但它给出的困难语言位于很高复杂度类，并未解决多数函数或 NP 是否具有 ACC⁰ 电路。该结果也说明电路可满足性算法公理库电路可满足性问题Circuit satisfiability problem · Circuit-SAT给定编码后的布尔电路，判断是否存在输入赋值使其输出为真的 NP 完全问题。为何会反过来产生电路下界。