基本复杂度类包含链

基本包含链来自“更多资源或更强选择不会让机器变弱”：每一步都把较受限的确定性计算当作非确定性等较宽松模型的特例，或用更多时间确定性地遍历原模型的有限搜索空间。空间可以复用，而多项式空间机器的配置数至多指数。链上的箭头来自这些模拟，大多只是上界关系，并不意味着相邻类已知严格分离；读图时应同时记住哪些等号未知、哪些严格性已有层级定理支撑。

已知 $\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}$ 都仍是开放问题。

具体而言，$NL\subseteq P$ 可通过显式搜索多项式大小的配置图，$NP\subseteq PSPACE$ 可深度优先遍历非确定计算树而复用空间，$PSPACE\subseteq EXP$ 则由多项式空间的指数配置上界得到。目前不知道 $L$ 是否等于 $NL$、$P$ 是否等于 $NP$、$NP$ 是否等于 $PSPACE$；已知 $P\ne EXP$，但这不能指定链中究竟哪一个相邻包含严格，只能说明至少有一处必须严格。

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

链把 L公理库复杂度类 LComplexity class L · Deterministic logspace可在确定性对数空间内判定的语言类。、NL公理库复杂度类 NLComplexity class NL · Nondeterministic logspace可在非确定性对数空间内判定的语言类。、P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。、NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。、PSPACE公理库复杂度类 PSPACEComplexity class PSPACE可由确定性图灵机在多项式空间内判定的语言类。 与 EXP公理库复杂性类 EXPEXPTIME · EXP可由确定性图灵机在单指数时间内判定的语言类。 放在同一资源坐标上。Savitch 定理、时间/空间层级定理和完全问题分别解释其中若干箭头与分离；研究具体问题时，找到最小可信上界通常比只说“可判定”更有信息。