NP困難

提供: ORWiki
2007年7月20日 (金) 00:40時点におけるOrsjwiki (トーク | 投稿記録)による版 ("NP困難" を保護しました。 [edit=sysop:move=sysop])
ナビゲーションに移動 検索に移動

【えぬぴーこんなん (NP hard)】

少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.