复杂性类 NC¹

$N{C}^1$ 允许多项式数量的局部门并行工作，但从任何输入到输出只经过对数轮依赖。二元扇入意味着一层最多把可影响范围扩大一倍；经过 $\log n$ 层，信息刚好可以从全部 $n$ 个输入汇聚到根。它因此位于“局部常深计算”与一般多对数深并行之间，是表达式求值、有限状态组合和通信式下界频繁相遇的一层。

公式刻画揭示了一个容易忽视的事实：NC¹ 电路虽然可以共享子计算，但深度太浅，展开所有根到叶路径至多产生多项式多个叶；共享不会在这一深度范围内造成指数于 $n$ 的爆炸。反之，一棵多项式大但极瘦的公式可由平衡化压到对数深。这个双向转换是结构定理，不等于每个给定电路与给定公式具有相同大小。

$n$ 位奇偶函数可由二输入 XOR 的平衡树计算。每个 XOR 用常数多个 AND/OR/NOT 门替换，整族大小 $O(n)$、深度 $O(\log n)$，所以 parity 属于非一致乃至标准 uniform $N{C}^1$。对 $n=8$，三层 XOR 树依次合并四对、两对和最后一对输入；翻转任一输入都会沿唯一父链翻转根值。相比之下，parity 不属于 AC⁰公理库Parity 不属于 AC⁰Parity not in AC0 · AC0 parity lower bound证明任何多项式规模、常数深度、无界扇入 AND/OR/NOT 电路族都不能计算奇偶函数。，差别来自对数深度而非规模。

有界扇入不可删。若允许无界 AND/OR，常数深度得到 AC 类；若允许无界多数门，得到 TC⁰。已知

但目前不能把后两条包含写成严格分离。标准一致性下还有 $N{C}^1\subseteq L\subseteq NL\subseteq N{C}^2$；这不证明 $N{C}^1=L$，也不能套给任意非一致电路族。把深度写成 $O({\log }^{2}n)$ 会进入 $N{C}^2$，不再是本层。

$N{C}^1$ 是布尔公式、并行算法和群程序之间的枢纽。Karchmer–Wigderson 博弈公理库Karchmer–Wigderson 博弈Karchmer-Wigderson game · KW game · Karchmer-Wigderson relation让一方持有真输入、另一方持有假输入并寻找分歧坐标的通信搜索关系。把最小公式深度翻译为确定性通信位数，因此对该搜索关系的通信下界会直接成为 NC¹ 公式深度下界。Barrington 定理又把非一致 NC¹ 刻画为多项式长度、常宽分支程序，说明看似很窄的顺序模型仍能承载完整 NC¹；该结论需要单独的群论构造，不能从定义直接读出。

在包含关系上，TC⁰公理库复杂性类 TC⁰TC0 · TC^0 · Threshold circuit class由多项式规模、常数深度、无界扇入多数门电路族计算的布尔函数类。通过把常数层无界 threshold 门模拟为对数深有界扇入电路落入 NC¹，而 NC¹ 自身在标准一致口径下落入对数空间。工程上“对数延迟”仍不保证实际快速：门数、布线、常数和生成电路的成本都被抽象化；复杂度结论只描述随输入长度增长的资源上界。