NP困難
NP-Hard
その問題自体はクラスNPに入っていないかもしれないが、NPに含まれる任意の問題が、その問題に多項式時間還元であるときに言う https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/300px-P_np_np-complete_np-hard.svg.png
つまりyes/noで答えられる問題でなくても良い
クラスNPに属すかどうかはわからないので。
定義
ある問題$ \varphiが以下を満たすこととき、$ \varphiはNP困難である、と言う $ \forall\alpha\in NPに対して、$ \alpha\le^p_m \varphi
NP困難な問題の例
参考