一本巨書旁的一小塊草稿紙
在前一階梯，你學會了用衡量時間的方式來衡量記憶體：計數的不是機器走了幾步，而是它在工作帶格上寫了幾格。關鍵的訣竅是唯讀輸入帶與工作帶的約定。少了它，誠實地計數空間永遠至少是 n，也就是輸入的長度，因為機器總得把輸入存在某處。於是我們把圖靈機的筆記本一分為二：一條唯讀的輸入帶，機器可以隨意掃描多少次都行，卻永遠不能在上面寫字；以及一條獨立的、空白的工作帶，我們真正計費的就是它的格子。如今，低於 n 的空間變得有意義了——甚至遠低於 n 的空間也是。
到底多小才有趣？答案是出奇強大的對數空間境界：一條只有 O(log n) 格的工作帶。這聽起來幾近羞辱——log n 只是一絲，遠遠小到無法複製輸入。但魔法在這裡。一個用來指名長度為 n 之輸入中某位置的數字，寫下來只需要大約 log n 個位元（把它想成你數到 n 所需的位數）。所以 O(log n) 格剛好夠裝下固定的幾根指向輸入的指標，外加幾個小小的計數器。你記不住輸入說了什麼；但你能記住你正在看哪裡，以及數一點點數。這就是全部的預算，而它足以做出令人驚嘆的事。
L 與 NL：兩個對數空間類別
這份預算下棲息著兩個類別，而它們的分岔正是你最初在有限自動機那裡遇見的確定型對非確定型的那道分叉。L（有時寫作 LOGSPACE）是確定型圖靈機能用 O(log n) 格工作帶判定的問題所成的集合。NL 則是把機器換成非確定型的同一回事：它在每一步都可以猜測並驗證——朝四面八方分支，只要任一分支接受就接受——同時仍只在工作帶上寫 O(log n) 格。這裡的非確定性，正是你在 NFA 那裡遇見的那同一個數學裝置，不是隨機的、也不是實體的機器；只不過這次受限的不是時間，而是記憶體。
這裡有一個落在 L 中的乾淨例子。假設輸入是一個字串，我們想判定它是否含有偶數個 a 符號——正是你當年交給一台小小 DFA 的那項任務。一台對數空間機器靠一個位元的工作帶（一個奇偶旗標）和一根由左掃到右的指標就能辦到：讀下一個符號，若它是 a 就翻轉旗標，把指標前移，到結尾時若旗標讀作「偶」就接受。指標裝進 log n 個位元，旗標裝進一個位元，而輸入從未被複製。更驚人的是：判定一個以二進位寫出的數是否被 3 整除也在 L 中——你掃過各位數字，只保留對 3 取餘數的滾動值，它是三個值之一，是個常數。
為什麼要關心一個這麼侷促的類別？兩個誠實的理由。第一，無論資料多麼浩大，凡是幾乎不需要工作記憶體就能跑的計算，對數空間正是它們的自然歸宿——這恰恰是串流感測器、瞄一眼封包的路由器，或對一個遠大於記憶體之資料庫所下的查詢所處的情境。第二，也更深刻：正因為空間預算如此緊，L、NL 與其上方各時間類別之間的關係出奇地容易推理，而其中有幾條——不像那令人抓狂的 P 對 NP——竟真的被證明了。對數空間，正是複雜度理論得以乾脆贏下幾場辯論的所在。
可達性：NL 的核心
有一個問題就是 NL，意思是 NL 中其他一切都只是套在它身上的戲服。它陳述起來簡單到幾乎令人尷尬。可達性（也叫 PATH 或 s-t 連通性）：給定一個有向圖與兩個頂點 s 和 t，從 s 到 t 有路徑嗎？想像一座以點與單向箭頭畫成的迷宮；你站在 s，想知道沿著箭頭走是否能抵達 t。整個問題就這樣。
為什麼可達性在 NL 中，又為什麼它就是無法以更輕鬆的方式塞進我們的對數空間預算？顯而易見的演算法——廣度優先搜尋——需要記住哪些頂點已經造訪過，而這份清單可能長得跟整張圖一樣，把對數空間的預算撐爆。非確定型機器以一個美妙省儉的訣竅繞過了它：它不去畫出一條路徑，而是一次猜一步，而且從不把路徑寫下來。它的工作帶上只保留兩樣東西：它此刻所站頂點的名字，以及一個步數計數器。每走一步，它就猜一個鄰居、走過去、把計數器加一。若它抵達 t，就接受。若計數器超過頂點數仍未抵達，這條分支就放棄。
REACHABILITY by a log-space NONDETERMINISTIC machine
(work tape holds only: cur = current vertex , steps = a counter)
graph: s -> a -> b -> t ( the lucky branch )
s -> c (dead end)
cur := s ; steps := 0
repeat:
guess a neighbour v of cur <- nondeterministic choice
cur := v ; steps := steps + 1
if cur = t -> ACCEPT
if steps > |V| -> this branch gives up
one accepting branch: s -> a -> b -> t (4 steps, then ACCEPT)
work tape ever used: one vertex name + one counter
each is about log n bits. NEVER the path.把這個訣竅讀仔細，因為它正是非確定性發揮價值的所在。機器從不持有「已造訪集合」或那條路徑——兩者都太大。它只持有一個頂點與一個計數器，並信賴分支去找出正確的下一跳。只要路徑存在，某條分支就會把每一步都猜對而接受；若不存在，每條分支終將把計數器耗盡而拒絕。這正是 NFA 那裡的猜測並驗證模式，如今被擠進一塊對數空間的草稿紙。一台確定型對數空間機器能否與它匹敵——也就是可達性是否在 L 中——是一個著名的未解問題，即 L 對 NL 之問。
NL 完全性與對數空間翻譯
可達性不只是在 NL 中——它是 NL 完全，是這個類別中最難的問題，是一道所有其他 NL 問題都能被翻譯進去的單一拼圖。「最難」這個概念依附於一次歸約，正如它在 NP 完全性那裡所做的那樣——但帶著一道強制性的收緊。我們在這裡不可以使用多項式時間的歸約，因為一台多項式時間的翻譯機本身就可能用掉多達多項式的空間，這會讓整個對數空間的預算相形見絀，使比較失去意義。所以正確的工具是對數空間歸約：一台只用自己的 O(log n) 格工作帶來改寫實例的翻譯機。
為什麼可達性是那個通用的標靶？因為運行一台 NL 機器這件事本身就是一個可達性問題。攤開這台機器的組態圖：每一個可能的組態（它的狀態、它的讀寫頭位置，以及工作帶上的那 O(log n) 個位元）對應一個頂點，而只要機器能在兩個組態之間跨一步，就從前者向後者畫一支箭頭。關鍵在於，由於工作帶只有 O(log n) 格，組態的總數只是 n 的多項式——小到圖中的每一個頂點都能被一根對數空間的指標指名。這台機器恰好在從起始組態到某個接受組態之間存在路徑時接受它的輸入。判定那次 NL 計算，就是在那張圖上求解可達性。
- 從 NL 中任一問題 A 出發，它由某台非確定型對數空間機器 M 判定。
- 給定輸入 w，（在對數空間內）建出 M 在 w 上運行的組態圖：它的頂點是 M 的各個組態，因為只有多項式那麼多個，所以可用短指標指名。
- 恰好在 M 能於一步內從組態 C 移動到 C' 時，加上一支箭頭 C -> C'——這項檢查由翻譯機在本地完成，讀取 w（唯讀）與少數幾根指標即可。
- 令 s 為起始組態，t 為（按慣例唯一的）接受組態。
- 於是「w 是 A 的一個『是』實例」恰好變成「從 s 到 t 存在路徑」——A 已被翻譯成可達性，且只用了對數空間。因此可達性是 NL 難的，而它本身又在 NL 中，故為 NL 完全。
對數空間棲身何處，以及前方兩個驚奇
現在我們能把這些類別擺到更大的地圖上了。顯然 L 在 NL 之內——一台確定型機器不過是一台從不分支的非確定型機器。而 NL 又坐落於 P 之內：要在多項式時間內確定型地判定一個 NL 問題，只要建出那張多項式大小的組態圖，並在其上跑一次尋常的可達性搜尋即可，這在時間上很快，儘管它在空間上花過了頭。把這些疊起來便得到鏈條 L 是 NL 的子集，NL 是 P 的子集，而它本身又匯入你將在最後一篇補完的那條宏大序列：L 在 NL 在 P 在 NP 在 PSPACE 在 EXPTIME 之內。
對那條鏈條中哪些環節是已知的，要誠實以對。L 是否等於 NL 仍未解——沒有人知道可達性能否在對數空間內被確定型地判定。NL 是否等於 P 同樣未解。一如 P 對 NP，這些都是猜想，被廣泛相信卻未經證明；包含關係是確定的，包含關係的嚴格性則不然。要抗拒把其中任何一條當成已成定論的那種輕率滑落。