复杂性类 NC

NC 把“可显著并行化”形式化为多项式数量处理单元在 polylog 时间内完成：大量局部操作同时进行，只留下多对数轮依赖；电路规模限制总工作，深度限制渐近关键路径。它不是“使用多核就快一点”。单纯拥有多项式时间算法不保证属于 NC，因为算法可能存在本质串行依赖；反过来，指数数量门即使深度常数也不算有效并行。通常还加入一致性，确保电路族可由小空间程序生成。

整数加法、矩阵乘法和许多树归约属于 NC；一般电路值问题是 P 完全问题，被视为难以高效并行化的代表。若去掉一致性，电路可能携带不可计算建议；若允许无界扇入，则得到 AC 类而非标准 NC。深度 $O({\log }^{k}n)$ 中 $k$ 是固定常数，不能随输入增长。NC 与现实加速还受通信、缓存和处理器数量影响。

两个 $n$ 位整数相加可用并行前缀电路在 $O(\log n)$ 深度、$O(n)$ 或近线性规模完成，属于 NC。矩阵乘法也可并行计算各乘积与求和。一般电路值问题是 P 完全问题，被视为难以有 NC 算法的代表，尽管尚不能由 $P\ne NC$ 无条件分离证明。

GPU 上跑得快不等于属于 NC：硬件常数、内存带宽和有限处理器数是工程指标；NC 讨论随 $n$ 增长的理论规模与深度。门基、fan-in 和 uniformity 不同会改变具体子类。

NC 提供并行可解性的理论基准，支撑 PRAM 算法、电路设计和 P 完全性分析，并把总工作量与并行时间同时纳入分类。

定义依赖 布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。、规模与深度公理库电路规模与深度Circuit size and depth分别计数门数和最长输入到输出路径长度的电路资源度量。 以及 电路族一致性公理库电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。。其层级 $N{C}^1,N{C}^2,\dots$ 按对数深度指数细分，并通过 并行复杂度包含链公理库并行复杂度类包含链Parallel complexity class containment chain · NC-L-NL containment chain标准一致性约定下 NC、L、NL 与 P 之间的包含关系。 与 L、NL、P 对照。