NP（複雑さ）

コンピュータサイエンスにおける未解決の問題:

${\displaystyle {\mathsf {P\ {\overset {?}{=}}\ NP}}}$

(コンピュータサイエンスにおける未解決の問題)

計算複雑性理論において、NP（非決定性多項式時間）は、決定問題を分類するために使用される複雑性クラスである。NPとは、答えが「はい」である問題インスタンスが決定性チューリングマシンによって多項式時間で検証可能な証明を持つ決定問題の集合、または非決定性チューリングマシンによって多項式時間で解決できる問題の集合である。^{[2] [注 1]}

• NP は、非決定性チューリングマシンによって多項式時間で解決可能な決定問題の集合です。
• NP は、決定論的チューリングマシンによって多項式時間で検証可能な決定問題の集合です。

最初の定義は、略語 NP (「非決定論的、多項式時間」)の基礎となっています。チューリングマシンに基づくアルゴリズムは 2 つのフェーズで構成されており、最初のフェーズは非決定論的な方法で生成された解決策についての推測で構成され、2 番目のフェーズは推測が問題の解決策であるかどうかを検証する決定論的アルゴリズムで構成されているため、これら 2 つの定義は同等です。^[3]

複雑性クラスP (多項式時間で決定論的に解決可能なすべての問題) が NP (多項式時間で解決が検証可能な問題) に含まれていることは容易にわかります。なぜなら、問題が多項式時間で解決可能な場合、その問題を解くだけで、解決も多項式時間で検証可能だからです。 P はNP より小さい、つまり、多項式時間で解決できない決定問題が存在するが、その解決は多項式時間で確認できると広く信じられていますが、証明されていません。 NP で最も難しい問題はNP 完全問題と呼ばれます。このような問題を多項式時間で解くアルゴリズムは、他の任意の NP 問題も多項式時間で解くことができます。 P が実際に NP に等しい場合、NP 完全を解く多項式時間アルゴリズムが存在し、必然的にすべての NP 問題も解くことができます。^[4]

複雑性クラス NP は複雑性クラスco-NPと関連しており、その答え「いいえ」は多項式時間で検証できます。NP = co-NPであるかどうかは、複雑性理論におけるもう一つの未解決の問題です。^[5]

複雑性クラス NP は、 NTIMEに関して次のように定義できます。

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}),}$

ここで、非決定性チューリングマシンによって時間内に解決できる決定問題の集合です。 ${\displaystyle {\mathsf {NTIME}}(n^{k})}$${\displaystyle O(n^{k})}$

あるいは、NPは決定性チューリングマシンを検証器として定義することもできます。言語 LがNPに属するのは、多項式pとq、および決定性チューリングマシンMが存在し、

• すべてのxとyに対して、マシンM は入力⁠ ⁠に対して時間p (| x |) で実行されます。${\displaystyle (x,y)}$
• L内のすべてのxに対して、 ⁠ ⁠となる長さq (| x |)の文字列y が存在します。${\displaystyle M(x,y)=1}$
• Lに含まれないすべてのxと長さq (| x |)のすべての文字列yについて、⁠ ⁠。${\displaystyle M(x,y)=0}$

多くの検索問題や最適化問題 の決定バージョンなど、多くのコンピューター サイエンスの問題が NP に含まれています。

NP の検証者ベースの定義を説明するために、部分集合の合計問題を考えてみましょう。いくつかの整数{−7, −3, −2, 5, 8} が与えられており、これらの整数のいくつかの合計が 0 になるかどうかを知りたいとします。ここで、整数 {−3, −2, 5} は合計(−3) + (−2) + 5 = 0 に対応するため、答えは「はい」です。

いくつかの整数を足すとゼロになるかどうかを答えるには、すべての可能なサブセットを取得するアルゴリズムを作成します。アルゴリズムに入力する整数の数が増えると、サブセットの数と計算時間の両方が指数関数的に増加します。

ただし、特定のサブセットが与えられている場合は、サブセットの整数を合計することで、サブセットの合計がゼロかどうかを効率的に検証できることに注意してください。合計がゼロの場合、そのサブセットは、答えが「はい」であることの証明または証拠です。特定のサブセットの合計がゼロかどうかを検証するアルゴリズムは、検証器です。明らかに、サブセットの整数を合計することは多項式時間で実行できるため、サブセットの合計問題は NP に属します。

上記の例は、あらゆる決定問題に一般化できます。問題の任意のインスタンス Iと証人 W が与えられた場合、検証者Vが存在し、順序付きペア (I、W) が入​​力として与えられたときに、証人が答えが「はい」または「いいえ」であることを多項式時間で証明した場合は V が多項式時間で「はい」を返し、そうでない場合は多項式時間で「いいえ」を返す場合、NP になります。 ${\displaystyle \Pi }$${\displaystyle \Pi }$

この問題の「いいえ」回答バージョンは、「有限の整数集合が与えられた場合、すべての空でない部分集合の合計はゼロではないか」と述べられています。検証子ベースの NP 定義では、 「いいえ」回答に対する効率的な検証子は必要ありません。「いいえ」回答に対するこのような検証子を持つ問題のクラスは、co-NP と呼ばれます。実際、NP のすべての問題に「いいえ」回答に対する検証子もあり、したがって co-NP であるかどうかは未解決の問題です。

いくつかの文献では、検証者は「認証者」、証人は「証明書」と呼ばれています。^[2]

検証者ベースの定義と同等なのは、次の特徴付けです。NP は、多項式時間で実行される非決定性チューリングマシンによって解決可能な決定問題のクラスです。つまり、 が、存在的受諾条件を持つ何らかの多項式時間非決定性チューリングマシンによって認識される場合はいつでも、決定問題は NP に属します。存在的受諾条件 とは、 の何らかの計算パスが受諾状態につながる場合のみです。この定義は、非決定性チューリングマシンが証明書を非決定的に選択し、その証明書に対して検証者を実行することで、NP 問題を多項式時間で解決できるため、検証者ベースの定義と同等です。同様に、そのようなマシンが存在する場合、多項式時間検証者を自然に構築できます。 ${\displaystyle \Pi }$${\displaystyle \Pi }$${\displaystyle M}$${\displaystyle w\in \Pi }$${\displaystyle M(w)}$

この観点から、co-NP を、存在拒絶条件を持つ多項式時間非決定性チューリングマシンによって認識可能な決定問題のクラスとして双対的に定義できます。存在拒絶条件は普遍的受容条件とまったく同じものであるため、 NP 対 co-NP の問題は、存在条件と普遍的受容条件が多項式時間非決定性チューリングマシンのクラスに対して同じ表現力を持つかどうかを尋ねるものと 理解できます。

NP は、和集合、積集合、連結集合、クリーネの星、反転集合の下で閉じています。NP が補集合の下で閉じているかどうかはわかっていません(この問題は、いわゆる「NP 対 co-NP」の問題です)。

このクラスには重要な問題が多数あるため、NP の問題に対する多項式時間アルゴリズムを見つけるための多大な努力がなされてきました。しかし、NP にはそのような試みが通用せず、超多項式時間を必要とすると思われる問題が多数残っています。これらの問題が多項式時間で決定可能かどうかは、コンピュータ サイエンスにおける最大の未解決問題の 1 つです(詳細な議論については、 P対 NP (「P = NP」) 問題を参照してください)。

この文脈で重要な概念は、NP のサブセットであり、NP の「最も難しい」問題と非公式に説明できるNP 完全決定問題のセットです。そのうちの1 つでも多項式時間アルゴリズムが存在する場合、NP のすべての問題に多項式時間アルゴリズムが存在します。このため、また熱心な研究によって NP 完全問題に対する多項式アルゴリズムが見つからなかったため、問題が NP 完全であることが証明されると、この問題に対する多項式アルゴリズムが存在する可能性は低いという兆候として広く認識されています。

しかし、実際の使用では、最適なソリューションを探すために計算リソースを費やす代わりに、十分な（ただし、潜在的に最適ではない）ソリューションが多項式時間で見つかることがよくあります。また、一部の問題の実際の適用は、理論上の同等のものよりも簡単です。

NP の 2 つの定義は、非決定性チューリング マシン(TM)によって多項式時間で解決可能な問題のクラスと、決定性チューリング マシンによって多項式時間で検証可能な問題のクラスであり、これらは同等です。証明は、たとえば Sipser の『Introduction to the Theory of Computation』のセクション 7.3 など、 多くの教科書で説明されています。

これを示すために、まず、決定論的な検証器があると仮定します。非決定論的なマシンは、すべての可能な証明文字列に対して検証器を非決定論的に実行するだけです (各ステップで証明文字列の次の文字を非決定論的に選択でき、証明文字列の長さは多項式で制限される必要があるため、これには多項式の数のステップしか必要ありません)。いずれかの証明が有効であれば、いずれかのパスが受け入れます。有効な証明がない場合、文字列は言語に含まれていないため拒否されます。

逆に、特定の言語 L を受け入れる A という非決定論的な TM があるとします。多項式的に多数のステップのそれぞれで、マシンの計算ツリーは最大で有限数の方向に分岐します。少なくとも 1 つの受け入れパスが存在する必要があり、このパスを記述する文字列が検証者に提供される証明です。検証者は、受け入れパスのみをたどり、最後に受け入れることを検証することで、A を決定論的にシミュレートできます。A が入力を拒否した場合、受け入れパスは存在せず、検証者は常に拒否します。

NP はP内のすべての問題を含みます。なぜなら、証明を無視してそれを解くだけで、問題のあらゆるインスタンスを検証できるからです。 NP はPSPACEに含まれます。これを示すには、すべての証明文字列をループし、それぞれを多項式時間検証器に渡す PSPACE マシンを構築すれば十分です。多項式時間マシンは多項式数のビットしか読み取れないため、多項式空間以上を使用することはできず、多項式空間以上を占める証明文字列を読み取ることもできません (したがって、これより長い証明を考慮する必要はありません)。 NP はEXPTIMEにも含まれており、同じアルゴリズムが指数時間で動作するからです。

co-NP には、例がなくとも簡単に証明できる問題(反例と呼ばれることもある) が含まれます。たとえば、素数判定はco-NP に自明に含まれます。これは、非自明な因数を与えるだけで整数の素数を反証できるためです。NP と co-NP は一緒に多項式階層の最初のレベルを形成し、これは P より上になります。

NPは決定論的マシンのみを使用して定義されます。検証者が確率的であることを許可すると（ただし、これは必ずしもBPPマシンである必要はありません^[6] ）、アーサーからマーリンへの通信なしで アーサー-マーリンプロトコルを使用してクラスMAを解くことができます。

BPPとNPの関係は不明である。BPPがNPのサブセットなのか、NPがBPPのサブセットなのか、あるいはどちらでもないのかは不明である。NPがBPPに含まれる場合（NP完全問題の実用的な解を意味するため、ありそうにないと考えられる）、NP = RPかつPH ⊆ BPPとなる。^[7]

NP は決定問題の一種であり、類似した関数問題の一種はFNPです。

唯一知られている厳密な包含関係は、時間階層定理と空間階層定理から来ており、それぞれとです。 ${\displaystyle {\mathsf {NP\subsetneq NEXPTIME}}}$${\displaystyle {\mathsf {NP\subsetneq EXPSPACE}}}$

記述的複雑性理論の観点から見ると、NP は存在二階述語論理(フェイギンの定理)によって定義可能な言語の集合に正確に対応します。

NP は、証明者が証明証明書を作成し、検証者がそれをチェックする決定論的多項式時間マシンである、非常に単純なタイプの対話型証明システムと見なすことができます。正しい証明文字列があればそれが受け入れられるため完全であり、受け入れ可能な証明文字列がない場合には検証者が受け入れることができないため健全です。

複雑性理論の主な結果は、NP は確率的にチェック可能な証明によって解決可能な問題として特徴付けられ、検証者は O(log n ) のランダム ビットを使用し、証明文字列の定数ビットのみを検査する (クラスPCP (log n , 1)) という点です。より非公式に言えば、これは、上記の NP 検証者が証明文字列内のいくつかの場所を「抜き打ちチェック」する検証者に置き換えられ、限られた数のコイン投げを使用して高い確率で正しい答えを決定できることを意味します。これにより、近似アルゴリズムの難しさに関するいくつかの結果が証明されます。

P内のすべての問題はと表記されます。 Pの問題に対する証明書が与えられている場合は、証明書を無視して問題を多項式時間で解くことができます。 ${\displaystyle {\mathsf {P\subseteq NP}}}$

整数因数分解問題の決定問題版：整数nとkが与えられたとき、 1 < f < kでnを割り切れる因数fが存在するか？^[8]

すべてのNP 完全問題は NP です。

ブール充足可能性問題（SAT ）。ブール変数を含む命題論理の特定の式が、変数のある値に対して真であるかどうかを知りたい場合。 ^[9]

巡回セールスマン問題の決定バージョンは NP です。n 都市間の距離の入力行列が与えられた場合、合計距離がk未満ですべての都市を訪問するルートが存在するかどうかを判断することが問題となります。

証明は、単に都市のリストにすることができます。そうすれば、検証は明らかに多項式時間で実行できます。都市間のパスに対応する行列のエントリを追加するだけです。

非決定性チューリングマシンは次のようなルートを見つけることができます。

• 訪問する各都市で、すべての頂点を訪問するまで、次に訪問する都市を「推測」します。行き詰まった場合は、すぐに停止します。
• 最後に、実行した経路のコストがO ( n ) 時間でk未満であったことを確認します。

それぞれの推測は、チューリング マシンの新しいコピーを「フォーク」して、それぞれの可能なパスをたどっていくものと考えることができます。そして、少なくとも 1 台のマシンがk未満の距離のルートを見つけた場合、そのマシンは入力を受け入れます。(同様に、これは常に正しく推測する単一のチューリング マシンと考えることができます)

可能な距離の範囲でのバイナリ検索は、巡回セールスマンの決定バージョンを繰り返し（多項式回数）呼び出すことで、決定バージョンを最適化バージョンに変換することができます。^{[10] [8]}

グラフGにグラフHと同型なサブグラフが含まれているかどうかを判定するサブグラフ同型問題。[ ^11]

• チューリングマシン – 抽象マシンを定義する計算モデル

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第2版。MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7。セクション34.2 :多項式時間検証、pp. 979–983。 
• マイケル・シプサー（1997年）。計算理論入門。PWS出版。ISBN 0-534-94728-X。セクション7.3～7.5（NPクラス、NP完全性、追加のNP完全問題）、241～271ページ。
• David Harel、Yishai Feldman。『アルゴリズム：コンピューティングの精神』、Addison-Wesley、マサチューセッツ州レディング、第 3 版、2004 年。

• 複雑動物園：NP
• 伝統的および最近の複雑性理論研究に関するAmerican Scientist入門書: 「偶然のアルゴリズム」