NP困難

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
PNPNP完全NP困難の相関を表すベン図

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

NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NP決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(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完全
NPの中では「完全」な問題を意味する。つまりNPの中では最も解くのが難しい。 
NP困難
「少なくとも」NPと同等以上に難しい問題(ただし、NPに属するとは限らない)。
NP-easy
「たかだか」NPと同等以下しか難しくない問題(ただし、NPに属するとは限らない)。
NP-equivalent
NPと同等に難しい問題(ただし、NPに属するとは限らない)。

脚注[編集]


関連項目[編集]

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