NP困難
【英】：NP hard
少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.
| グラフ･ネットワーク： | K-opt法 L凸関数 M凸関数 NP困難 PERT TSP多面体 クラスカル法 |
| 非線形計画： | 2次の最適性必要条件 2次計画問題 DC計画問題 NP困難 エラーバウンド カルーシュ・キューン・タッカー条件 カーマーカー法 |
| 線形計画： | 2次錐計画 NP困難 アフィン変換法 カーマーカー法 シンプレックス法 ポテンシャル関数 中心パス |
| 組合せ最適化： | 0-1整数計画 2次割当問題 AVL木 NP困難 TDI性 アルゴリズム オンラインアルゴリズム |
| スケジューリング： | 1機械問題 3つ組み記法 FMSスケジューリング NP困難 オープンショップ問題 ガントチャート グループスケジューリング |
| 計算幾何： | K-d木 NP困難 TSP多面体 アレンジメント ガブリエルグラフ スケルトン スラブ法 |
NP困難
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/24 14:08 UTC 版)
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困難に属する問題は実社会において需要が大きい分野でもある。
P≠NP予想との関係
もし、いずれかのNP困難な問題を多項式時間で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。ところが、P＝NPが成立しても「任意の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に属するとは限らない）。
- NP-easy
- 「たかだか」NPと同等以下しか難しくない問題（ただし、NPに属するとは限らない）。
- NP-equivalent
- NPと同等に難しい問題（ただし、NPに属するとは限らない）。
脚注
- ^ B.コルテ (2012). 組合せ最適化 第2版 (理論とアルゴリズム). 丸善. ISBN 978-4621062029
関連項目
NP困難
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/26 02:14 UTC 版)
計算複雑性理論の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、NP困難である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか（例えば「小さな」問題）が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。
※この「NP困難」の解説は、「組合せ最適化」の解説の一部です。
「NP困難」を含む「組合せ最適化」の記事については、「組合せ最適化」の概要を参照ください。
- NP困難のページへのリンク
