從「找出答案」到「是或否」
至今你一路爬過的每一個演算法，解的都是一個最佳化或搜尋問題：回傳最短路徑、回傳最長共同子序列、回傳最大匹配。為了建立一套乾淨的「難度理論」，我們刻意把這份野心縮小。一個決定性問題，它的答案只是一個位元——是或否。不是問「最短的旅程是多長？」，而是問「有沒有一條長度至多 100 的旅程？」；不是問「要多少個頂點才能覆蓋所有邊？」，而是問「有沒有一個大小至多 k 的頂點覆蓋？」。把答案削成一個位元，正是讓不同問題之間能互相比較的關鍵，而比較，就是這一整階的全部精髓。
這看起來像是一種損失，但其實幾乎沒丟掉什麼。只要你有一個快速的是／否神諭來回答「有沒有一條長度至多 B 的旅程？」，你就能對 B 做二分搜尋找出最佳長度，然後一次剝掉一條邊、再重新發問，把一條真正的最短旅程重建出來——這一切只需要多項式數量的額外呼叫。所以決定性版本本質上和搜尋版本一樣難、絕不會更難；如果那個看似簡單的是／否問題竟是難解的，那麼更豐富的最佳化問題當然也難解。這正是我們要的推論：把最簡形式證成難的，建立其上的一切都會繼承那份難。
在我們能度量任何東西之前，還有一筆帳要記。一個輸入的大小，是把它寫下來所需的位元數——它的編碼。一張有 n 個頂點的圖、一串 k 個整數、一個布林公式：每一個都被攤開成位元，而一個演算法的執行時間，就拿來對照那個位元長度衡量。這聽起來很迂腐，但它在一個著名的地方狠咬一口。一個整數 N 只需大約 log N 個位元就能寫下，所以一個迴圈跑 N 次的演算法，對輸入大小而言是指數的、而非線性的——這個陷阱，等到子集和與分割問題看似騙人地簡單時，我們會再遇到一次。
P 類：我們稱之為「有效率」的那些問題
現在我們劃下第一條線。P 類，是那些存在某個演算法能在多項式時間內求解的決定性問題——時間為 O(n^c)，其中 c 是固定常數、n 是輸入的位元大小。「這個數是不是三的倍數？」、「從 s 到 t 有沒有路徑？」、「這些區間能不能全部排進去？」——這些都有跑在 O(n)、O(n + m)、O(n log n) 之類的演算法，所以它們全都安穩地坐在 P 類裡。你先前爬過的整道階梯——排序、最短路徑、動態規劃、網路流——從這個高度回望，其實就是一趟 P 類的巡禮。
為什麼挑多項式當分界線，而不是比方說「十億步以內」呢？有兩個誠實的理由。第一，穩健性：把一個合理的機器模型換成另一個、或者改以位元而非字組來度量，P 類都不會改變，因為一個多項式套上另一個多項式，仍然是多項式。這種穩定性既罕見又珍貴——它意味著 P 類是問題的性質，而不是你那台筆電的性質。第二，它所捕捉的那道鴻溝在實務上極其巨大：當 n 變大，一個 n^3 的演算法依舊堪用，而一個 2^n 的則會引爆。在 n = 60 時，n^3 是區區幾十萬步；2^n 卻超過一百億億。
NP 類：容易驗證，找出來卻或許很難
有些是／否問題，抵抗著我們試過的每一個多項式演算法，卻共享一個耐人尋味的特徵：如果答案是是，就存在一小段證據，能讓這個「是」變得顯而易見。「這個一萬變數的公式可滿足嗎？」也許會難倒我們直到宇宙終結——但只要遞給我一組能滿足它的賦值，我把它代進去，幾秒內就能確認「是」。「這張圖有沒有漢米頓迴圈？」要判定起來極其殘酷，但一條被提議的迴圈，要走一遍並加以驗證卻易如反掌。「找出」與「驗證」之間的這種不對稱，正是下一個類別的核心。
NP 類，是這樣一群決定性問題：每一個是的實例都有一段簡短的憑證——一個長度為多項式的被提議解——而一個多項式時間的驗證器能加以檢查。把確切的規矩釘清楚，因為這個定義是精準的：對一個是的實例，必須存在一段憑證能讓驗證器接受；對一個否的實例，驗證器必須拒絕每一段被宣稱的憑證，使得沒有任何字串能騙過它。驗證器是幹活的工人，憑證是悄悄遞給它的提示。NP 類，恰恰就是「一個好提示能把難問題變成易檢查」的那一群問題。
一個做過的例子：SAT 屬於 NP
我們真的來一步一步驗證：SAT——「這個布林公式有沒有一組賦值能讓它為真？」——確實屬於 NP。證明任何問題屬於 NP 的食譜，形狀永遠相同：指明一段憑證、限定它的長度、描述驗證器，然後檢查驗證器跑在多項式時間內、且永遠不會被騙。SAT 是這當中再乾淨不過的範例。
- 憑證：一組真值賦值——對公式的每個變數各給一個位元（真／假）。若公式有 v 個變數，憑證就只是 v 個位元，至多和公式本身一樣大，所以它對輸入長度而言穩穩是多項式的。
- 驗證器：把那些真值代進公式裡並求值。把公式走一遍，從各自的輸入算出每個 AND、OR 與 NOT。這是對公式的單趟掃描，因此跑在對輸入大小呈線性的時間內——遠在多項式時間之內。
- 當且僅當公式求值為真時才接受。現在檢查 NP 定義的兩半：若公式可滿足，就有某組賦值能讓它為真，驗證器會接受那段憑證（一個是的實例「擁有」一段好憑證）。若它不可滿足，每一組賦值都求值為假，於是無論遞上哪段憑證，驗證器都會拒絕（一個否的實例騙不了任何人）。
那段四行的論證，是「SAT 屬於 NP」的一個完整而嚴謹的證明——而請留意它從未做過的事。它從未找出一組能滿足的賦值；它只檢查了一段被遞給它的賦值。某個聰明的演算法能否在多項式時間內把那組賦值找出來，是個敞開著的大問題，而 SAT 終將被證明是庫克-列文定理所釘住的、全 NP 中最難的那一個問題。眼下，要學的是這個方法：證明某問題屬於 NP，靠的是展示一段簡短的提示與一個快速的檢查器，而不是把問題解出來。
P 包含於 NP，以及那個價值百萬美元的問題
首先，一個會讓人驚訝的事實：P 類裡的每個問題也都在 NP 裡，所以 P 是 NP 的子集。論證只要一句話。如果你能在多項式時間內解出一個問題，你根本不需要那個提示——讓憑證是空的，讓驗證器乾脆無視它、直接跑你那個多項式時間的求解器。「容易解」顯然就蘊含「容易驗」。所以 NP 既包含了所有易解的問題，又看似在其上額外堆著一疊看起來難解的問題，像 SAT 和漢米頓迴圈。
P = { decision problems solvable in poly time }
NP = { decision problems verifiable in poly time, given a short certificate }
P is a subset of NP (proven, easy)
P = NP ? (OPEN -- nobody knows)那個價值上兆的問題是：這個包含關係是不是嚴格的。會不會「驗證容易」其實早已蘊含「找出容易」——NP 裡的每個問題偷偷都在 P 裡，而 SAT 表面上的難只不過是人類聰明才智的失敗？這就是P 對 NP問題，而它確確實實是未決的：沒有人為 SAT 找到多項式演算法，也沒有人證明過這樣的演算法不存在。因此，對於「這個問題很難」究竟能意味著什麼，要一絲不苟——對我們將要研究的那些問題而言，它意味著「目前不知道有多項式時間演算法」，這是一句關於當前知識狀態的陳述，而非一個「不可能」的證明。把後者錯當成前者，是這整門學問裡最深的陷阱。
所以這一階要往哪裡去，這裡看得出來。我們有兩個類別、P 包含於 NP，以及它們之間那道沒人能合上、揮之不去的鴻溝。而令人振奮的發現——也就是接下來幾篇的主題——是：大量自然的 NP 問題彼此等價：只要在多項式時間內解出其中任何一個，你就解出了它們全部，把 P 與 NP 一舉壓合在一起。把它們串起來的工具，是多項式時間歸約；而它們全都歸約過去的那些鎮山之寶，就是 NP 完全問題。決定性問題、P 類與 NP 類，正是支撐起那整座結構的三個定義。