空间层级定理

空间层级定理通过对角化说明，可构造地增加工作空间会严格增加可判定能力：新机器列举较小空间程序，在输入编码某台机器时模拟并反转其答案，也就会在与自身编号对应的输入上故意不同，同时利用更大空间完成通用模拟。与时间层级相比，空间可复用使开销控制更直接；可构造性则保证机器能在给定输入长度上实际标记出允许空间。

由定理可得 $L⊊PSPACE$，因为对数空间远小于某个多项式空间界；更精确地存在语言位于 $\mathrm{DSPACE}(n)$ 而不在 $\mathrm{DSPACE}(\log n)$。定理不能直接证明具体自然问题的分离，只保证某个对角语言存在。若空间函数不可构造，机器未必能知道何时越界，对角化可能失效。Big-O 类之间必须有渐近间隙，不能从同阶函数推出严格包含。

特别地，$DSPACE(\log n)$ 严格包含于某些更大空间类，并由层级结果可推出 $L\ne PSPACE$。

定理需要满足技术条件，不能对任意振荡或不可计算的空间界直接套用。它证明的是存在某种语言需要更多空间，不意味着每个具体 PSPACE 完全问题都已获得精确空间下界。

空间层级定理证明空间复杂性不是人为记账：随着内存上界增长，语言类严格扩张，并为 L、PSPACE 及更高空间类提供无条件分离。

该结果建立在 确定性空间类公理库确定性空间复杂性类Deterministic space class · DSPACE由确定性图灵机在给定工作空间界内判定的语言集合。 与 空间复杂度公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。 上，给出 L公理库复杂度类 LComplexity class L · Deterministic logspace可在确定性对数空间内判定的语言类。 与 PSPACE公理库复杂度类 PSPACEComplexity class PSPACE可由确定性图灵机在多项式空间内判定的语言类。 的无条件分离。它与 时间层级定理公理库时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。 共同说明资源上界不是记号游戏，而确实形成严格计算能力层次。