同一本筆記本上的第二種資源
在上一階梯，你學會了用時間來衡量圖靈機——把讀寫頭的基本動作當成輸入長度 n 的函數來計數，取最壞情況，再用大 O把常數抹平。時間是計算所花的兩種自然資源之一。另一種是記憶體：機器在停機前在紙帶上塗寫了多少格。一台機器可以又快卻很耗紙，也可以又慢卻很省。於是我們現在問一個平行的問題——不是它要花多久？而是它需要多少空間？——而答案就是空間複雜度。
這套設定令人安心地熟悉。正如時間複雜度是一個函數 T(n)，空間複雜度也是一個函數 S(n)：在所有長度為 n 的輸入上、在最壞情況下，機器同時標記過的紙帶格數的最大值。我們仍以同一個 n——輸入字串的長度——來衡量它，並套用同一層大 O 鏡頭，忽略常數與低階項，好讓答案描述的是問題本身，而非某一台特定機器的記帳方式。你對誠實衡量所內化的一切都直接延用過來；只是我們計數的那個量，從讀寫頭的動作換成了紙帶的格子。
讓次線性空間成為可能的那個技巧
這裡立刻有個問題。一台普通的圖靈機把輸入讀在紙帶上，所以那 n 格在機器寫下任何屬於自己的東西之前就已經被佔用了。照這樣算，沒有任何機器能用少於 n 的空間——它總得把輸入擺在某處。這會讓整個問題變得乏味：空間永遠至少是線性的，而最有趣的地帶，也就是那些微小記憶體的機器，將完全看不見。所以這個領域採用了一個小而果決的慣例，來誠實地對記憶體計費。
解法就是工作帶慣例：給機器兩條規則不同的紙帶。一條是裝著 n 個輸入符號的唯讀輸入帶——讀寫頭可以沿著它滑動、觀看，但永遠不能寫——而且關鍵在於它的格子不計入空間。另一條（或數條）是可讀寫的工作帶（草稿紙），而只有在那裡用到的格子才被計為空間。可以想成一場考試：你拿到一張印好的題目卷，想看幾遍就看幾遍，但不能在上面做記號，外加一本薄薄的草稿本；你的「空間」是你填滿了多少草稿本，而非那張免費發給你的題目卷。
為什麼空間和時間如此不同
空間有一個時間沒有的性質：它是可重複使用的。計算的每一步一旦花掉就永遠消失，但工作帶的一格可以被擦掉、再一次又一次地覆寫。這正是為什麼結果上空間是一種比時間更寬容的資源的深層原因。一台機器可以走天文數字般的步數，卻從不用超過一小塊紙帶，方法只是反覆覆寫那一塊。所以對同一件工作，空間界限往往戲劇性地小於時間界限——而且兩者根本不必同步移動。
但反方向的關係並非免費。如果一台機器跑了 t 步，它至多標記 t 個新格子（每步至多一個），所以空間至多是時間：S(n) 至多是 T(n)。反過來，更令人驚訝的關係也成立，它用空間界住時間。一台用 S(n) 個工作格的機器，只有有限多種不同的整體快照——它的狀態、各讀寫頭的位置，以及那 S(n) 格的內容。如果它曾重複某個快照，就會永遠繞圈，所以一台會停機的機器，所跑的步數至多就是它有多少種不同的快照，算下來大約是 2^(O(S(n)))——對空間呈指數。簡言之，一點點空間就能藏下極其龐大的時間。
Two resources on one Turing machine
read-only INPUT tape (n cells, FREE -- never counted)
+---+---+---+---+---+---+
| 1 | 0 | 1 | 1 | 0 | 1 | <-- head may read, never write
+---+---+---+---+---+---+
read-write WORK tape (CHARGED -- this IS the space)
+---+---+---+
| x | 0 | _ | ... <-- erase & overwrite freely; reusable
+---+---+---+
<-- S(n) = high-water mark of cells used here -->
log-space S(n) = O(log n) : a few pointers into the input
poly-space S(n) = n^k : PSPACE
Relations: S(n) <= T(n) (each step marks <= 1 new cell)
T(n) <= 2^(O(S(n))) (only that many distinct snapshots)替各區域命名：一張新的類別地圖
正如界住時間給了我們 P 與 NP，界住空間也劃出一族嶄新的空間複雜度類別，每一個都收集機器能在某個工作格預算內判定的語言。從省到奢的幾個頭條層級：L，在確定型機器上能用 O(log n) 空間解決的問題；NL，同樣的預算但允許非確定型機器；以及 PSPACE，能用多項式空間解決的問題——n、n^2，或任何 n 的某個固定次方。這些對應你早已認得的時間類別，只是計量表從步數換成了格數。
上面時間對空間的關係，讓我們能把這些縫成一條橫跨兩階梯的宏大鏈條：L 在 NL 之中，NL 在 P 之中，P 在 NP 之中，NP 在 PSPACE 之中，PSPACE 在 EXPTIME 之中。每一個包含關係都有一句誠實的理由。L 在 NL 之中，因為確定型是非確定型的特例。NL 在 P 之中，因為一台對數空間機器只有多項式多種快照，所以你能在多項式時間內搜索它們。P 與 NP 落在 PSPACE 之中，因為一台多項式時間的機器只標記多項式多的格子。而 PSPACE 在 EXPTIME 之中，因為按快照論證，多項式空間能在指數時間內被模擬。這就是整個階梯要繪製的類別地圖。
這一階梯將帶你看到什麼
把空間定義好、地圖描出後，這一階梯其餘的部分就去探索它。最大的回報在於：空間因為可重複使用，行為比時間更溫馴——而這產生了一些乍看不可能的結果。有兩個坍縮特別突出。Savitch 定理指出非確定性對空間幾乎毫無用處：任何用 S(n) 空間的非確定型機器，都能改成只用 S(n)^2 空間的確定型機器，這迫使 PSPACE = NPSPACE——P 對 NP 問題的空間版本就這麼消失了。而 Immerman–Szelepcsenyi 定理指出 NL 對補集封閉，所以 NL = co-NL——對非確定型對數空間而言，一個「是」的實例和一個「否」的實例同樣容易出示證書，而這件事對 NP 對 co-NP 卻全然未知（且普遍被懷疑不成立）。
接著這一階梯轉向事情真正變難的地方。PSPACE 有它自己的「最難問題」概念——那些 PSPACE 完全的問題——而它們的自然形式不是 NP 那種你能查驗的拼圖，而是一場雙人遊戲：一個量化的布林公式，問「是否存在一步我可以走，使得對你的所有回應，都存在一步我可以走……」，其中交替的存在／全稱量詞，恰恰就是最佳對弈的你來我往。最後，第五篇揭示我們究竟如何證明這些類別彼此真的不同：一個對角化論證——正是讓停機問題不可判定的那個自我指涉的把戲——被用在各種 階層定理裡，證明嚴格更多的空間（或時間）能換來嚴格更多的能力。
往上爬時，請握住一個誠實的告誡。各個包含關係是定理，但各個分離大多是猜想：我們相信 L、NL、P、NP、PSPACE 全都真的不同，但我們幾乎沒證明過這些間隙裡的任何一個。我們能證明的那一點點，恰恰就是階層定理的那兩個端點。分清楚哪些事實已成定論、哪些只是被懷疑，正是讓這一階梯保持誠實的紀律——也正是為什麼像 P 對 NP 這樣的問題，至今仍是本學科的重大未解問題之一，而非一樁陳舊的已結案件。