并行复杂度类包含链

形式陈述

对标准的对数空间一致、有界扇入电路族，

\mathrm{NC}^1\subseteq\mathrm L\subseteq\mathrm{NL} \subseteq\mathrm{NC}^2\subseteq\mathrm{NC}\subseteq\mathrm P.

$\mathrm{NC}^1\subseteq\mathrm L$ 可把输出向输入展开为深度 $O(\log n)$ 的树来求值，而不把树存下来：每层只记所选孩子、访问阶段和一个已算出的 bit，整条路径共 $O(\log n)$ 位。需要某个门编号时，从输出沿这条路径重新查找，并复用对数空间的一致生成器；不必在每层都压入一个 $O(\log n)$ 位门编号。 $\mathrm L\subseteq\mathrm{NL}$ 是确定性到非确定性的直接包含； $\mathrm{NL}\subseteq\mathrm{NC}^2$ 可把多项式大小配置图的可达性写成布尔矩阵的重复平方：先加自环，每次平方把路径长度预算加倍。一轮的每个矩阵元是多项式项的 OR，各项为两个 bit 的 AND，有界扇入展开后深度为 $O(\log n)$ ；共 $O(\log n)$ 轮仍只用多项式门，深度为 $O(\log^2 n)$ 。 $\mathrm{NC}\subseteq\mathrm P$ 则按拓扑序求值多项式规模电路即可。

直觉

并行包含链把低空间与浅电路联系起来：对数空间算法只能保留少量状态，却可反复读取输入；浅电路则允许大量门并行工作。配置图把两种资源模型接到同一个可达性问题上，使小空间机器能展开为多项式规模电路，浅一致电路又能用有限空间逐门求值，低空间计算因而可转写成多对数深度的并行计算。NC 位于“高效并行”一侧，P 位于“高效串行”一侧；是否二者相等未知，因此 P 完全性常被当作本质串行性的证据而非定理。

例子与边界

这条链依赖一致性约定；非一致电路可能把难以计算的信息直接编码进电路族。 $\mathrm{NC}$ 是所有固定 $k$ 的 $\mathrm{NC}^k$ 之并，不能从 $\mathrm{NC}^1\subseteq\mathrm L$ 推出 $\mathrm{NC}\subseteq\mathrm L$ 。目前不知道 $\mathrm L=\mathrm{NL}$ 或 $\mathrm{NC}=\mathrm P$ 是否成立。

若把 AC 纳入比较，常见的细化关系为 $NC^1\subseteq L\subseteq NL\subseteq AC^1\subseteq NC^2\subseteq P$ ，并有 $NC=\bigcup_k NC^k\subseteq P$ 。例如 logspace-uniform 浅电路可由多项式时间机器按拓扑顺序求值；反向模拟时，空间受限机器的配置图可被并行可达性电路处理。

具体链随 uniformity、fan-in 和类的定义略有版本差异，不能只看符号名称。 $NC\subseteq P$ 不意味着现实中所有 NC 算法都更快；处理器限制与通信成本不在抽象电路深度中。

推论与应用

该链把“内存很少”“可高度并行”和“多项式时间”放到同一坐标系中，也是用 P 完全性解释问题可能难以有效并行化的基础。

NC、L、NL 与 P 共同构成并行复杂度坐标。一致性是把电路链与机器链对齐的关键，P 完全问题则用于检验某个多项式时间任务是否可能落入 NC。

参考资料

Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory, Oxford University Press, 1995，Chs. 2–4。
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 4 and 6。

形式陈述 ​

反向链接

形式陈述