[用語] NP困難

NP困難 - Wikipedia

NP困難（エヌピーこんなん、英: NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである^[1]。正確にいうと問題 HがNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。

NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。

上に挙げた定義から、問題 H がNP困難なとき次のことが言える（以下は定義ではなく主張）。

• すべてのNP完全問題は H に還元して多項式時間で解ける。またNPに属する全ての問題も H に還元できる。
• もし最適化問題 H の特殊例としてNP完全な決定問題 L を考えられるなら、H はNP困難である。

NP困難な組合せ最適化問題は、一般に最適解を求めるのが非常に困難であると考えられているため、近似アルゴリズムに関しても研究されている。