「NP困難」の版間の差分

'''NP困難'''（-こんなん、NP-hard）とは[[計算複雑性理論]]における問題のクラスの1つ。非形式的に言えば「[[NP]]に属する最も難しい問題と比べて、少なくとも同等以上に難しい」問題である。問題 ''H'' がNP困難のクラスに属するとは、「[[NP完全問題]]に属する何いずれかの問題 ''L'' が ''H'' へ[[多項式時間変換|多項式時間チューリング還元]]可能である」と定義される。即ち<math>\scriptstyle L\, \leq\,_T H</math>であり、NP困難問題を解ける[[神託機械]]がもしあれば、それを利用してNP完全問題を多項式時間で解くことができる。<br />

* 問題 ''H'' は少なくとも L と同等以上に難しい。何故なぜなら H を用いて ''L'' を解けるからである。

* ''L'' はNP完全であり、NPの中では最も難しいので、問題 ''H'' は少なくともNPと同等以上に難しい。しかし ''H'' はNPに属している必要はなく、従したがって[[決定問題]]ではなくても良い。

* NP完全問題同士は互いに多項式時間[[多対一還元]]（別称：多項式変換とも）可能なので、すべてのNP完全問題は ''H'' に還元して多項式時間で解ける。従したがってNPに属する全ての問題も ''H'' に還元できる。但ただし、ここでは二種類の変換を組み合わせていることに注意されたいが必要。NP完全に属する決定問題をNP完全な問題 ''L'' に帰着する際は多項式変換であり、''L'' を ''H'' に変換する際は多項式時間[[チューリング還元]]である。

* もし ''H'' がたまたまNPに属すなら、''H'' はNP完全。何故なぜならこの場合多項式時間チューリング還元が多項式変換の要件を満たすので。<ref>注：英語版（版：18:14, 10 November 2008）ではこの一文は疑問があるとして削除されている。</ref>

もし何、いずれかのNP困難な問題を[[多項式時間]]で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。同様に、何いずれかのNP完全な問題を多項式時間で解くアルゴリズムが存在した場合も、NPに属する全ての問題が多項式時間で解ける。そのため「'''何いずれかの'''NP困難（またはNP完全）な問題を多項式時間で解く方法が存在するか」という問題はそのまま [[P≠NP予想]]の否定の証明になる。ところが、P＝NPが成立しても「'''任意の'''NP困難な問題が多項式時間で解ける」とは言えない。これに対し、P≠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-easy''' — 「たかだか」NPと同等以下しか難しくない問題（但ただし、NP'''に属する'''とは限らない）。

'''NP-equivalent''' — NPと同等に難しい問題（但ただし、NP'''に属する'''とは限らない）。

*[[チューリング還元]] - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Cook還元と呼ぶ。

*[[多対一還元]] - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Karp還元と呼ぶ。単に「多項式変換」と書けば通常 Karp還元を指す。