「NP困難」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【えぬぴーこんなん (NP hard)】''' 少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPと...') |
細 ("NP困難" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 00:40時点における版
【えぬぴーこんなん (NP hard)】
少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.