2008年11月22日 (土) 02:12時点における版編集 218.251.73.212 (会話) Undo revision 23015632 by 203.124.68.208 (会話) ← 古い編集		2008年11月25日 (火) 03:46時点における版編集取り消し Caspar (会話 \| 投稿記録) 拡張承認された利用者 1,279 回編集訳語、カッコ、他「NP困難な問題の例」についてen:NP-hard（版：18:14, 10 November 2008）より補訳新しい編集 →
1行目: [[Image:P_np_np-complete_np-hard.svg\|thumb\|300px\|right\| [[P (計算複雑性理論)\|P]]、[[NP]]、[[NP完全問題\|NP完全]]、[[NP困難]]の相関を表す[[ベン図]]]] '''NP困難''' (（-こんなん、NP-~~hard)~~hard）とは[[計算複雑性理論]]における問題のクラスの1つ。直観非形式的に言えば「[[NP]]に属する最も難しい問題と比べて、少なくとも同等以上に難しい」問題である。問題 ''H'' がNP困難のクラスに属するとは、「[[NP完全問題]]に属する何れかの問題 ''L'' が ''H'' へ[[チューリング還元]]可能である」と定義される。即ち<math>\scriptstyle L\, \leq\,_T H</math>であり、NP困難問題を解ける[[神託機械]]がもしあれば、それを利用してNP完全問題を多項式時間で解くことができる。<br> NP完全問題とは、NPの任意の問題から[[多項式時間変換\|多項式時間帰着]]可能であり、かつ、<u>NPに属する</u>問題である。これと異なり、NP困難である問題は<u>NPに属するとは限らない</u>。[[P (計算複雑性理論)\|P]]や[[NP]]は[[決定問題]]のクラスなので、NP完全もまた決定問題に限られるが、NP困難には決定問題、[[検索問題]]([[:en:Search problem\|en]])、[[最適化問題]]など様々な問題が属しうる。 18行目: ==NP困難な問題の例== [[停止問題]] - NP困難だがNP完全ではない決定問題。NP困難であることは、例えば[[充足可能性問題]]を停止問題に容易に還元できることから言える（充足できる解を見付けたら停止し、そうでない場合は無限ループするような[[チューリングマシン]]の停止問題を考えればよい）。NP完全でないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることに拠る。但し、NP困難でありかつNP完全でない問題の全てが決定不可能という訳ではない。例えば[[TQBF問題]]([[:en:True quantified Boolean formula\|en]])は[[PSPACE]]で決定可能だが、多分NPではない。 [[停止問題]] - NP困難だがNP完全ではない決定問題。 [[巡回セールスマン問題]] - 最適化問題。 [[ハミルトン閉路問題]] - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。

「NP困難」の版間の差分