拼圖的那道鴻溝
在上一階梯你學會了誠實地衡量執行時間——把機器的步數當成輸入大小 n 的函數來計數，取最壞情況，把常數抹平——並把那條頭條界線畫在多項式時間處。P 類恰恰收集了確定型機器能在多項式時間內判定的那些是/否問題，是我們對「可有效求解」的實用代稱。這篇要在那張地圖上開闢一個新區域，而它從一種人人早已熟悉的感受出發：動手做一道難題，與檢查一道做好的題，這兩者之間的差別。
想像一桌倒出來的一千片拼圖。拼湊它是一場漫長而令人挫折的搜尋：你試一塊，退回，再試。但如果一位朋友走進來，手上的拼圖已經拼好，並宣稱它是對的，檢查這個宣稱卻很快——你的目光掃過整幅畫面，確認每一條邊都對齊。求解感覺是指數級的；檢查感覺幾乎免費。這種不對稱並非拼圖獨有。一道數獨要填出來要人命，要驗證卻在一瞬間。一座迷宮要走出來很折磨人，但一旦把路徑畫出，瞄一眼就能確認。這一階梯的整個主題，就是這一類問題：一個解一旦遞到你面前，驗證起來很便宜——即使找出一個解看似得靠殘暴的搜尋。
把「易於檢查」講精確：驗證器
要把那種感受變成數學，我們得釘死「易於檢查」是什麼意思。關鍵的物件是一個驗證器：它不是一台求解問題的機器，而是一台評分某個提議答案的機器。除了輸入之外，驗證器還會拿到一段簡短的提示——一份憑證（也叫見證或證明）——而它唯一的工作，就是確認那段提示是否真的證明了「是」這個答案。拼好的拼圖、填滿的數獨格、畫出的迷宮路徑：每一個都是一份憑證。驗證器不搜尋；它只是檢查別人送給它的那份禮物。
兩個條件讓一個驗證器誠實。第一是完備性：若真正的答案是「是」，則存在某份憑證能讓驗證器接受。第二是健全性：若真正的答案是「否」，則沒有任何憑證——再怎麼狡猾——能騙它接受。而關鍵在於，驗證器必須在輸入大小的多項式時間內執行——檢查是便宜的那部分。一個問題恰好落在 NP 類中，正是當它擁有這樣一個多項式時間的驗證器，搭配一份多項式長度的憑證時。這就是整個定義：NP 是那些「是」答案都附帶一份簡短、可快速檢查的證明的是/否問題所成的集合。
一個乾淨的例子是可滿足性（SAT）。輸入是一個布林公式，例如 (x OR NOT y) AND (y OR z) AND (NOT x OR NOT z)；問題是：是否存在某種對變數的真/假指派，使整個公式為真。在 2^n 種可能裡找出這樣一種指派，看起來像在指數級的乾草堆裡搜尋。但把一個候選指派遞給我——比如 x=真、y=假、z=真——我代入後一條子句接一條子句地求值，片刻便完成。那個指派就是憑證；那個代入並求值的過程就是多項式時間的驗證器。SAT 在 NP 中。再次留意那種不對稱：我只替「是」的方向背書。一份憑證能證明一個「是」；它對證明一個「否」毫無幫助。
Is this 3-coloring valid? (a graph-coloring CERTIFICATE)
graph: vertices {1,2,3,4} edges 1-2 2-3 3-4 4-1 1-3
claim (the certificate): 1=Red 2=Green 3=Blue 4=Green
VERIFIER walks each edge, checks the two ends differ:
1-2 Red vs Green ok
2-3 Green vs Blue ok
3-4 Blue vs Green ok
4-1 Green vs Red ok
1-3 Red vs Blue ok -> ACCEPT
5 edge-checks: time grows with the input, not 2^n.
Finding a coloring is hard; checking one is a quick walk.從另一扇門進入同一個類：非確定性
定義 NP 還有第二種等價的方式，而它解釋了字母 N 的來歷。回想前面階梯裡的非確定型機器——那台 NFA，面對一個選擇時，在概念上把自己複製出來同時探索每一條分支，只要任一分支接受就接受。把這個想法從有限自動機提升到非確定型圖靈機，並限定它在多項式時間內執行。NP 恰恰就是這樣一台機器所判定的問題類。這台機器靠著朝每一種可能分裂出去來「猜」一份憑證，然後用一次多項式的檢查加以確認——正是你最初在 NFA 那裡遇見的猜測並驗證模式，如今放大到了整個計算。
這兩扇門——帶著憑證的驗證器，與那台會猜測的非確定型機器——通往的是同一個房間。那個猜測就是憑證；那次多項式的檢查就是驗證器。本階梯的第二篇會仔細走過這兩個定義並證明它們重合；現在只要握住這幅圖像：NP 就是那些你能在多項式時間內「先猜後查」其答案的拼圖。從自動機那幾階誠實地帶過來的兩個提醒在這裡同樣適用。非確定性是一種數學裝置，不是一台實體機器：沒有任何真實電腦會把自己複製出來，分支也不是隨機的好運。而且正如 NFA 並不比 DFA 更強大（它只換來了簡潔），這裡的非確定型機器也是一種定義上的方便——它是否真的比確定型機器更快，恰恰就是我們正繞向的那個未解問題。
把一道拼圖翻譯成另一道：歸約
NP 是一個浩大的集合——圖著色、旅行推銷員的路線、塞滿背包、安排考試。令人震驚的發現是，在深處，這當中極大量的問題其實是同一個問題換了戲服。揭露這件事的工具是多項式時間歸約，是你早已用來證明不可判定性的那種歸約的一種精修版。把它想成一位翻譯：一套快速、機械化的程序，把問題 A 的每一個實例改寫成問題 B 的一個實例，使得是/否答案被保留。如果你擁有一台 B 的快速求解器，這位翻譯就會立刻給你一台 A 的快速求解器：翻譯、解 B、回報答案。
歸約的讀法，正是初學者最常讀反的部分，所以大聲說出來：若 A 歸約到 B（寫作 A <=p B），則 B 至少和 A 一樣難。那次翻譯把 A 的難度載進了 B。所以一次歸約只在恰好一個方向上證明難度——讀反了就什麼也沒證明。嚐一小口：要把 3-SAT 歸約到團問題，就建一個圖，每個「子句中的一個文字」對應一個頂點，並在兩個頂點位於不同子句且彼此不矛盾時，用一條邊把它們連起來。那麼這個公式可滿足，若且唯若那個圖有一個大小為 k 的團（每個子句各貢獻一個頂點）。一個可滿足的指派變成一個團；一個團變回一個可滿足的指派。第三篇會把這個小裝置一塊一塊地搭起來；現在的重點是：這座橋是可建造的，而且很快。
NP 中最難的問題，與那個百萬美元的問題
歸約讓我們能依難度替問題排序，而那個排序有一座頂峰。一個問題若每一個 NP 中的問題都歸約到它，它就是 NP 難——它至少和 NP 中任何東西一樣難。一個既是 NP 難又本身是 NP 成員的問題，就是 NP 完全：NP 之內最難的那一類問題，一道所有其他問題都能被翻譯進去的單一拼圖。里程碑式的 Cook-Levin 定理點燃了引信，它證明了第一個：SAT 是 NP 完全的。一旦你有了一個 NP 完全問題，再多就便宜了——把 SAT 歸約到你的問題，它就入會。那著名的名單正是這樣長出來的：3-SAT、團、頂點覆蓋、漢米爾頓路徑、旅行推銷員、子集和、圖著色。第四與第五篇會證明 Cook-Levin 並巡覽這座動物園。
現在整幅圖像就圍繞著一個問題清晰地對上焦了。我們知道 P 在 NP 之內。我們知道數以千計的自然 NP 完全問題，全被歸約緊緊地串在一起，緊到只要任何一個有了快速演算法，就會為它們全部帶來快速演算法——並會證明 P = NP。然而努力了半個世紀，沒有人找到這樣的演算法，也沒有人證明這樣的演算法不可能存在。P 是否等於 NP 仍未解——這是克雷研究所的百萬美元問題之一，可說是計算機科學中最深刻的未解問題。多數研究者猜想 P 不等於 NP（也就是檢查確實比求解容易），但猜想不是證明。