空間階層定理（space hierarchy theorem）

空間階層定理是時間階層定理的記憶體孿生兄弟，而且若論起來甚至更乾淨。它說真正更多的草稿記憶體能讓機器判定嚴格更多的語言。給機器一條更大的工作帶，就會有些問題它現在能解、而任何記憶體更小的機器都永遠辦不到。這是我們真能證明的少數分離之一，是那張原本充滿猜想的複雜度類別地圖底下的堅實地面。

形式上，若 f 與 g 是空間可構造的，且 g(n) 是 o(f(n))（f 成長嚴格更快，這次不需要任何 log 額外開銷），則 SPACE(f(n)) 嚴格包含 SPACE(g(n))。證明又是對角線論證，這次用的是空間計數器而非時鐘。建造一台機器 D，模擬給定機器 M 跑在 M 自己的描述上，同時標出恰好 f(n) 個格子並拒絕用更多；若 M 在那個空間內停機並接受，則 D 拒絕，否則 D 接受。於是 D 需要略多於 g(n) 的空間，並在每台 g(n) 空間機器自己的程式碼上與之相左，所以 D 的語言屬於 SPACE(f) 卻不屬於 SPACE(g)。空間不需要額外 log 因子（不像時間）的原因，是模擬一台機器幾乎不花記憶體開銷，你可以直接重用被模擬的紙帶。

由此我們得到堅如磐石的空間分離：L 嚴格包含於 PSPACE、PSPACE 嚴格包含於 EXPSPACE，且一般而言空間階梯永遠往上爬。這些都是定理，毋庸置疑。誠實的提醒，而且很重要：階層定理分離的是「同一種資源」的不同量（更多空間對更少空間）。它們並不分離空間與時間，也不分離確定型與非確定型，所以它們把招牌問題——如 L 是否嚴格在 P 之內、或 P 在 PSPACE 之內——完全留作未解。我們能證明階梯在單一資源內升高；跨資源比較才是我們工具用罄之處。