NP困難

描述P, NP, NP完全，以及NP難之間關係的歐拉圖

NP困難（NP-hard,non-deterministic polynomial-time hard）問題是計算複雜性理論中最重要的複雜性類之一。某個問題被稱作NP困難，當所有NP問題可以在多項式時間圖靈歸約到這個問題。

因為NP困難問題未必可以在多項式的時間內驗證一個解的正確性（即不一定是NP問題），因此即使NP完全問題有多項式時間內的解，NP困難問題依然可能沒有多項式時間內的解。因此NP困難問題「至少與NPC問題一樣難」。