我們身在何處：一座大半靠信念撐著的類之塔
前三篇搭起了一座資源類的垂直之塔。塔底坐著 NL，是非確定型機器只用對數大小的工作帶、外加一條唯讀輸入帶就能解的那些問題；它的招牌問題是可達性——在一張有向圖裡，你能否從節點 s 走到節點 t？NL 之上是 P、NP，然後是 PSPACE（多項式工作帶空間，是量化公式與博弈類問題的家），再高高在上的是 EXPTIME。誠實而略帶尷尬的真相是：這座塔幾乎每一級都是一個沒人證明過是嚴格的單向包含關係。我們相信 NL 比 P 小、P 比 NP 小，但我們證明不了。這一篇講的，正是迷霧偶爾散開的那些罕見之處——在那裡我們能說出某些既驚奇又確定的話。
對時間而言，非確定性看起來像一道深淵：整齣 P 對 NP 的戲，講的就是「猜測機器或許能比埋頭硬幹的機器快上指數倍」這份疑慮。而這一階梯的震撼在於：對空間而言，那道深淵幾乎合攏了。兩個定理——薩維奇定理與 Immerman-Szelepcsenyi 定理——指出讓機器去猜，在記憶體上幾乎換不到任何額外好處。記憶體不像時間，它可以重複使用：你走過的一步收不回來，但你在某個帶格上塗寫的東西可以擦掉重寫。正是這單一的不對稱，是這裡每一樁驚奇背後的祕密引擎。
薩維奇定理：猜測幾乎換不到額外的空間
先講頭條。薩維奇定理說：任何使用 s(n) 空間的非確定型機器，都能被一台只用 s(n) 平方空間的確定型機器模擬。平方聽起來很多，其實很溫和：一個多項式的平方仍然是多項式。最常被引用的推論是 PSPACE 等於 NPSPACE——非確定型多項式空間並不給你任何超出確定型多項式空間的東西。把這拿來對比時間：在時間上，把非確定型機器轉成確定型機器要付出指數級的暴增，而我們完全不知道如何避免它。對空間而言，代價不過是一個平方。
這怎麼可能成立？訣竅是把整個問題改寫成可達性——正是定義 NL 的那同一個「s 到 t」問題。一台使用空間 s 的非確定型計算，是在探索一張圖，圖的頂點是組態（機器的狀態加上它的帶內容），這樣的頂點至多約 2^(s) 個。機器接受，恰恰就在於：在這張巨大的組態圖中，存在一條從起始組態通往某個接受組態的路徑。所以「這台非確定型機器接受嗎？」字面上就是「目標可達嗎？」確定型模擬器要做的，只是節儉地回答可達性，邊走邊重複使用記憶體。
這套節儉的演算法，是一個遞迴的分治法，核心有個漂亮的點子，有時叫做 REACH 或中點法。要問「我能否在至多 k 步內從 a 走到 b？」，不要去追蹤一條路徑——而是猜中點。途中必定存在某個處於半途的組態 m，於是改問兩個更小的問題：我能否在 k/2 步內從 a 到 m，以及在 k/2 步內從 b 到 m？把每一個可能的 m 一個接一個地試過去，每次試驗都重複使用同一塊草稿空間。這個遞迴只有大約 log(k) 層深，因為 k 每次減半，而每一層只存一個大小為 s 的組態。總空間：log(k) 乘以 s。由於 k 約為 2^(s)，log(k) 約為 s，最終總和便是 s 平方。整個定理就這樣了，而在試過許多個 m 的過程中重複使用那塊草稿空間，正是時間做不到的記憶體回收。
REACH(a, b, k): "can b be reached from a in <= k steps?"
if k == 1: return (a==b) OR (a -> b is one legal move)
for each possible midpoint configuration m: <-- reuse the SAME
if REACH(a, m, k/2) AND REACH(m, b, k/2): cell for each m
return YES
return NO
recursion depth ~ log(k) ~ log(2^s) = s levels
each level stores ~ s (one configuration)
TOTAL space ~ s * s = s^2 (NOT s^2 TIME -- time blows up!)Immerman-Szelepcsenyi：非確定性能數清自己的失敗
第二樁驚奇關於取補集——把「是」和「否」對調。對確定型機器而言，取補集再簡單不過：跑它一遍、把答案反過來。對非確定型機器卻不然，而這正是讓 co-NL（以及 co-NP）顯得神祕的同一個關鍵。一台處理可達性的非確定型機器，在存在某條從 s 到 t 的路徑時接受；它只需要一條走運的分支就能說「是」。但要辨認那個補集——也就是要證明 t 是不可達的——單一一條分支得有辦法保證每一條路徑都失敗。這對一台會猜測的機器來說感覺是不可能的，於是數十年來人們都假定 NL 與 co-NL 必定不同。
他們錯了。Immerman-Szelepcsenyi 定理證明了 NL 等於 co-NL：非確定型對數空間類對取補集是封閉的。破解它的技巧叫做歸納計數，點子美極了。假設機器能算出從 s 在 i 步內可達的頂點的確切數目——叫它 count(i)。那麼它就能驗證那個不可達的情形：要證明 t 不可達，就對那 count(n) 個可達頂點中的每一個，非確定地猜出並重新驗證一條抵達路徑，確認你恰好找到了那麼多個，再檢查 t 不在其中。如果你能精準地產出那個被承諾的可達頂點數目、而 t 不在其列，那麼 t 就真的不可達——沒有任何路徑被遺漏，因為那個計數本身就是完整性的證明。
而 count(i) 本身是一步一步、一層一層建起來的，由 count(i) 算出 count(i+1)——每一層都只用對數空間重新驗證，因為——再一次——那些草稿是被回收的，而不是被累積的。其深層寓意與薩維奇定理一致：在記憶體的世界裡，一台非確定型機器可以被裡外翻轉，因為它愛重跑、重數多少次都行，而不必在空間上付帳。誠實的範圍界定：這種對補集的封閉性，是空間受限類的特殊福分。類比的 NP 是否等於 co-NP 完全未解，且普遍受懷疑——時間的世界保有它的不對稱。
層級定理：一道終於證明出某物「確實更大」的對角線
至此為止的驚奇都是坍縮——某些類原來是相等的。但我們也渴望相反的東西：一份保證，保證更多資源確實換來更多能力，這座塔並非暗地裡是平的。時間層級定理與空間層級定理恰恰交出了這個。粗略地說：給予有意義地更多的時間（或空間），一台機器就能判定那些任何擁有有意義地更少時間（或空間）的機器都無法判定的語言。對同一種資源而言，多真的就是多。這些是我們能夠徹底證明的少數幾個分離之一。
其證明是對角線論證——正是你看著它擊敗停機問題、更早之前用來數實數的那同一招。建一台時間預算寬裕的機器 D，它只做一件存心搗蛋的事：模擬第 i 號機器在輸入 i 上的行為，然後反其道而行，跟那台機器在較小預算內做的事對著幹。如今 D 的行為在至少一個輸入上（也就是替那台機器命名的那個輸入）與每一台小預算機器都不一致，所以 D 所判定的語言無法被它們任何一台判定。D 跑那場模擬所需的時間，只比它所駁倒的那些機器多一點點——正是這點額外開銷，使得那道差距必須大於一個常數倍。這道對角線靠著建構，造出了嚴格分離的一個見證。
由此我們收穫一個乾淨、無條件的事實：P 不等於 EXPTIME。指數時間嚴格地勝過多項式時間，不需要任何猜想——時間層級定理保證存在一個能在指數時間內解、卻可證明無法在任何多項式內解的問題。值得細品為什麼這在 P 對 NP 上行不通、在這裡卻行得通。對角線論證分離的是一個類與同一種資源的更大版本（更多時間對更少時間）。它對分離不同資源或不同模式（確定型時間對非確定型時間）無能為力——在那裡，兩台機器並沒有玩同一場遊戲，對角線也找不到一個乾淨的對立面可供翻轉。正是這個盲點，使得 P 對 NP 抵擋住了這項技巧。
讀懂類地圖：什麼已成定論，什麼仍是信念
把我們手上的一切疊起來。類地圖讀作 L 在 NL 在 P 在 NP 在 PSPACE 在 EXPTIME 之內，一條單一的上升鏈。這一篇在其中添上了地標：PSPACE 等於 NPSPACE（所以靠薩維奇定理，給多項式空間加上非確定性是免費的）、NL 等於 co-NL（Immerman-Szelepcsenyi），而在確定型那一側，L 在 NL 在 P 之內——這本身也是一個帶薩維奇味道的事實，因為用平方訣竅解出的 NL 落在多項式時間之內。NP 之上，多項式層級疊起一層層交替的「存在」與「對所有」——NP 與 co-NP 是它的第一階——而整座塔嚴絲合縫地嵌在 PSPACE 之內。
現在來點殘酷的誠實。那些相鄰的包含關係，幾乎沒有一個已知是嚴格的。我們不知道 L 是否比 NL 小、NL 是否比 P 小、P 是否比 NP 小、NP 是否比 PSPACE 小。這每一個都是猜想為「是」、卻什麼都沒證明出來。層級定理確實沿著這條鏈交給我們某些嚴格的縫隙——最有名的是 P 不等於 EXPTIME，同樣地 NL 嚴格地落在 PSPACE 之內——這意味著它們之間那些未證明的環節中至少有一個必定是嚴格的，只是我們指不出是哪一個。這是一種真正古怪的認知狀態：我們證明了大樓裡某處有火，卻說不出究竟是哪一個房間在燒。