驗證器、證書與非確定性

一眼就能驗收的拼圖

想像一幅一千片的拼圖。從零拼好它可能吃掉你整個下午，但如果有朋友把一幅拼好的圖遞到你面前，你幾秒鐘就能確認它對不對——每片都嚴絲合縫，圖案完整。動手做和驗收之間的這道鴻溝，正是 NP 類的靈魂。一個問題屬於 NP，是說對每個「是」實例，都存在一份簡短的證明——一幅拼好的圖——你能很快檢視它，即使要你自己找出那份證明看起來慢得要命。

我們把這幅畫面拆成兩個有名字的零件。朋友拼好的那幅圖是一份證書（也叫見證 witness）：一串額外資訊，為「是」這個答案作擔保。而把它看一遍、判定它有效的動作，由一個驗證器完成：一台普通的、確定型的演算法，它吃進原始輸入連同一份候選證書，然後輸出接受或拒絕。驗證器從不需要解開拼圖，它只是稽核別人提出的某個解。

有兩個條件讓一個驗證器是誠實的，而且兩者都要緊。健全性（soundness）：如果輸入是「否」實例，那麼沒有任何證書能騙過驗證器、害它接受。完備性（completeness）：如果輸入是「是」實例，那麼至少存在一份證書，能讓驗證器接受。拿一個可滿足的布林公式當輸入（布林可滿足性問題，本級稍後的主角）：證書不過就是給各變數指派真／假的一組賦值，而驗證器只要把它代進去、求個值。代入很快；要搜遍全部 2^n 種賦值，才是那看起來慢的事。

多項式的那行小字

「簡短」和「很快」這兩個字都得長出牙齒，否則 NP 會把一切都吞下去。那對牙齒是兩個綁在輸入規模 n 上的多項式界。第一，證書必須是多項式有界的：它的長度至多 p(n)，其中 p 是某個固定的多項式。第二，驗證器必須在輸入長度上以多項式時間執行——也就是對某常數 k 跑在 O(n^k) 之內。乾淨地說：一個語言 L 屬於 NP，恰好當存在一個多項式時間的驗證器 V 與一個多項式 p，使得對每個 x，x 屬於 L 若且唯若存在一份長度至多 p(|x|) 的證書 c，讓 V(x, c) 接受。

這個定義悄悄白送你一個漂亮的事實：P 包含於 NP。如果一個問題本來就能在多項式時間內、不靠外援地解出，那它當然有一個多項式時間的驗證器——一個乾脆無視證書、自己把問題解掉的驗證器。所以你永遠可以遞上空字串當作「什麼都不做」的證書。每個 P 問題都是一個帶著瑣碎見證的 NP 問題。那個深刻而懸而未決的問題，是反過來成不成立——容易檢查是否就逼得容易求解。我們會在本級結尾遇到它，也就是 P 對 NP 問題；眼下，只要記住 P 舒舒服服地坐在 NP 裡頭就好。

把自己複製出去：非確定型的觀點

還有第二種同樣著名的定義 NP 的方式，而字母 N 真正的出處就在這裡。回想你在 NFA 那裡見過的非確定型機器，那時的非確定性意思是「把自己複製出去，同時試遍每一條分支」。把那個想法搬到一台圖靈機上，並讓它跑多項式那麼多步。在每一步，機器可能面對好幾個合法的動作；它不是挑一個，而是分裂成若干份副本，每一份各走一個不同的動作。只要這棵爆炸式增長的副本樹上有任何一條分支抵達接受狀態，這台機器就接受它的輸入。

一台非確定型圖靈機若每一條分支都在 p(n) 步內停機（p 是某多項式），就說它跑在多項式時間。在這個觀點下，NP 類恰好就是被這類機器所判定的語言之集合。它與驗證器圖像之間的連結，直接到幾乎令人不好意思：那條幸運的接受分支所做的一連串猜測——這裡向左轉、那裡把這個變數設為真——就是那份證書。非確定型機器非確定地猜出一份證書；驗證器檢查遞給它的一份證書。同一枚硬幣的兩面。

從驗證器到機器：給定一個多項式時間驗證器 V，造一台非確定型機器，它先非確定地寫下一份長度至多 p(n) 的證書 c（每個分支選擇對應一個符號），再確定地執行 V(x, c)，並恰好在 V 接受時接受。
從機器到驗證器：給定一台多項式時間的非確定型機器，把證書取為某一條分支上所做選擇的清單。驗證器確定地重放那條分支——不再需要猜，只是照著記錄下來的選擇走——若那條分支接受就接受。
兩個方向的翻譯都跑在多項式時間，並且原封不動地保留「接受與否」，因此這兩個定義指的是同一個類。你愛用哪個鏡頭都行；複雜度理論家無時無刻在兩者之間切換。

那個死不掉的迷思：「NP 代表非多項式」

這是整個複雜度理論裡最常見的一個誤解，你應該要能一眼就把它拍掉。NP 不是「非多項式（non-polynomial）」的縮寫。它是 Nondeterministic Polynomial time（非確定型多項式時間）——非確定型機器上的多項式時間。那個 N 修飾的是機器，不是時間。這個錯誤之所以誘人，是因為太多著名的 NP 問題確實看起來都需要指數時間才解得出來；但「看起來需要」是一個關於難度的猜想，不是烙進名字裡的事實，更不是這幾個字母的意思。

如果你還是感到迷思的拉力，就讓 P 位於 NP 之內這件事來平息它。排序、最短路徑、檢驗一個數是不是質數——這些全都住在 P 裡，而 P 是 NP 的子集，所以它們每一個也都在 NP 裡。一個你能在 O(n log n) 內解掉的問題，就是一個 NP 問題。倘若 NP 真的代表非多項式，這句話就會自相矛盾；事實上它只是一句日常的真話。NP 不是「困難」的同義詞。它是一個精確的成員資格條件：存在一份簡短的證書，且能被快速檢查。

趁著整理名詞，再做一次誠實的查核。大 O 是最壞情況成長率的上界，不是確切的執行時間，也不是典型情況——一個 O(n^2) 的驗證器，在大多數輸入上可能眨眼就跑完。而多項式這個界是一個粗糙的承諾：一個跑 n^100 步的演算法是「多項式的」，卻在任何真實輸入上都完全沒用。所以「屬於 P」和「在實務上真的快」並不是同一句話。理論之所以畫下多項式／指數這條線，是因為它穩健又乾淨，不是因為每個多項式都友善。

一個從頭到尾走完的驗證器

我們用一個小到能裝進腦袋的例子，把抽象變具體：團問題（稍後造歸約時我們還會倚重它）。輸入是一張圖 G 和一個數 k，「是」的問題是：G 裡有沒有 k 個彼此兩兩相連的頂點——一坨大小為 k、彼此全連的疙瘩？用蠻力找這樣一坨，意味著檢查所有大小為 k 的子集，而這種子集的數目可能多到天文。但檢查一坨被提議出來的疙瘩，卻是輕而易舉。

input  : graph G on vertices V, target size k
certif.: a list S of vertices, e.g. S = [v2, v5, v7]   (for k = 3)
verifier V(G, S):
  1. check |S| = k                         -> O(1)
  2. check every vertex in S is in V       -> O(k)
  3. for each pair {u,w} in S:
        check edge (u,w) is present in G    -> O(k^2) pairs
  4. accept iff all checks pass
total work: O(k^2) edge look-ups  =>  polynomial in input size

團問題的一個多項式時間驗證器：證書就是那坨疙瘩本身；檢查它，不過是數一數、再確認各條邊在不在。

把那兩個誠實條件走一遍。健全性：如果 G 確實沒有 k-團，那沒有任何清單 S 能通過第 3 步——總會缺某條該有的邊，於是驗證器拒絕每一份證書。完備性：如果存在一個 k-團，那把它的頂點當作 S 遞進去，就會順順地通過全部四項檢查，於是存在某份接受的證書。驗證器的開銷，O(k^2) 次查邊，是 G 規模上的多項式。這就是團問題之所以坐在 NP 裡的全部理由，無論找出那個團最後會有多難。

把這個模板帶走，因為你日後寫的每一個 NP 成員資格證明都照它走。指名一份證書（一個「是」答案長什麼樣？），描述一個稽核它的驗證器，論證證書很短（多項式有界），再論證稽核很快（多項式時間）。把這四行寫對，你就證明了這個問題屬於 NP。下一篇我們把視角從成員資格翻轉到關係——一個多項式時間歸約，如何讓一個這類問題的困難，沾染到另一個問題身上。