NP困難
NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。
上に挙げた定義から、問題 H がNP困難であるときには次のことが言える(以下は定義ではなく主張)。
すべてのNP完全問題は H に還元して多項式時間で解ける。またNPに属する全ての問題も H に還元できる。
もし最適化問題 H の特殊例としてNP完全な決定問題 L を考えられるなら、H はNP困難である。
NP困難な組合せ最適化問題は、一般に最適解を求めるアルゴリズムが計算完了までに指数関数時間を必要とするなどして、非常に困難であると考えられているため、近似アルゴリズムが多数考案されている。また、数理的に解く従来からのアプローチの他に、ディープラーニングの応用なども盛んに行われている。量子コンピュータでは最適解をリアルタイムで求める方法も試みられている。