NP困難のソースを表示

[[ファイル:P_np_np-complete_np-hard.svg|thumb|300px|right| [[P (計算量理論)|P]]、[[NP]]、[[NP完全問題|NP完全]]、[[NP困難]]の相関を表す[[ベン図]]]]

'''NP困難'''（NPこんなん、NP-hard）とは[[計算量理論]]において、問題が「[[NP]]に属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 ''H'' がNP困難であるとは、「[[NP]]に属する任意の問題 ''L'' が ''H'' へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば[[多項式時間帰着|多項式時間多対一帰着]]や[[多項式時間帰着|多項式時間チューリング帰着]]を用いる。NP困難問題を解ける多項式時間の[[機械]]がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。

NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。[[NP]]は[[決定問題]]のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、[[探索問題]]([[:en:Search problem|en]])、[[最適化問題]]など様々な問題が属しうる。

上に挙げた定義から、問題 ''H'' がNP困難なとき次のことが言える（以下は定義ではなく主張）。

* すべてのNP完全問題は ''H'' に還元して多項式時間で解ける。またNPに属する全ての問題も ''H'' に還元できる。
* もし最適化問題 ''H'' の特殊例としてNP完全な決定問題 ''L'' を考えられるなら、''H'' はNP困難である。

NP困難な[[最適化問題]]は、最適解を求めるのが非常に困難であるため、[[近似アルゴリズム]]に関しても研究されている。

== P≠NP予想との関係 ==
もし、いずれかのNP困難な問題を[[多項式時間]]で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。ところが、P＝NPが成立しても「'''任意の'''NP困難な問題が多項式時間で解ける」とは言えない。この関係を右上の[[ベン図]]に示す。

== NP困難な問題の例 ==
*[[停止問題]] - NP困難だがNPではない決定問題。NP困難であることは、例えば[[充足可能性問題]]を停止問題に容易に還元できることから言える（充足できる解を見付けたら停止し、そうでない場合は無限ループするような[[チューリングマシン]]の停止問題を考えればよい）。NPでないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることによる。ただし、NP困難でありかつNP完全でない問題の全てが決定不可能というわけではない。例えば[[TQBF問題]]([[:en:True quantified Boolean formula|en]])は[[PSPACE]]で決定可能だが、多分NPではない。
*[[巡回セールスマン問題]] - 最適化問題。
*[[ハミルトン閉路問題]] - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。 
*[[ナップサック問題]] - 最適化問題。
*[[部分和問題]] - ナップサック問題の特殊ケース。NP困難かつNP完全な決定問題。
*[[最小頂点被覆問題]]
*[[最大独立集合問題]]
*[[最大クリーク問題]]
*[[分数和計画問題]]

== NP関連クラスの命名規約 ==
NPに関連するクラスの名称はまぎらわしい。「NP困難」はクラス名に「NP」と付くのに、全てが[[NP]]というわけではない。しかし現状では定着した名称なので、いまさら変わりそうにない。とはいえ、NPを中心に置いた上でそれなりに体系があるのも事実である。
;NP完全
:NPの'''中では'''「完全」な問題を意味する。つまりNPの'''中では'''最も解くのが難しい。　
;NP困難
:「少なくとも」NPと同等以上に難しい問題（ただし、NP'''に属する'''とは限らない）。
;NP-easy
:「たかだか」NPと同等以下しか難しくない問題（ただし、NP'''に属する'''とは限らない）。
;NP-equivalent
:NPと同等に難しい問題（ただし、NP'''に属する'''とは限らない）。

== 脚注 ==
<references/>

== 関連項目 ==
*[[NP完全問題]]
*[[多項式時間変換]] - 多対一還元やチューリング還元に計算時間の制限を付加したもの。
*[[チューリング還元]] - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Cook還元と呼ぶ。
*[[多対一還元]] - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Karp還元と呼ぶ。単に「多項式変換」と書けば通常 Karp還元を指す。

{{DEFAULTSORT:えぬひいこんなん}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事|NPえぬひいこんなん]]

[[he:NP (מחלקת סיבוכיות)#NP-קושי ובעיות NP-שלמות]]