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