形式陈述

$N{C}^k$ 通常由对数空间一致、大小 $n^{O(1)}$、有界扇入且深度 $O({\log }^{k}n)$ 的布尔电路族判定；$NC=\bigcup _{k\ge 1}N{C}^k$。多项式大小限制总工作量，多对数深度表示可在多项式处理器上高效并行。已知 $NC\subseteq P$，是否 $NC=P$ 未知；$N{C}^1\subseteq L\subseteq NL\subseteq N{C}^2$ 是常见包含链（取标准一致性约定）。

直觉

NC 捕捉“可以显著并行化”的问题：把大量局部操作同时做，只留下多对数轮依赖。它不是“使用多核就快一点”，而是渐近关键路径极短。

例子与边界

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

推论与应用

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

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012，Chs. 1–6。