NP困難

NP困難とは

計算量理論において、NP困難（NP-hard） とは、問題の難しさを示す概念の一つです。ある問題がNP困難であるとは、「NP（非決定性多項式時間）に属する任意の問題と比較して、少なくとも同等以上に難しい」ということを意味します。

NP困難の定義

より正確には、問題HがNP困難であるとは、NPに属する任意の問題Lが、問題Hに「帰着可能」であると定義されます。この「帰着」の定義には、多項式時間多対一帰着や多項式時間チューリング帰着などが用いられ、どの帰着を用いるかによって定義が微妙に異なります。

もし、あるNP困難問題を多項式時間で解くことができる機械が存在すれば、それを利用することで、NPに属する任意の問題を多項式時間で解けることになります。これは、NP困難な問題が、NPに属する全ての問題を内包する、または同等以上に難しいことを示唆しています。

NP完全問題との違い

NP完全問題は、NP困難であり、かつNPに属する問題です。NP困難な問題は必ずしもNPに属するとは限りません。NPは決定問題のクラスなので、NP完全問題も決定問題に限られます。しかし、NP困難には、決定問題だけでなく、探索問題や組合せ最適化問題など、様々な種類の問題が含まれます。

NP困難な問題の特徴

NP困難な問題Hには、以下の特徴があると言えます。

すべての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困難: 少なくともNPと同等以上に難しい問題（NPに属するとは限らない）を指します。
NP-easy: たかだかNPと同等以下しか難しくない問題（NPに属するとは限らない）を指します。
NP-equivalent: NPと同等に難しい問題（NPに属するとは限らない）を指します。

これらの名称は、歴史的な経緯から定着しており、今後変更される可能性は低いと考えられます。

関連用語

P≠NP予想: 計算量理論における未解決問題の一つ。
NP完全問題: NP困難であり、かつNPに属する問題。
多項式時間変換: 多対一還元やチューリング還元に計算時間の制限を付加したもの。
チューリング還元: 計算時間を多項式時間に制限した場合は、多項式時間チューリング還元、またはCook還元と呼ばれる。
多対一還元: 計算時間を多項式時間に制限した場合は、多項式時間多対一還元、またはKarp還元と呼ばれる。単に「多項式変換」と書けば、通常はKarp還元を指す。

まとめ

NP困難な問題は、計算機科学における重要な研究対象であり、実社会でも様々な応用があります。これらの問題の効率的な解法を開発することは、計算機科学の発展に不可欠であり、今も多くの研究者が取り組んでいます。

もう一度検索