NP困難

出典: フリー百科事典『ウィキペディア（Wikipedia）』

NP困難（-こんなん、NP-hard）とは計算複雑性理論における問題のクラスの1つ。非形式的に言えば「NPに属する最も難しい問題と比べて、少なくとも同等以上に難しい」問題である。問題 H がNP困難のクラスに属するとは、「NP完全問題に属する何れかの問題 L が H へ多項式時間チューリング還元可能である」と定義される。即ちであり、NP困難問題を解ける神託機械がもしあれば、それを利用してNP完全問題を多項式時間で解くことができる。
NP完全問題とは、NPの任意の問題から多項式時間多対一還元可能であり、かつ、NPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。PやNPは決定問題のクラスなので、NP完全もまた決定問題に限られるが、NP困難には決定問題、検索問題(en)、最適化問題など様々な問題が属しうる。

上に挙げた定義から次のことが言える（以下は定義ではなく主張）。

• 問題 H は少なくとも L と同等以上に難しい。何故なら H を用いて L を解けるからである。
• L はNP完全であり、NPの中では最も難しいので、問題 H は少なくともNPと同等以上に難しい。しかし H はNPに属している必要はなく、従って決定問題ではなくても良い。
• NP完全問題同士は互いに多項式時間多対一還元（別称：多項式変換とも）可能なので、すべてのNP完全問題は H に還元して多項式時間で解ける。従ってNPに属する全ての問題も H に還元できる。但しここでは二種類の変換を組み合わせていることに注意されたい。NP完全に属する決定問題をNP完全な問題 L に帰着する際は多項式変換であり、L を H に変換する際は多項式時間チューリング還元である。
• もし最適化問題 H の特殊例としてNP完全な決定問題 L を考えられるなら、H はNP困難である。
• もし H がたまたまNPに属すなら、H はNP完全。何故ならこの場合多項式時間チューリング還元が多項式変換の要件を満たすので。^[1]

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

目次 1 P≠NP予想との関係 2 NP困難な問題の例 3 別定義 4 NP関連クラスの命名規約について 5 関連項目 6 脚注

[編集] P≠NP予想との関係

もし何れかのNP困難な問題を多項式時間で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。同様に、何れかのNP完全な問題を多項式時間で解くアルゴリズムが存在した場合も、NPに属する全ての問題が多項式時間で解ける。そのため「何れかのNP困難（またはNP完全）な問題を多項式時間で解く方法が存在するか」という問題はそのまま P≠NP予想の否定の証明になる。ところが、P＝NPが成立しても「任意のNP困難な問題が多項式時間で解ける」とは言えない。これに対し、P≠NPが成り立つならば「如何なるNP困難な問題についても、これを多項式時間で解く一般的なアルゴリズムは存在しない」と言える。この関係を右上のベン図に示す。

[編集] NP困難な問題の例

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

[編集] 別定義

NP困難の別定義として、NP困難を決定問題に限定し、チューリング還元の替りに多項式時間多対一還元を用いるものがある。この場合、問題 L がNP困難であるための条件はである。ここでもし L が NP に属すなら、L はNP完全。

[編集] NP関連クラスの命名規約について

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

[編集] 関連項目

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

[編集] 脚注

1. ^ 注：英語版（版：18:14, 10 November 2008）ではこの一文は疑問があるとして削除されている。