Loading article…
計算複雑性理論において、NP完全問題とは、解を迅速に検証できる問題の中で最も難しい問題である。より正確には、問題がNP完全であるのは、以下の条件を満たす場合である。
最初の 3 つの基準を満たす問題は、 NPクラスに属します。NPは「非決定性多項式時間」の略です。この名前の「非決定性」とは、総当たり探索アルゴリズムの概念を数学的に形式化する方法である非決定性チューリング マシンを指します。多項式時間とは、決定性アルゴリズムが単一の解をチェックする、または非決定性チューリング マシンが探索全体を実行するのに「速い」と考えられる時間を指します。NP に属し、かつ 4 番目の基準も満たす問題は、「NP 完全」であると言われます。「完全」という用語は、同じ複雑性クラスのすべてをシミュレートできるという性質を指します。つまり、ある NP 完全問題に多項式時間アルゴリズムが存在する場合、NP に属するすべての問題に多項式時間アルゴリズムが存在するということです。
NP完全問題の集合は、しばしばNP-CまたはNPCと表記される。
NP完全問題の解は「迅速に」検証できるものの、解を迅速に見つける既知の方法は存在しない。つまり、現在知られているどのアルゴリズムを用いても、問題の規模が大きくなるにつれて、解決に必要な時間は急速に増加する。したがって、これらの問題を迅速に解決できるかどうかを判断すること、いわゆるP対NP問題は、今日のコンピュータ科学における根本的な未解決問題の一つとなっている。
NP完全問題の解を迅速に計算する方法はまだ発見されていないが、コンピュータ科学者やプログラマーは依然として頻繁にNP完全問題に遭遇する。NP完全問題は、ヒューリスティック手法や近似アルゴリズムを用いて解決されることが多い。
意思決定問題NP完全であるとは、以下の条件を満たす場合である。
候補解が であることを示すことで、 が NP に属することが証明できる。多項式時間で検証できる。
多項式時間で解ける決定問題はクラスPに属します。P に属する問題はすべて必然的に NP に属します。しかし、クラス NP が実際に P より大きいことは証明されていません。言い換えれば、NP に属する問題で P に属さないものが存在するかどうかはまだわかっていません。クラス P と NP が等しいかどうかという問題は、P 対 NP 問題として知られています。NP 完全性の定義の帰結として、UTMまたはその他のチューリング等価な抽象マシン上で多項式時間アルゴリズムがあれば、そうすれば、NPに属するすべての問題を多項式時間で解くことができるだろう。
NP に含まれるすべての問題を多項式時間で変換できる場合、その問題は NP に含まれていなくても、NPに含まれるすべての問題を変換できる場合、 NP困難であると言われます。 [ 4 ] NP に含まれる問題で、かつ NP 困難である場合、その問題は NP 完全であると言われます。したがって、NP 完全問題は、ある意味で NP の中で最も難しい問題です。
クック・レヴィンの定理は、ブール充足可能性問題がNP完全であることを述べており、このような問題が存在することを初めて証明しました。1972年、リチャード・カープは、他のいくつかの問題もNP完全であることを証明しました（カープの21のNP完全問題を参照）。したがって、ブール充足可能性問題以外にもNP完全問題のクラスが存在します。これらの最初の結果以来、以前にNP完全であることが示された他の問題からの還元によって、何千もの他の問題がNP完全であることが示されています。これらの問題の多くは、Garey & Johnson (1979)にまとめられています。
新しい問題がNP完全であることを証明する最も簡単な方法は、まずその問題がNPに属することを証明し、次に既知のNP完全問題をその問題に還元することです。したがって、さまざまなNP完全問題を知っておくことは有用です。以下のリストには、決定問題として表現した場合にNP完全となる、よく知られた問題がいくつか含まれています。
右側には、NP完全性を証明するために一般的に用いられる問題とその還元方法を示した図があります。この図では、問題は下から上へと還元されています。ただし、この図はこれらの問題間の数学的な関係性を説明するものとしては誤解を招く可能性があります。なぜなら、任意の2つのNP完全問題の間には多項式時間で還元できる関係が存在するからです。しかし、この図は、その多項式時間還元を実証するのが最も容易であった箇所を示しています。
P に属する問題と NP 完全問題の間には、多くの場合、わずかな違いしかありません。たとえば、ブール充足可能性問題の制限である3 充足可能性問題は NP 完全のままですが、少し制限された2 充足可能性問題は P に属します (具体的にはNL 完全です)。しかし、少し一般的な最大 2 充足問題は再び NP 完全です。グラフが 2 色で彩色できるかどうかを判定することは P に属しますが、3 色で彩色できるかどうかは、平面グラフに限定した場合でも NP 完全です。グラフがサイクルであるか二部グラフであるかを判定することは( Lに属して) 非常に簡単ですが、最大二部グラフまたは最大サイクル部分グラフを見つけることは NP 完全です。ナップサック問題の解は、最適解の任意の固定パーセンテージの範囲内で多項式時間で計算できますが、最適解を見つけることは NP 完全です。
興味深い例として、グラフ同型性問題があります。これは、2つのグラフ間にグラフ同型性が存在するかどうかを判定するグラフ理論の問題です。2つのグラフは、頂点の名前を変更するだけで一方を他方に変換できる場合に同型であると言えます。次の2つの問題を考えてみましょう。
部分グラフ同型問題はNP完全である。グラフ同型問題はNPに属するが、PにもNP完全にも属さないと疑われている。これは難しいと考えられているが、NP完全とは考えられていない問題の一例である。このクラスはNP中間問題と呼ばれ、P≠NPの場合に限り存在する。[ 5 ]
現在知られているNP完全問題に対するアルゴリズムはすべて、入力サイズに対して超多項式的な時間を必要とする。
以下の手法は、一般的に計算問題を解決するために適用でき、多くの場合、大幅に高速なアルゴリズムを生み出します。
上記のNP完全性の定義において、「還元」という用語は、多項式時間多対一還元の技術的な意味で使用されました。
もう一つのタイプの還元は、多項式時間チューリング還元である。多項式時間チューリング還元可能な問題サブルーチンが与えられた場合、多項式時間で、このサブルーチンを呼び出して解くプログラムを書くことができる。多項式時間で実行できます。これは、プログラムがサブルーチンを一度しか呼び出せず、サブルーチンの戻り値がプログラムの戻り値と一致する必要があるという制約がある多対一還元性とは対照的です。
多対一還元ではなくチューリング還元を用いてNP完全問題の類似物を定義する場合、結果として得られる問題の集合はNP完全問題よりも小さくなることはない。むしろ大きくなるかどうかは未解決の問題である。
NP完全性を定義するためによく用いられるもう1つのタイプの削減は、対数空間多対1削減です。これは、対数量の空間だけで計算できる多対1削減です。対数空間で実行できるすべての計算は多項式時間でも実行できるため、対数空間多対1削減が存在するならば、多項式時間多対1削減も存在することになります。このタイプの削減は、より一般的な多項式時間多対1削減よりも洗練されており、P完全などのより多くのクラスを区別することができます。これらのタイプの削減の下でNP完全性の定義が変わるかどうかは、まだ未解決の問題です。現在知られているすべてのNP完全問題は、対数空間削減の下でNP完全です。現在知られているすべてのNP完全問題は、次のようなはるかに弱い削減の下でもNP完全のままです。削減と削減。SAT などの NP 完全問題の中には、多対数時間射影の下でも完全であることが知られているものもあります。[ 6 ]ただし、AC 0削減は、多項式時間削減よりも厳密に小さいクラスを定義することが知られています。[ 7 ]
NP完全性の概念は1971年に導入されました（クック・レヴィンの定理を参照）。ただし、 NP完全という用語は後から導入されました。1971年のSTOC会議では、NP完全問題が決定性チューリングマシン上で多項式時間で解けるかどうかについて、コンピュータ科学者の間で激しい議論が交わされました。ジョン・ホプクロフトは、 NP完全問題が多項式時間で解けるかどうかという問題は、どちらの主張に対しても正式な証明がなかったため、後日解決すべきであるという点で、会議参加者全員の合意を得ました。
クレイ数学研究所は、 2000年にP対NP問題を7つのミレニアム懸賞問題の1つに指定した。 [ 8 ] [ 9 ]
ドナルド・クヌースによれば、「NP完全」という名称は、アルフレッド・アホ、ジョン・ホプクロフト、ジェフリー・ウルマンが著した有名な教科書「コンピュータアルゴリズムの設計と解析」で普及した。同氏によれば、理論計算機科学コミュニティを対象に行ったアンケートの結果に基づき、彼らは本の校正刷りの証明でこの名称を（「多項式完全」から）変更したという。[ 10 ]アンケートで提案された他の名称[ 11 ]には、「ヘラクレス級」、「恐るべき」、クックにちなんでスティグリッツが用いた「ハードボイルド」、そして「おそらく指数時間」を意味するシェン・リンの頭字語「PET」などがあったが、 P対NP問題がどちらの方向に進むかによって、「証明可能な指数時間」または「以前の指数時間」を意味する可能性もあった。 [ 12 ]
以下の誤解はよく見られます。[ 13 ]
決定問題をある固定された符号化の形式言語とみなすと、すべてのNP完全問題の集合NPCは、以下の制約の下で閉じられていない。
NPCが補文に関して閉じているかどうかは不明である。なぜなら、NPC= co-NPCとなるのはNP= co-NPの場合のみであり、NP=co-NPは未解決の問題だからである。[ 17 ]
NPとco-NPが等しいかどうかという問題は、おそらくP対NP問題に次いで、複雑性理論における2番目に重要な未解決問題である。
