從「求解它」到「檢查它」
上一篇遞給你一份乾淨的是／否問題清單，以及對 P 類的第一幅圖像——單一演算法能在多項式時間內判定的那些問題。它也對 NP 類做了第一個較粗略的手勢。本篇把那個手勢說精確，而關鍵的一步是：別再問「我們能不能快速找到答案？」，改問「若有人聲稱答案是『是』並遞給我們證據，我們能不能快速檢查它？」這是天差地別的兩個問題，而兩者之間的鴻溝，正是這一整階的故事。
用一個數獨謎題把它具體化。從空白格子白手起家地填，感覺是真的難；你可能得嘗試、回溯、再嘗試。但若朋友把一張填好的格子推過桌面，聲稱它解開了這道謎，檢查他就輕而易舉：掃過每一列、每一行、每一宮，確認各自都裝著 1 到 9 且無重複。這個檢查只是在格子上跑幾遍——又快又機械。求解很難；檢查一個被提出的解卻很容易。NP 正是給「這件事為真」的那些問題的精確名稱。
憑證與驗證器
讓我們把這兩個零件命名。朋友遞給你的「證據」是一張憑證 certificate（也稱見證 witness 或證明 proof）——一串額外的資訊，對一個「是」實例而言，它指出答案為何是「是」。那台機械檢查者是驗證器 verifier：一個普通的決定性演算法，它同時接受原始實例與憑證，輸出接受或拒絕。這兩者的配對，就是 NP 的驗證器定義的核心。
這個定義必須謹慎陳述，因為草率的版本會把每一個問題都放進來。一個問題屬於 NP，若存在一台驗證器 V，其執行時間對實例規模呈多項式，並具備兩條性質。完備性 completeness：若實例是「是」實例，則存在某張憑證能使 V 接受。健全性 soundness：若實例是「否」實例，則沒有任何一張憑證——一張都沒有——能矇騙 V 去接受。驗證器必須既慷慨到足以辨認出一份真正的證明，又嚴格到讓假的證明永遠失敗。
兩條規模約束讓這件事誠實，而少了任一條都會破壞這個類。第一，驗證器在多項式時間內執行。第二——這條較微妙——由此推得只有長度為多項式的憑證才可能起作用：一台執行時間為 p(n) 的驗證器,連讀完一張長度超過 p(n) 個符號的憑證都辦不到，所以不失一般性,憑證受 n 的某個多項式所界定。若你允許指數長的憑證，你就能把整張答案表偷渡進來，這個類便會坍縮成無意義的東西。簡短的證明、快速的檢查：兩個詞都承重。
一個實作過的驗證器：SAT
最乾淨的例子是 可滿足性問題 SAT。一個實例是一個布林公式，變數為 x1, x2, ..., xn——比方說 (x1 OR NOT x2) AND (x2 OR x3) AND (NOT x1 OR NOT x3)。問題是個是／否決定：是否存在一組把真／假指派給變數的賦值，使整個公式為真？要找到這樣一組賦值，似乎得在 2^n 種可能中搜尋。但驗證其中一組,卻便宜到近乎令人不好意思。
這裡的憑證就只是一組被提出的賦值——每個變數一個真／假值，剛好 n 個位元長。驗證器把這些值代進公式並求值：走過每個子句，檢查它的字面量中是否至少有一個為真，唯有當每個子句都被滿足時才接受。對一個長度為 m 的公式求值花費 O(m) 時間，輕鬆地落在多項式之內。現在對照定義檢查那兩條性質。
- 完備性：若公式可滿足，則依定義存在一組滿足賦值——把那組賦值當作憑證遞上，驗證器求值得到真並接受。
- 健全性：若公式不可滿足，則沒有任何賦值能使它為真，所以不論獻上什麼字串當憑證，要嘛求值得不到真,要嘛根本不是合法賦值——驗證器每次都拒絕。
- 規模：憑證是 n 個位元而檢查是 O(m)；兩者對實例皆呈多項式，所以依驗證器定義,SAT 屬於 NP。
為何 P 坐落於 NP 之內
驗證器定義讓一個事實幾乎免費可得，而它值得一看，因為初學者往往覺得意外。P 中的每個問題也都在 NP 中。若你本來就能自己在多項式時間內求解一個問題，那麼你連一張有用的憑證都不需要,就能驗證「是」答案：造一台驗證器,讓它無視遞來的任何憑證,在實例上跑你自己的多項式時間解算器,並恰在解算器說「是」時接受。
那台驗證器確實是一台合法的 NP 驗證器。它在多項式時間內執行（它就只是你的解算器）。在一個「是」實例上,每張憑證都使它接受,所以當然有某張憑證使它接受——完備性成立。在一個「否」實例上,沒有憑證能使它接受,因為不論被無視的憑證是什麼,解算器自己都說「否」——健全性成立。所以 P 包含於 NP,記作 P ⊆ NP。憑證之所以淪為免費的形式,正是因為求解本來就容易。
反方向是那個價值連城的問題。每個「是答案易於檢查」的問題,是否也都是「答案易於尋找」的問題？這是在問是否 NP ⊆ P,而它與 P ⊆ NP 合起來就會意味著 P = NP。沒有人知道。誠實的現況是：P 對 NP 仍懸而未決——普遍相信 P ≠ NP,但相信不等於證明。把這份謙遜放在心頭最前:這一階接下來的內容,展示的是這個領域如何圍繞一個它尚無法回答的問題來組織自己的知識。
非決定性：同一個觀念,一位幸運的猜測者
還有第二種、更古老的方式來定義 NP,它看起來截然不同,卻描述著一模一樣的類——而看清它們為何一致,會加深整幅圖像。回想基礎那一階對 決定性機器與非決定性機器的區分。一個決定性演算法在每一刻恰有一個下一步。一台非決定性機器則是個思想實驗:當它遇到一個選擇時,被允許同時分支進所有選項,而只要任何單一分支抵達接受狀態,就說它接受了這個輸入。
友善的卡通版本,是一台會猜的機器。在每個分支點,它神奇地猜中正確的選擇,彷彿無限幸運,然後驗證它的猜測是否成立。NP 是非決定性機器能在多項式時間內判定的決策問題之類。這幅圖正是 猜測與驗證的模式:猜一個候選,再決定性地檢查它。而這正是兩個定義何以重合的原因——那串幸運的猜測,就是憑證。
把這個等價在兩個方向上各走一遍,它就咬合了。一台在多項式時間內判定某問題的非決定性機器,沿任一分支至多做出多項式次猜測;把那些被猜出的位元寫下來,你就有了一張多項式長度的憑證,而一邊從憑證讀出這些位元、一邊重播這台機器,就是一台決定性多項式時間驗證器。反過來,給定一台驗證器,造一台逐位元猜測憑證、然後執行驗證器的非決定性機器——它恰在存在一張接受憑證時於某分支上接受。兩個定義刻畫出的是同一個類,非決定性的觀點與驗證器的觀點,是同一枚硬幣的兩面。
nondeterministic decide(instance):
cert = GUESS a polynomial-length string # the lucky guess
return Verifier(instance, cert) # deterministic, poly-time
# accepts <=> SOME guessed cert makes Verifier accept
# <=> instance is a yes-instance這給我們帶來什麼,又沒帶來什麼
驗證器這副鏡片,把一整群頑固的問題重新納入同一個屋簷下。SAT、在圖中尋找漢米頓迴圈、判定子集和、圖著色、把背包裝到命中某個目標值——每一個看起來都像不同的野獸,卻各自共享 SAT 的形狀:一個「是」答案攜帶一張簡短憑證（一條巡迴、一個選定的子集、一種著色),一台簡單的決定性驗證器能在多項式時間內檢查它。那份共享的結構,正是接下來的篇章能夠比較它們困難度的根本原因。
但要對「屬於 NP」主張了什麼、又沒主張什麼保持精確,因為這些字眼容易招致過度解讀。說一個問題在 NP 中,只說了是答案擁有簡短、可檢查的證明。它對如何找到一張憑證隻字未提,更斷然沒說這個問題很困難——P 中的每個問題也都在 NP 中,如我們所見。誠實的總結:NP 是關於可檢查性的一層上層結構,而非困難度的判決。困難度的故事稍後才登場,當歸約讓我們得以把這些問題彼此排名時。
並把前面幾階的漸進告誡留在視野裡。「多項式時間驗證器」是一把漸進、與機器無關的量尺:它告訴你檢查的規模擴展是優雅的,而非它對你今天桌上那個 n 而言很快,因為像 n^6 這樣帶大常數的高次多項式,在不大的規模下也可能遲緩。多項式與指數成長之間的那條邊界,正是整套理論所劃下的界線——刻意地粗糙,也正因為它無視常數而強健。下一篇轉向 歸約,那個最終讓我們得以說「某個問題至少和另一個一樣難」的工具。