NP 完全（NP-complete）
NP 完全問題是 NP 中最難的問題，它們結成一個了不起的兄弟會：對「任何一個」的快速演算法，會立刻給出對「所有」的快速演算法，事實上是對 NP 中一切的快速演算法。它們全都互相多項式時間可歸約，所以在精確的意義上是同一個問題穿著不同戲服：SAT、團、著色、排程、路線。把一個高效解開，整座大廈就垮了。
一個問題是 NP 完全，須同時滿足兩個條件。第一，它「屬於」NP：其「是」答案具有短而能在多項式時間內檢查的證書。第二，它是「NP 困難」：NP 中每個問題都多項式時間歸約到它。第一個條件使它不至於難到無法驗證；第二個讓它與 NP 中任何東西一樣難。兩者合起來把它精確地釘在 NP 的頂端。因為每個 NP 完全問題都歸約到每個其他的（各自屬於 NP，故歸約到任何 NP 困難問題），它們全在多項式時間翻譯之下等價，這正是為何單一個突破會傳遍各處。
這是這套理論戲劇性的回報。若哪怕只有一個 NP 完全問題結果屬於 P，則 P＝NP，成千個重要問題會一舉變得可解；反之，若其中任一個被證明需要超多項式時間，則 P 不等於 NP，它們全都沒有快速演算法。Cook-Levin 定理給了我們第一個 NP 完全問題 SAT，Karp 等人接著靠一連串歸約抵達了龐大的工具箱。當你證明自己的問題是 NP 完全，你同時做兩件事：證明它屬於 NP（給出一個驗證器），並證明某個已知的 NP 完全問題歸約到它。
要證明 3-SAT 是 NP 完全：(1) 它屬於 NP，因為一個真值賦值就是可在線性時間內檢查的證書；(2) 它是 NP 困難，因為 SAT（由 Cook-Levin 證明為 NP 困難）藉由把每個長子句改寫成一串帶新變數的三文字子句而歸約到 3-SAT。屬於 NP 加上 NP 困難，就等於 NP 完全。
NP 完全＝屬於 NP 且 NP 困難。所有 NP 完全問題互相多項式時間可歸約，所以它們同生共死。
兩半都不可或缺。少了「屬於 NP」就只是 NP 困難（可能難得多，如停機問題）。NP 完全正是這兩者的交集。