NP 類（class NP）

想像一幅拼到一半的拼圖。從零開始把它拼完可能要花很久，但若朋友遞給你一幅已完成的圖、聲稱它是對的，你幾乎能瞬間「檢查」：只要掃一眼，確認每塊都吻合即可。NP 正是這種味道的判定問題類：答案也許難「找」，但一旦有人遞上候選答案，就容易「驗證」。它的「是」答案會附帶一段你能快速檢查的短證據。

形式上，一個判定問題（對輸入的是非提問）屬於 NP，是指存在一個驗證器：一個確定型演算法，接收輸入連同一段叫做證書（或見證）的額外字串，並在輸入大小的多項式時間內執行完畢。規則是單邊的。若真實答案為「是」，則「存在」某個證書能讓驗證器在多項式時間內回答「是」。若真實答案為「否」，則「沒有」任何證書騙得過它。例如要問「這張圖有沒有大小為 50 的團？」，證書就只是一份 50 個頂點的清單；驗證器在多項式時間內檢查其中每一對都有邊相連。

NP 涵蓋了大量真實問題：排程、路由、裝箱、電路設計、蛋白質摺疊模型、解謎。幾乎每個「尋找一個滿足某些限制的結構」的問題都落在 NP 裡，因為找到的結構本身就是一份易檢查的證書。深層的謎團是：易「檢查」是否也讓問題易「求解」？這就是 P 對 NP 問題，沒有人知道答案。我們確知的是 P 包含於 NP，而且 NP 有一群最難的成員——NP 完全問題——它們同生共死。