复杂性类 NC

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

两个 $n$ 位整数相加可用并行前缀电路在 $O(\log n)$ 深度、$O(n)$ 或近线性规模完成。二进制编码整数矩阵的乘法可并行计算各整数乘积与求和，许多树归约也属于 uniform NC。这里按全部输入位数计资源，并输出精确结果的有限位串；矩阵乘积的输出位长至多增加输入位长与矩阵维数的对数项，不把无限精度运算当作一门。一般电路值问题是 P 完全问题，被视为难以有 NC 算法的代表，但这并不是 $P\ne NC$ 的无条件证明。

这些例子沿用前述一致性与有界扇入约定：去掉一致性，电路可能携带不可计算建议；允许无界 AND/OR 扇入，则得到相应 AC 类。深度 $O({\log }^{k}n)$ 中 $k$ 必须是固定常数，不能随输入增长。GPU 上跑得快也不等于属于 NC：通信、缓存、内存带宽和有限处理器数量影响现实加速，而 NC 讨论随输入长度增长的理论规模与深度。

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 对照。