理論與進階主題
NP 完全性
NP 完全性是給一族問題貼的標籤，這族問題共享一種奇特的雙重性格：給出的答案可以被快速核驗，但要找到這個答案卻似乎得在一個巨大的空間裡搜尋、且沒有已知的捷徑。「NP」是這樣一類問題：它們的「是」答案附帶一份證書，你能在多項式時間內驗證。數獨是最親切的畫面：確認一張填好的盤面是否合法只要幾秒，可從空盤解起卻可能令人頭疼。NP 完全問題就是 NP 裡最難的那些。
它們的特殊之處由「歸約」刻畫。一個問題是 NP 完全的，當且僅當它屬於 NP，且 NP 裡的所有其他問題都能高效地變換成它——於是只要你為某一個 NP 完全問題找到了真正快（多項式時間）的演算法，就能把任何 NP 問題翻譯成它並一併快速解決。這正是它們被稱為「NP 裡最難」的原因：它們靠這些翻譯彼此牢牢綁在一起。著名成員有布林可滿足性（SAT）、旅行推銷員問題的判定版本（是否存在一條短於 k 的迴路？）、圖著色，以及背包問題。
它的現實意義令人清醒，卻很有用。如果你證明了自己的問題是 NP 完全的，這並不是說它不可能解——而是說當今地球上沒人知道一個能良好擴展的方法，因此死磕一個快速的精確演算法多半是白費力氣。你轉而該拿起別的工具：能逼近最優解的近似演算法、在實踐中表現良好的啟發式、對小規模輸入可行的精確求解器，或利用你手上資料的特殊結構。這個標籤是給你的努力改道，而非叫停。
// SAT, e.g. (a OR !b) AND (b OR c)
// Verifying a proposed assignment is fast:
bool satisfies(const Formula& f, const Assignment& a) {
for (const Clause& c : f.clauses)
if (!c.isTrueUnder(a)) return false; // O(total literals)
return true;
}
// But finding a satisfying assignment among 2^n possibilities
// has no known polynomial-time algorithm.核驗一個候選解是 O(公式大小)；搜遍所有賦值則是指數級。
NP 完全不等於「已證明不可能」——它意味著沒有已知的快速演算法，而只要為其中任何一個找到快速演算法，就能一舉攻破全部。
又稱
另見