NP 困難（NP-hard）
稱一個問題為 NP 困難，是說「它至少和 NP 中每個問題一樣難」。想像一把萬能鑰匙：若你對這一個問題有快速演算法，你就能解開整個 NP。一個問題贏得這個標籤，不是靠它本身屬於 NP，而是靠它是個「每個 NP 問題都能被高效翻譯進去」的目標。它位於「至少一樣難」的那一端，對它實際上能有多難並無上限。
形式上，問題 B 是 NP 困難，是指 NP 中每個問題 A 都多項式時間歸約到 B，即對所有 NP 中的 A 都有 A <=p B。把任一 NP 問題翻譯成 B 並解 B，就會解出那個 NP 問題，所以 B 背負了整個類別的難度。注意「不」要求什麼：B 本身不必屬於 NP。NP 困難問題可以遠在 NP 之外。像「找出『最短』推銷員路線」（而非只問「有沒有長度低於 L 的路線？」）這類最佳化問題、停機問題、乃至更難的問題，全都是 NP 困難，但其中有些根本不屬於 NP，因為它們的「是」答案缺少短而可檢查的證書。
實務上你幾乎從不從定義去證明 NP 困難（要歸約「整個」NP 令人卻步）。你改用遞移性：取一個已知 NP 困難的問題，例如 3-SAT，把「它」歸約到你的問題 B。既然每個 NP 問題都歸約到 3-SAT、而 3-SAT 又歸約到 B，每個 NP 問題就都到得了 B。最重要的單一後果：若任何一個 NP 困難問題屬於 P，則 P 就會等於 NP。這就是為何發現你的問題是 NP 困難，是個強烈訊號——別再追快速精確演算法，改去設法應對這份難度。
最佳化版 TSP，「輸出最短長度的路線」，是 NP 困難但不屬於 NP。我們可把 NP 完全的判定版 TSP 歸約到它，所以它至少和 NP 一樣難。然而單一條最短路線並非顯而易見的短證書：要確認某條路線「就是」最短，似乎得排除所有其他路線，所以它未知是否屬於 NP。
NP 困難＝至少和整個 NP 一樣難。它「不必」屬於 NP；最佳化版通常是 NP 困難但落在 NP 之外。
NP 困難不蘊含屬於 NP。一個既是 NP 困難「又」屬於 NP 的問題才是 NP 完全；落在 NP 之外的 NP 困難問題（如許多最佳化版）很難但不是完全。