NP 類（class NP）
/ en-pee /
有些是非問題從零開始「回答」很難，但一旦有人連同提示把答案交給你，「檢查」就很容易。「這個巨大的數獨有解嗎？」單獨判定可能要耗上大把時間——但若朋友給你看一格已填好的盤面，你瞬間就能驗證它是否為合法解。「這個數是兩個大質數 p 與 q 的乘積嗎？」很難破解，但若有人悄悄告訴你 p 與 q，驗證起來易如反掌。NP 就是所有具有這種風味的決定問題所成的類別：每個「是」的答案都附帶一個簡短的提示（憑證），讓你能快速確認它。
精確地說，一個決定問題屬於 NP，若存在一個多項式時間的「驗證器」：一個決定性演算法 V，吃進輸入 x 與一段額外字串 c（憑證，長度為 |x| 的多項式），在多項式時間內執行，並具有此性質——若 x 的真實答案是「是」，則「存在某個」憑證 c 使 V 接受；若答案是「否」，則「沒有任何」憑證能使 V 接受。所以「是」的實例擁有一個你能快速檢查的、有說服力的簡短證明，而「否」的實例則無法被任何證明偽造。另一個等價定義用到非決定性：一台機器可以一舉「猜中」憑證再驗證它；這幅「猜了再查」的圖像，正是歷史名稱「非決定性多項式時間」的由來。注意其中內建的不對稱：NP 講的是容易檢查的「是」答案；對「否」答案的對應保證則定義出另一個類別 co-NP。
每個屬於 P 的問題也屬於 NP（若你能快速「解出」它，當然也能快速「檢查」它——忽略提示重解一遍即可），所以 P 坐落於 NP 之內。那個價值百萬美元的未解問題是：兩者是否其實相等？每個能快速檢查的問題是否也能快速解出？幾乎所有人都相信 P 不等於 NP，但沒人證明過。NP 龐大而實用——它包含可滿足性、旅行推銷員的決定問題、圖著色、排程，以及上千個其他問題——這正是為什麼理解它的內部結構（P、NP 完全、NP 中間）如此重要。
子集合加總：給定數字 {3, 34, 4, 12, 5, 2} 與目標 9，存在加總為 9 的子集合嗎？要找出一個，可能得搜許多子集合。但若憑證說「{4, 5}」，你只要加 4 + 5 = 9 並檢查這些元素確實在集合中——幾步就好。這個容易檢查的「是」之證明，正是把子集合加總放進 NP 的原因。
NP：每個「是」都有一個簡短憑證，能被多項式時間驗證器確認。
常見迷思：以為 NP 意指「非多項式」或「困難」。並非如此——它代表「非決定性多項式」，講的是「是」答案的「容易檢查」。P 是 NP 的子集，所以「屬於 NP」也包含所有簡單問題；NP 不是難解問題的集合。