地圖到頭的地方
你已經爬了很遠。你從一個只記得自己當前狀態的旋轉閘門起步——一台 DFA——而你如今能把整片地景擺對位置：有限自動機與正規語言，接著一疊盤子把機器變成處理上下文無關語言的下推自動機，再來是圖靈機那本無盡的筆記本與不可判定性的懸崖，最後是給了我們 P、NP 以及其餘一切的時間與空間度量。這篇終章不教新機器。它一路拉到最遠，把前四篇的邊疆收攏成一幅圖景，再帶你走到邊緣——那些至今無人回答的問題。
這整門學問誠實的主旋律，直白地說，是這樣的。已被證明的事實是一座小小的、得來不易的島嶼；環繞四周的汪洋是猜想。我們知道停機問題是不可判定的——這是個定理，由對角線論證永遠地定了案。但複雜度類別之間幾乎每一個有趣的分離——P 是否不同於 NP、NL 是否不同於 P、P 是否不同於 PSPACE——都懸而未決。有些東西我們能證明它必為真；但對那些大問題，我們多半只有強烈的信念，以及一種令人氣餒的、無法把它證出來的窘境。對這個領域成熟的理解，就是清楚分辨哪一條線是定理、哪一條只是盼望。
收攏邊疆
讓我們把前四篇拉成一幅圖，因為每一道邊疆其實都是在用一種新方式問：「高效計算到底是什麼意思？」首先是隨機性。BPP 這個類別收納的是：若允許一台機器擲硬幣、並容忍一個微小且有界的錯誤，它就能快速判定的問題。當前深刻而令人意外的信念——由去隨機化的結果撐腰——是隨機性大概買不到額外的能力：多數研究者預期 BPP 等於 P，也就是每個快速的擲硬幣演算法，都有一個快速的確定型雙胞胎。隨機位元是一種方便，多半不是一種超能力。
其次是互動與證明。當一個強大但不被信任的證明者，與一個快速、多疑、會擲硬幣的驗證者來回交談，驗證者竟能被說服相信一些難得驚人的真理——那個著名的結果是，互動式證明恰好捕捉了 PSPACE（即聞名的 IP = PSPACE）。再往前推，你就得到零知識證明，證明者讓你相信某個陳述為真，卻除了它的真實性之外什麼都不洩漏——這是現代密碼學身分驗證底下的基岩。而 PCP 定理，這個對 NP 令人震驚的重述，說每一個 NP 證明都能改寫成：驗證者只需抽查常數個隨機選出的位元；正是這個驚人的事實，撐起了近似困難度，證明對某些問題，連接近最佳值都是 NP 難的。
第三是量子邊疆——而這裡最需要誠實。BQP 這個類別捕捉了量子電腦能高效做到的事，而它在某些特殊的、有結構的問題上，確實勝過古典機器（例如用秀爾演算法做整數因數分解）。但量子電腦並不是一台神奇的 NP 求解器：沒有任何已知的量子演算法能在多項式時間內解出 SAT 或任何 NP 完全問題，而多數專家相信這樣的演算法並不存在。葛羅佛搜尋只給出平方的加速——把 2^n 的暴力搜尋變成大約 2^(n/2)——這是真的，卻遠遠談不上讓 NP 塌縮。那個流行的形象——量子機器「一次試遍所有答案、再把對的那個讀出來」——根本是錯的；讓量子演算法奏效的干涉現象既精微、又只在恰好的隱藏結構下才幫得上忙。
當自動機遇上邏輯
有一道邊疆值得細看，因為這套理論正是在那裡，悄悄地變成了一件工業工具。回到最初，你的自動機讀的是有限字串。但一台伺服器、一個作業系統、或一盞紅綠燈，永遠不會停下來——它的行為是一串無窮的狀態序列。要推理「這個系統會不會死鎖？」或「每個請求最終都會被服務嗎？」，我們需要在無窮字（infinite word）上運轉的自動機。畢希自動機（Büchi automaton）正是如此：它看起來像一台普通的 NFA，但它的接受規則為無窮而扭轉了——一次運轉若無窮多次經過某個接受狀態（而不是停在某個接受狀態），就算接受。光是這一個改動，就足以捕捉那些必須永遠成立的性質。
美妙的連結在這裡。工程師用時序邏輯描述想要的行為——一種帶有「永遠」「最終」這類算符的精確語言（例如「永遠都是這樣：一個請求最終會被批准」）。關鍵的定理是：這樣一條邏輯公式，能被機械地翻譯成一台畢希自動機，恰好辨識所有滿足它的無窮運轉。於是模型檢驗就化為純粹的自動機理論：替系統造一台畢希自動機、替想要性質的否定造另一台，取它們的乘積（兩台自動機的交集，正如你在正規語言裡見過的乘積構造），再問這個乘積到底接不接受任何一個無窮字。若它是空的，就沒有任何行為違反該性質，系統便被證明為正確；若不是，那個接受運轉就是一個具體的反例——一條 bug 軌跡，免費奉送到你手上。
還有第三股線值得點名，因為它把複雜度本身重新框定了。描述複雜度問的不是「一個問題需要多少時間或空間？」而是「你需要多豐富的邏輯，才能把它描述出來？」其里程碑是費金定理（Fagin's theorem）：一個性質落在 NP 裡，恰恰當它能用存在型二階邏輯表達——也就是說「存在一個關係（一種著色、一條巡迴、一個真值賦值），使得某個簡單的局部條件成立」。這是一座令人瞠目的橋：NP，原本由「猜測並驗證」的機器定義，竟原來是一個純粹的邏輯概念，連機器的影子都沒有。整個整個的複雜度類別都有這種邏輯指紋，這意味著像 P 對 NP 這樣的問題，也能當成一個關於各種邏輯之表達力的問題來進攻。
理論悄悄運轉世界的地方
在那些未解問題之前，先停一下，看看你每天已經多麼仰賴這些東西。這套理論不是象牙塔；它是計算的沉默基礎建設。每當你打進一個搜尋樣式，一個正規表示式引擎就把它編譯——理想上編譯成一台 DFA——那不過就是有限自動機在運作。每一種程式語言都由一個上下文無關文法剖析，那文法驅動著編譯器的前端；那個剖析器內部的堆疊，就是一台喬裝的下推自動機。那些不可判定性的結果也不是陰鬱的冷知識——它們解釋了為什麼沒有編譯器能標出每一個無窮迴圈、為什麼完美而全自動的程式驗證在一般情況下不可能；工具只能退而求其次，接受可靠的近似。
而 NP 完全性是工作中的科學家每天的早期警報系統。當你證明自己的真實問題是 NP 完全的，你並非失敗了——你學會了別再獵尋一個快速精確的演算法，轉而伸手去拿一個近似演算法、一個啟發式、在某參數保持很小時的參數化易解性，或在輸入極小時的精確指數方法。模型檢驗，建在上面那套畢希機制之上，驗證著真實的晶片與協定。計算語言學借用喬姆斯基階層來建模人類語言的結構。這套理論在電腦科學幾乎每個角落都繳得起房租——而它做得到，恰恰因為它的邊界（正規、上下文無關、可判定、易解）是鋒利而被證明過的。
站在邊緣：幾個偉大的未解問題
現在來到地圖的邊緣，由那個凌駕整個電腦科學的問題領頭。P 對 NP問的是：是否每個答案容易檢查的問題，也都容易找出——那個瞄一眼就能驗證的拼圖，是否總能被快速拼好。我們已經證明 P 是 NP 的子集（能快速求解就蘊含能快速檢查）。未解的是這個包含關係是否嚴格。再想起 NP 那一階的那根槓桿：因為有NP 完全性，只要連一個 NP 完全問題（如 SAT）有了多項式演算法，整條歸約鏈就會一口氣把整個 NP 拖進 P 裡。所以一切都繫在我們所知最難的那些問題上，而它們全都一起沉浮。
PROVED (theorems, settled forever):
P is a subset of NP is a subset of PSPACE
IP = PSPACE (interactive proofs)
PCP theorem (NP proofs spot-checkable)
Halting problem is undecidable
OPEN (conjectured, NOT proved):
P =? NP <-- the big one (since 1971)
NL =? P
P =? PSPACE
BPP =? P (most believe YES: randomness is free)
BQP vs NP (quantum is NOT a known NP-solver)
Reductions: a fast algorithm for ONE NP-complete problem
would collapse ALL of NP into P.P 對 NP 為何抵擋了超過半個世紀？不是因為缺乏努力——而是因為我們最鋒利的工具，已知都太鈍了。曾斬殺停機問題的對角線論證，可證明地無法解決 P 對 NP（這是相對化障礙）；而最自然的那些組合論證，則撞上了自然證明障礙。從某個真切的意義上說，我們缺的是一個根本性的全新點子。這就是整道階梯誠實的收尾：你如今握著一張精確而被證明過的計算地圖——機器能做與不能做什麼、什麼便宜什麼昂貴——然而它最重要的那一個地標，「容易」與「僅僅可檢查」之間的那條邊界，依舊未被標出。這片邊疆不是理論的失敗；它是一封敞開的邀請函，而你現在已有能力讀懂它。