并行复杂度类包含链

并行包含链把低空间与浅电路联系起来：对数空间算法只能保留少量状态，却可反复读取输入；浅电路则允许大量门并行工作。配置图把两种资源模型接到同一个可达性问题上，使小空间机器能展开为多项式规模电路，浅一致电路又能用有限空间逐门求值，低空间计算因而可转写成多对数深度的并行计算。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 纳入比较，常见的细化关系为 $N{C}^1\subseteq L\subseteq NL\subseteq A{C}^1\subseteq N{C}^2\subseteq P$，并有 $NC=\bigcup _{k}N{C}^k\subseteq P$。例如 logspace-uniform 浅电路可由多项式时间机器按拓扑顺序求值；反向模拟时，空间受限机器的配置图可被并行可达性电路处理。

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

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

NC公理库复杂性类 NCNick's Class · NC由多项式规模、复对数深度的统一布尔电路族判定的高度并行语言类。、L公理库复杂度类 LComplexity class L · Deterministic logspace可在确定性对数空间内判定的语言类。、NL公理库复杂度类 NLComplexity class NL · Nondeterministic logspace可在非确定性对数空间内判定的语言类。 与 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 共同构成并行复杂度坐标。一致性公理库电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。 是把电路链与机器链对齐的关键，P 完全问题则用于检验某个多项式时间任务是否可能落入 NC。