階層定理與複雜度類別地圖

我們已經知道的，以及還缺的那一件事

盤點一下這一階。你學會了用一條獨立的唯讀輸入帶來數記憶體，這樣「次線性的工作空間」才講得通；你見過 L 與 NL，也就是能在對數工作空間內解出的問題，並看到圖的可達性是 NL 中最難的問題；你見過 PSPACE 及其完全問題，那些雙人遊戲與量化布林公式；你也目睹了兩場漂亮的坍塌——Savitch 定理把 NPSPACE 折進 PSPACE，以及 Immerman–Szelepcsenyi 證明 NL 等於 co-NL。這些結果每一個都在說：「這個類別其實偷偷地跟那個類別一樣。」

於是出現了一個令人不安的領悟。我們有一整座由命名類別堆起的高塔——L、NL、P、NP、PSPACE、EXPTIME——而到目前為止，幾乎每個定理要嘛證明其中兩個相等，要嘛說我們分不出它們。我們從來沒有一次證明過這座塔真的很高，也就是某個較高的類別嚴格地包含一個較低的類別。萬一整座塔悄悄坍成單獨一層怎麼辦？這篇就回答這個恐懼。恰好有一個證明「分離」的主技巧，它是個喬裝過的老朋友，而它給了我們整個複雜度理論裡第一個堅如磐石的「這個嚴格大於那個」。

再一次，對角線化

你已經看過這個技巧打敗停機問題：把機器列成一排，造一台新機器，刻意在輸入 i 上跟第 i 號機器唱反調，於是你製造出了一個列表上沒有任何機器能等於的東西。那就是穿上電腦科學戲服的 Cantor 對角線論證。時間階層定理正是同一招，只是螺上了一個碼錶。我們不問「第 i 號機器會停嗎？」，而問「第 i 號機器會在一個寬裕的時間預算內停嗎？」——然後跟那個答案唱反調。

定下一個寬裕的時間預算，比方說 f(n) 步，其中 f 的成長要比 g（我們想超越的較小預算）快上足夠多。造一台「對角線」判定機 D，它讀入一段同時編碼了某機器 M、以及把這份編碼當成 M 自身輸入的字串。
D 去模擬 M 在該輸入上的執行，但帶著一個計數器：它只准 M 跑大約 g(n) 步——一個小心設計的通用模擬，正是通用圖靈機的同一個想法，只多花一個 f(n) 吸收得了的溫和係數。
當模擬在預算內結束時，D 輸出與 M 相反的答案：M 接受，D 就拒絕，反之亦然。若 M 超過了它的 g(n) 預算，D 就乾脆停下並接受（任何固定的選擇都行）。
現在假設某台在 g(n) 時間內執行的機器判定了 D 的語言。把它自己的編碼餵給這台機器。在那個輸入上，D 被設計成做完全相反的事——一個直接的矛盾。所以沒有任何 g(n) 時間的機器能算出 D，然而 D 本身在 f(n) 時間內就跑得完。f(n) 那一類嚴格更大。

回報立刻而具體。多項式時間與指數時間相隔夠遠，「f 比 g 成長快」這個差距撐得很舒服，所以時間階層定理證明了 EXPTIME 嚴格包含 P。這是真的：P 不等於 EXPTIME，沒有星號、沒有開放問題。確實存在需要指數時間、且永遠無法擠進多項式時間的問題。把同樣的論證改在帶子格子上跑（而非時鐘滴答），就得到空間階層定理，所以更多空間也嚴格買得到更多能力——比方說 L 是 PSPACE 的真子集。

為什麼同一招破不了 P 對 NP

既然對角線化能這麼乾淨地分開 P 與 EXPTIME，為何不直接把它對準著名的 P 對 NP 問題、把獎金領走？這裡有個誠實的陷阱，而它是這個領域最深刻的教訓之一。對角線化靠的是用一台機器以溫和的額外開銷去模擬另一台。但正是那個開銷，也就是通用模擬的成本，使它無法分開 P 與 NP：它們之間的落差（如果真有的話）太細，細到「模擬再翻轉」的論證解不開。P 與 NP 都帶著「多項式味」，而對角線技巧需要一個舒適的預算落差，那是「多項式對多項式」的設定根本給不出來的。

NP 之上：co-NP 與多項式階層

在畫出主地圖之前，NP 與 PSPACE 之間還坐著兩座地標。回想一下，一個問題屬於 NP，是因為它的「是」答案有一張你能快速檢查的短憑證——一塊難拼完、但有人把解交給你後就很容易驗證的拼圖。現在把它翻過來：co-NP 是那種「否」答案才有短而可檢查憑證的類別。「這公式可滿足嗎？」屬於 NP（給我看一組可滿足的賦值）；「這公式不可滿足、對任何賦值都不為真嗎？」則是它的 co-NP 雙胞胎，而沒人知道那有什麼短憑證。NP 是否等於 co-NP 仍是開放問題，多數人相信它們相異。

把這些想法疊起來，你就得到多項式階層。NP 問題可改寫成「是否存在一張憑證，使得某個多項式檢查通過？」——一個「存在」。co-NP 則是「對所有猜測，檢查都通過」——一個「對所有」。允許交替的量詞——存在、然後對所有、然後存在，像一場辯論裡雙方輪流回應對方——每多一次交替就定義出階層更高的一層。它正是你在 PSPACE 的量化布林公式裡看到的「量詞堆疊」在時間受限下的回聲，差別在於交替的次數維持為一個固定常數，而不隨輸入增長。

這個階層被普遍相信是一道真正的階梯，每一層都嚴格高於前一層——但說實話，那是猜想。更糟（或說更奇妙）的是，它一旦坍塌，坍塌會連鎖：萬一 P 結果等於 NP，整個多項式階層會一口氣壓平回 P。所以這座量詞層級之塔是栓在 P 對 NP 問題上的；抽掉那一根插銷，整個結構就可能垮下。

整張地圖，以及哪些門仍鎖著

現在我們可以把一切掛上同一面牆。從節儉讀到奢華：L 在 NL 之內（多一點非確定性從不吃虧），NL 在 P 之內（Savitch 與可達性演算法把對數工作空間塞進多項式時間），P 在 NP 之內（一台判定機就是一個忽略憑證的、毫不費力的驗證器），NP 在 PSPACE 之內（你能反覆回收多項式量的空間，一次一個地碾過指數般多的憑證），而 PSPACE 在 EXPTIME 之內（一台使用多項式空間的機器在必須停機或進入迴圈之前，只能抵達指數般多個相異的組態）。這條鏈就是每個學生腦中都揣著的複雜度類別地圖。

  L  <=  NL  <=  P  <=  NP  <=  PSPACE  <=  EXPTIME
  |                                          |
  +----- ALL inclusions above are PROVED ----+
  +------- this END pair is PROVED STRICT ----+
         (NL strict in PSPACE; P strict in EXPTIME)

  PROVED to be NOT EQUAL (some gap is strict):
     NL  !=  PSPACE        (space hierarchy)
     P   !=  EXPTIME       (time hierarchy)

  STILL OPEN (could be equal, could be strict):
     L  vs  NL      NL vs  P      P vs  NP      NP vs PSPACE

  so: SOMEWHERE in L<=NL<=P<=NP<=PSPACE a strict gap must hide
      -- but we cannot yet point to WHICH link it is.

一眼看盡的類別地圖。每一對相鄰的包含關係都已證明；階層定理證明了首尾兩段落差是嚴格的，所以每條鏈中至少有一個環節必定嚴格——然而是哪一個，仍是個謎。

盯著那張地圖，感受我們無知的這個奇異形狀。階層定理保證了「L 在 NL 內、在 P 內、在 NP 內、在 PSPACE 內」這條鏈不可能全是等號，因為它的兩個端點 NL 與 PSPACE 已被證明相異——某處藏著一個嚴格落差。然而我們指不出這四個環節中的任何一個、並證明它就是那個嚴格的。P 對 NP 最有名，但 NL 對 P、L 對 NL 同樣開放。我們證明了這道階梯不是平的，卻說不出哪一階才是高的那階。比起任何單一定理，這更是這門學問誠實的最前線——而它正是這整座階梯一路把你領向的那道懸崖。