P 、NP 、NP完全 、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困難に属する問題は実社会において需要が大きい分野でもある。
もし、いずれかのNP困難な問題を多項式時間 で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。ところが、P＝NPが成立しても「任意の NP困難な問題が多項式時間で解ける」とは言えない。この関係を右上のベン図 に示す。
停止問題 - NP困難だがNPではない決定問題。なぜなら、停止問題は決定不可能という問題クラスに属しており、決定不可能はNPより困難で、かつ決定不可能とNPは互いに素だからである。具体的に示すには、NP困難であることは、例えば充足可能性問題 を停止問題に容易に還元できることから言える（充足できる解を見付けたら停止し、そうでない場合は無限ループするようなチューリングマシン の停止問題を考えればよい）。NPでないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることによる。ただし、NP困難でありかつNP完全でない問題の全てが決定不可能というわけではない。例えばTQBF問題 (en )はPSPACE で決定可能だが、多分NPではない。ハミルトン閉路問題 - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。部分和問題 - ナップサック問題の特殊ケース。NP困難かつNP完全な決定問題。
NPに関連するクラスの名称はまぎらわしい。「NP困難」はクラス名に「NP」と付くのに、全てがNP というわけではない。しかし現状では定着した名称なので、いまさら変わりそうにない。とはいえ、NPを中心に置いた上でそれなりに体系があるのも事実である。
NP完全
NPの中では 「完全」な問題を意味する。つまりNPの中では 最も解くのが難しい。
NP困難
「少なくとも」NPと同等以上に難しい問題（ただし、NPに属する とは限らない）。
NP-easy
「たかだか」NPと同等以下しか難しくない問題（ただし、NPに属する とは限らない）。
NP-equivalent
NPと同等に難しい問題（ただし、NPに属する とは限らない）。
^ B.コルテ (2012). 組合せ最適化 第2版 (理論とアルゴリズム) . 丸善. ISBN 978-4621062029
P≠NP予想 NP完全問題 多項式時間変換 - 多対一還元やチューリング還元に計算時間の制限を付加したもの。チューリング還元 - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Cook還元と呼ぶ。多対一還元 - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Karp還元と呼ぶ。単に「多項式変換」と書けば通常 Karp還元を指す。実用的な時間で解けるクラス 実用的な時間で解けないと疑われているクラス 実用的な時間では解けないクラス クラス階層 クラスの族
一覧 ・カテゴリ
