形式陈述

在标准图灵机模型下，

$$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{PSPACE}\subseteq \mathrm{EXP}.$$

$\mathrm{L}\subseteq \mathrm{NL}$ 与 $\mathrm{P}\subseteq \mathrm{NP}$ 来自确定性计算是非确定性计算的特例。对数空间非确定机器只有多项式多个配置，确定性搜索其配置图可得 $\mathrm{NL}\subseteq \mathrm{P}$。NP 验证器的多项式长证书可被逐一枚举而只复用多项式空间，故 $\mathrm{NP}\subseteq \mathrm{PSPACE}$。多项式空间停机计算的配置数至多为 $2^{\mathrm{poly}(n)}$，所以 $\mathrm{PSPACE}\subseteq \mathrm{EXP}$。

直觉

每一步都把较受限的计算当作较宽松模型的特例，或用更多时间确定性地遍历原模型的有限搜索空间。包含关系来自模拟，不表示相邻类别已经证明不同。

例子与边界

已知 $\mathrm{L}⊊\mathrm{PSPACE}$ 与 $\mathrm{P}⊊\mathrm{EXP}$，分别由空间层级定理公理库空间层级定理Space hierarchy theorem在适当空间可构造性条件下，更多渐近空间严格提升可判定语言能力。和时间层级定理公理库时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。推出。但这些端点分离不能确定链中哪一条相邻包含是严格的；例如 $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$、$\mathrm{NP}\stackrel{?}{=}\mathrm{PSPACE}$ 与 $\mathrm{PSPACE}\stackrel{?}{=}\mathrm{EXP}$ 都仍是开放问题。

推论与应用

这条链为问题分类提供快速上界传播：证明一个问题属于较小类，会自动得到其属于右侧所有较大类；证明它对某个右侧类别困难，则会限制它落入左侧类别的可能性。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–4。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 7–8。