NP 完全（NP-completeness）
/ en-pee com-PLEET /
在龐大的 NP 類之中，坐著少數特殊問題，它們在精確的意義下是「整群裡最難的」——而且了不起的是，它們全被綁在一起：只要快速解出其中任何一個，你就快速解出了全部。這些就是 NP 完全問題。它們是 NP 的承重支柱：可滿足性、旅行推銷員的決定問題、圖著色、團、子集合加總，以及從物流到生物學到晶片設計的上千個問題。當人們說某問題「NP 完全」，意思是它既真正屬於 NP，又和 NP 中任何問題一樣難。
精確地說，一個問題 L 是 NP 完全，若它滿足「兩個」條件：(1) L 屬於 NP——「是」實例有簡短、可在多項式時間檢查的憑證；且 (2) L 是 NP 困難——NP 中每個問題都在多項式時間內歸約到 L。第一個條件不讓 L 荒謬地難（它是 NP 的真正成員，不是某個不可判定的東西）；第二個條件讓它成為萬用標靶。兩者合起來把 L 釘在 NP 的最頂端。條件 (2) 那驚人的後果，就是「全有或全無」的塌縮：若「哪怕一個」NP 完全問題竟屬於 P，那麼透過歸約，NP 中「每個」問題都將屬於 P，給出 P = NP。反之，若 P 不等於 NP（如幾乎所有人所信），則「沒有」任何 NP 完全問題有多項式時間演算法。所以所有 NP 完全問題共享同一命運；它們同生共死。要證明一個新問題 L 是 NP 完全，你要證明兩件事：L 屬於 NP（給出憑證與驗證器），且 L 是 NP 困難（把一個已知的 NP 完全問題，如 3-SAT，歸約到 L）。
這個概念是演算法設計中最具後果的一個，因為它告訴你該「做什麼」。發現你的問題是 NP 完全，並非個人的失敗，也不是你該更努力的訊號；它是一條定理，說地球上沒人有它的多項式時間演算法，而找到一個將是歷史性的突破（與百萬美元的獎金）。誠實而務實的回應，是停止尋找精確、快速、通用的演算法，轉而『應對』：接受附帶可證明保證的近似答案、限制在特殊輸入上（小參數、樹狀結構）、使用對你面對的規模而言夠聰明的指數時間方法，或套用啟發式。要保持誠實的一個提醒：「NP 完全」是最壞情況、漸進的判決；許多 NP 完全問題在真實實例上被好的求解器例行地解出，因為真實輸入並非刻意刁難。
SAT 是最初的 NP 完全問題（庫克-列文）。要證明 3 著色性也是 NP 完全：(1) 它屬於 NP，因為一個著色是簡短憑證，掃過各邊即可檢查；(2) 它是 NP 困難，靠已知的歸約 3-SAT <=p 3 著色。兩格都打勾，所以 3 著色性是 NP 完全——並與 SAT 共享完全相同的命運。
NP 完全＝屬於 NP「且」是 NP 困難。只要其中一個屬於 P，整個 NP 都屬於 P（P = NP）。
NP 完全不是「該問題需要指數時間」的證明——P 對 NP 未解。它意指：沒有已知的多項式演算法，而找到一個就解出「全部」。此外，這個最壞情況標籤並不妨礙求解器攻破許多真實實例；要『應對』，不要放棄。