「NP困難」の版間の差分
削除された内容 追加された内容
m編集の要約なし |
|||
1行目:
[[ファイル:P_np_np-complete_np-hard.svg|thumb|300px|right| [[P (計算量理論)|P]]、[[NP]]、[[NP完全問題|NP完全]]、
'''NP困難'''（エヌピーこんなん、{{lang-en-short|NP-hard}}）とは[[計算量理論]]において、問題が「[[NP]]に属する任意の問題と比べて、少なくとも同等以上に難しい」ことである<ref>{{cite book
|title=組合せ最適化 第2版 (理論とアルゴリズム)
|year=2012
|isbn=978-4621062029
22行目:
===決定問題===
*[[停止問題]] - NP困難だがNPではない決定問題。なぜなら、停止問題は決定不可能という問題クラスに属しており、決定不可能はNPより困難で、かつ決定不可能とNPは互いに素だからである。具体的に示すには、NP困難であることは、例えば[[充足可能性問題]]を停止問題に容易に還元できることから言える（充足できる解を見付けたら停止し、そうでない場合は無限ループするような[[チューリングマシン]]の停止問題を考えればよい）。NPでないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることによる。ただし、NP困難でありかつNP完全でない問題の全てが決定不可能というわけではない。例えば[[TQBF問題]]([[:en:True quantified Boolean formula|en]])は[[PSPACE]]で決定可能だが、多分NPではない。
*[[ハミルトン閉路問題]] - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。
*[[部分和問題]] - ナップサック問題の特殊ケース。NP困難かつNP完全な決定問題。
===組合せ最適化問題===
| |||