NP 困難（NP-hardness）
/ en-pee hard /
有些問題「至少和 NP 中最難的問題一樣難」，難到只要其中任何一個有了快速演算法，就能為其餘上千個解鎖快速演算法。我們稱這樣的問題為 NP 困難。直覺是：它是一個萬用瓶頸——NP 中每個問題都能被改寫成它的一個特例，所以攻破它就攻破了所有。「NP 困難」是一個強烈的難度宣告，而且（在普遍相信的 P 不等於 NP 之下）幾乎保證不存在多項式時間演算法。
精確地說，一個問題 H 是 NP 困難，若 NP 中「每一個」問題 A 都透過多項式時間歸約歸約到 H：對所有 A 屬於 NP 都有 A <=p H。因為 <=p 會保持並串接，這單一條件意味著 H 的多項式時間演算法將為 NP 中每個問題給出多項式時間演算法（先翻譯再求解），把 P 與 NP 塌縮為一。實務上你幾乎從不直接檢查「所有 A 屬於 NP」。你改用遞移性：一旦你知道某個問題（例如 SAT，由庫克-列文定理）是 NP 困難，你就藉由把 SAT（或任何已知的 NP 困難問題）歸約「到」H 來證明新問題 H 是 NP 困難。既然 NP 中一切都已歸約到 SAT，且 SAT <=p H，NP 中一切便都歸約到 H——大功告成。方向是全部關鍵：把一個「已知困難」的問題歸約進你的目標。
兩個誠實的要點。第一，NP 困難「不」要求該問題屬於 NP。停機問題與 TSP 的最佳化版本（「找最短旅程」，而非「存在長度 <= B 的旅程嗎？」）是 NP 困難卻不屬於 NP——它們可能更難，停機那個甚至是不可判定的。一個「既是 NP 困難又屬於 NP」的問題，是那個特殊而核心的情形，稱為 NP 完全。第二，NP 困難不是指數難度的「證明」：P 對 NP 仍未解，所以「NP 困難」形式上意指「除非 P = NP，否則無多項式演算法」，而非「可證明需要指數時間」。不過實務上，它是停止尋找精確快速演算法、轉而開始『應對』的標準、有充分根據的理由——做近似、限制輸入，或在小規模情形上接受指數時間。
要證明頂點覆蓋是 NP 困難，你「不」需列舉整個 NP。你把單一個已知困難的問題 3-SAT 歸約到它：給定一個 3-SAT 公式，你建出一張圖與一個數 k，使得「該圖有大小為 k 的頂點覆蓋」恰好在「公式可滿足」時成立。既然 3-SAT 是 NP 困難且 3-SAT <=p vertex-cover，頂點覆蓋便透過遞移性繼承了 NP 困難性。
證明 NP 困難，要把一個已知 NP 困難問題歸約「進」你的問題——絕不反過來。
NP 困難不等於「屬於 NP」，也不能證明需要指數時間（P 對 NP 未解）。它意指「和 NP 中任何問題一樣難」。致命的方向錯誤：把你的問題歸約「到」一個已知困難問題什麼都證明不了——你必須把那個已知困難問題歸約到你的問題。