「NP困難」の版間の差分
ナビゲーションに移動
検索に移動
細 ("NP困難" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる. | 少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる. | ||
| + | |||
| + | [[Category:線形計画|えぬぴーこんなん]] | ||
| + | |||
| + | [[Category:非線形計画|えぬぴーこんなん]] | ||
| + | |||
| + | [[Category:組合せ最適化|えぬぴーこんなん]] | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|えぬぴーこんなん]] | ||
| + | |||
| + | [[Category:スケジューリング|えぬぴーこんなん]] | ||
| + | |||
| + | [[Category:計算幾何|えぬぴーこんなん]] | ||
2008年11月5日 (水) 16:49時点における最新版
【えぬぴーこんなん (NP hard)】
少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.