NP困難

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困難な組合せ最適化問題は、一般に最適解を求めるアルゴリズムが計算完了までに指数関数時間を必要とするなどして、非常に困難であると考えられているため、近似アルゴリズムが多数考案されている。また、数理的に解く従来からのアプローチの他に、ディープラーニングの応用なども盛んに行われている。量子コンピュータでは最適解をリアルタイムで求める方法も試みられている。NP困難に属する問題は実社会において需要が大きい分野でもある。