ある問題の、とある性質

クラスNPの全ての問題より、同等以上に難しい問題

その問題自体はクラスNPに入っていないかもしれないが、NPに含まれる任意の問題が、その問題に多項式時間還元であるときに言う

これは別に決定問題でなくてもいい

つまりyes/noで答えられる問題でなくても良い

クラスNPに属すかどうかはわからないので。

定義

ある問題\varphiが以下を満たすこととき、\varphiはNP困難である、と言う

\forall\alpha\in NPに対して、\alpha\le^p_m \varphi

\le^p_mは、多項式時間還元

NP困難な問題の例

以下はNP完全かつNP困難

参考