形式陈述

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

$${\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}$ 可由小空间模拟浅电路得到；$\mathrm{L}\subseteq \mathrm{NL}$ 是确定性到非确定性的直接包含；$\mathrm{NL}\subseteq {\mathrm{NC}}^2$ 可把配置图可达性写成布尔矩阵的重复平方；$\mathrm{NC}\subseteq \mathrm{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}$ 是否成立。

推论与应用

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

参考资料

• 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。