NP困難 - mrsekut-p

NP困難

NP-Hard

ある問題の、とある性質

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

その問題自体はクラス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

$ \le^p_mは、多項式時間還元mrsekut.icon

NP困難な問題の例

参考