P対NP問題

P対 NP 問題は、理論計算機科学における未解決の主要問題です。非公式には、解決がすぐに検証できるすべての問題は、すぐに解決できるかどうかを問うものです。

ここで「迅速に」とは、タスクを解決し、多項式時間（たとえば指数時間ではなく）で実行するアルゴリズムが存在することを意味します。つまり、タスク完了時間は、アルゴリズムへの入力のサイズに対する多項式関数によって上限が設定されます。何らかのアルゴリズムが多項式時間で回答できる一般的な質問のクラスは、 「 P 」または「クラス P 」です。一部の質問では、回答を迅速に見つける方法が知られていませんが、回答が提供されていれば、迅速に検証できます。回答が多項式時間で検証できる質問のクラスは「 NP 」であり、「非決定性多項式時間」を表します。^{[注 1]}

P 対 NP の質問に対する答えは、多項式時間で検証できる問題が多項式時間で解決できるかどうかを決定します。広く信じられているように、P ≠ NP の場合、NP には検証するよりも計算する方が難しい問題があることを意味します。つまり、それらの問題は多項式時間で解決できませんが、答えは多項式時間で検証できます。

この問題は、コンピュータサイエンスにおける最も重要な未解決問題と呼ばれています。^[1]計算理論における重要な問題であることに加えて、いずれの証明も、数学、暗号、アルゴリズム研究、人工知能、ゲーム理論、マルチメディア処理、哲学、経済学、その他多くの分野に深い影響を与えるでしょう。^[2]

これはクレイ数学研究所が選定した7つのミレニアム懸賞問題のうちの1つであり、それぞれの問題で最初の正解者に100万ドルの賞金が贈られます。

次のはい/いいえの問題を考えてみましょう。サイズ の不完全な数独グリッドが与えられたとき、すべての行、列、およびマス目に 1 から までの整数が含まれる有効な解が少なくとも 1 つありますか。この一般化された数独の問題の「はい」の例を、候補の解が与えられれば簡単に検証できます。ただし、この問題のすべての例に対して「はい」または「いいえ」を正しく答えることができる多項式時間アルゴリズムがあるかどうかはわかっていません。したがって、一般化された数独は NP (すばやく検証可能) に属しますが、P (すばやく解決可能) に属する場合と属さない場合があります。(固定サイズの数独には有限数のグリッドしかないため、数独の一般化バージョンを検討する必要があります。この場合、答えはテーブル検索で見つけることができるため、問題は P に属します。) ${\displaystyle n^{2}\times n^{2}}$${\displaystyle n\times n}$${\displaystyle n^{2}}$

P対NP問題の正確な記述は、1971年にスティーブン・クックの重要な論文「定理証明手順の複雑さ」^[3]で導入されました（また、1973年にレオニード・レビンによって独立して^[4]）。

P対NP問題は1971年に正式に定義されたが、それ以前にも、関連する問題、証明の難しさ、および潜在的な結果についての兆候はあった。1955年、数学者のジョン・ナッシュはNSAに手紙を書き、十分に複雑なコードを解読するには、鍵の長さの指数関数的な時間が必要になるだろうと推測した。 ^[5]もしそれが証明されれば（そしてナッシュは当然懐疑的だったが）、これは現在P≠NPと呼ばれていることを意味する。なぜなら、提案された鍵は多項式時間で検証できるからである。根本的な問題に関するもう一つの言及は、1956年にクルト・ゲーデルがジョン・フォン・ノイマンに書いた手紙の中にあった。ゲーデルは、定理証明（現在では共NP完全であることが知られている）が2次時間または線形時間で解決できるかどうかを尋ね、^[6]そして、もしそうなら、数学的証明の発見を自動化できるという最も重要な結果の1つを指摘した。

計算複雑性クラスP と NPの関係は、計算複雑性理論で研究されています。計算複雑性理論は、与えられた問題を解決するために計算中に必要なリソースを扱う計算理論の一部です。最も一般的なリソースは、時間 (問題を解決するのに必要なステップ数) と空間 (問題を解決するのに必要なメモリ量) です。

このような分析では、時間を分析する必要があるコンピュータのモデルが必要です。通常、このようなモデルでは、コンピュータが決定論的(コンピュータの現在の状態と入力が与えられた場合、コンピュータが実行できるアクションは 1 つだけ) かつ順次的(アクションを次々に実行する) であると想定されます。

この理論では、クラス P は、入力のサイズの多項式期間で決定性シーケンシャルマシン上で解決可能なすべての決定問題(以下に定義) で構成されます。クラスNP は、正しい情報が与えられれば正の解が多項式時間で検証可能なすべての決定問題、または同等に、非決定性マシン上で多項式時間で解を見つけることができるすべての決定問題で構成されます。^{[7]明らかに、P ⊆ NP です。}理論計算機科学における最大の未解決問題は、おそらく、これら 2 つのクラスの関係に関するものです。

PはNPと等しいですか?

2002年以来、ウィリアム・ガサーチは、この疑問や関連する疑問について研究者を対象に3回の世論調査を実施している。^{[8] [9] [10]} P≠NPへの信頼は高まっており、2012年には83%、2002年には61%だったのに対し、2019年には88%がP≠NPを信じていた。専門家に限定すると、2019年の回答では99%がP≠NPを信じているという結果になった。^[10]これらの世論調査はP = NPかどうかを示唆するものではなく、ガサーチ自身は「これによってP=?NPの解明や、いつ解明されるかの判断に近づくことはないが、この時代における主観的な意見に関する客観的な報告となることを目指している」と述べた。

P = NP 問題に取り組むには、NP 完全性の概念が非常に役立ちます。NP 完全問題とは、他の任意の NP 問題が多項式時間で還元可能であり、その解決が多項式時間で検証可能な問題です。つまり、任意の NP 問題は任意の NP 完全問題に変換できます。非公式には、NP 完全問題とは、少なくとも NP の他のどの問題と同じくらい「難しい」 NP 問題です。

NP 困難問題とは、少なくとも NP 問題と同じくらい難しい問題です。つまり、すべての NP 問題は (多項式時間で) NP 困難問題に還元できます。NP 困難問題は NP である必要はありません。つまり、多項式時間で検証可能な解を持つ必要はありません。

たとえば、ブール充足可能性問題は、クック・レビンの定理により NP 完全であるため、 NP のあらゆる問題のインスタンスは、多項式時間で機械的にブール充足可能性問題に変換できます。ブール充足可能性問題は、多くの NP 完全問題の 1 つです。NP 完全問題が P に含まれる場合、P = NP になります。ただし、多くの重要な問題は NP 完全であり、それらのいずれに対する高速アルゴリズムも知られていません。

定義だけから見ると、NP完全問題が存在することは直感的ではありません。しかし、自明なNP完全問題は次のように定式化できます。多項式時間で停止することが保証されているチューリングマシン Mが与えられた場合、 Mが受け入れる多項式サイズの入力は存在するでしょうか? ^[11]これはNPです。なぜなら、(入力が与えられた場合) M をシミュレートすることで、 M が入力を受け入れるかどうかを簡単に確認できるからです。これはNP完全です。なぜなら、NPの問題の特定のインスタンスの検証器は、検証するソリューションを入力として受け取る多項式時間マシンMとしてエンコードできるからです。次に、インスタンスが「はい」インスタンスであるか「いいえ」インスタンスであるかという質問は、有効な入力が存在するかどうかによって決定されます。

NP完全であることが証明された最初の自然な問題は、ブール充足可能性問題（SATとも呼ばれる）でした。上で述べたように、これはクック・レビンの定理です。充足可能性がNP完全であるというその証明には、NPの定義に関連するチューリングマシンの技術的な詳細が含まれています。しかし、この問題がNP完全であることが証明された後、還元による証明により、前述のゲーム数独を含む他の多くの問題もNP完全であることを示すより簡単な方法が提供されました。この場合、証明は、多項式時間での数独の解法を使用して、ラテン方陣を多項式時間で完成させることもできることを示しています。^[12]これは、3部グラフを三角形に分割する問題の解を与え、^[13]これは、SATの特殊なケースである3-SATの解を見つけるために使用でき、^[14]それは、一般的なブール充足可能性の解を提供します。したがって、数独の多項式時間解は、一連の機械的変換によって、満足可能性の多項式時間解につながり、今度は、他のあらゆる NP 問題を多項式時間で解くために使用できます。このような変換を使用すると、一見無関係に見える膨大な種類の問題がすべて互いに還元可能になり、ある意味で「同じ問題」になります。

P = NP かどうかは不明ですが、P の範囲外の問題は知られています。クラス P が多項式実行時間で定義されるのと同様に、クラスEXPTIMEは指数実行時間を持つすべての決定問題の集合です。言い換えると、EXPTIME 内の任意の問題は、決定論的チューリングマシンによってO (2 ^{p ( n )} ) 時間で解くことができます。ここで、 p ( n ) はnの多項式関数です。決定問題は、EXPTIME 内にある場合EXPTIME 完全であり、EXPTIME 内のすべての問題には多項式時間の多対一縮約があります。多くの問題は EXPTIME 完全であることが知られています。P ≠ EXPTIME であることが示されるため、これらの問題は P の範囲外であり、多項式時間以上を必要とします。実際、時間階層定理により、指数時間よりも大幅に短い時間で解くことはできません。例としては、 N × Nボード上のチェスの位置に対する完全な戦略を見つけること^[15]や、他のボードゲームの同様の問題などがあります。 ^[16]

プレスブルガー算術における文の真偽を決定する問題は、さらに多くの時間を必要とする。フィッシャーとラビンは1974年に^{[17] 、長さ}nのプレスブルガー文の真偽を決定するすべてのアルゴリズムは、ある定数cに対して少なくとも実行時間を持つことを証明した。したがって、この問題は指数関数的実行時間よりも長い時間を必要とすることが知られている。さらに難しいのは、停止問題などの決定不能問題である。これらの問題は、特定のアルゴリズムでは少なくとも 1 つの入力に対してそのアルゴリズムが正しい答えを生成しないという意味で、どのアルゴリズムでも完全に解くことはできない。つまり、間違った答えを生成するか、決定的な答えを与えずに終了するか、あるいはまったく答えを生成せずに永遠に実行されるかのいずれかである。 ${\displaystyle 2^{2^{cn}}}$

決定問題以外の問題を考えることも可能である。そのようなクラスの 1 つに、計数問題があり、#Pと呼ばれるものがある。NP 問題が「解は存在するか?」を問うのに対し、対応する #P 問題は「解はいくつあるか?」を問う。明らかに、#P 問題は対応する NP 問題と少なくとも同じくらい難しいに違いない。なぜなら、解の数をカウントすると、その数が 0 より大きい場合、少なくとも 1 つの解が存在するかどうかが直ちにわかるからである。驚くべきことに、難しいと考えられている一部の #P 問題は、簡単な (たとえば線形時間) P 問題に対応する。^[18]これらの問題では、解が存在するかどうかは非常に簡単にわかるが、いくつ存在するかは非常に難しいと考えられている。これらの問題の多くは#P 完全であり、したがって #P で最も難しい問題の 1 つである。なぜなら、これらの問題のいずれかに対する多項式時間解は、他のすべての #P 問題に対する多項式時間解を可能にするからである。

1975年、リチャード・E・ラドナーは、 P ≠ NPの場合、NPにはPにもNP完全でもない問題が存在することを示した。^[19]このような問題はNP中間問題と呼ばれる。グラフ同型性問題、離散対数問題、整数因数分解問題は、 NP中間であると考えられている問題の例である。これらは、Pに含まれず、NP完全ではないことが知られている非常に少数のNP問題の一部である。

グラフ同型性問題は、2 つの有限グラフが同型であるかどうかを判断する計算問題です。計算量理論における重要な未解決問題は、グラフ同型性問題が P か、NP 完全か、NP 中間かという問題です。答えはわかっていませんが、この問題は少なくとも NP 完全ではないと考えられています。^[20]グラフ同型性が NP 完全である場合、多項式時間階層は2 番目のレベルに縮小します。^{[21]多項式階層は有限レベルに縮小しないと広く信じられているため、グラフ同型性は NP 完全ではないと考えられています。この問題の最良のアルゴリズムは、} László Babaiによるもので、準多項式時間で実行されます。^[22]

整数因数分解問題は、与えられた整数の素因数分解を決定する計算問題である。決定問題として表現すると、入力がk未満の因数を持つかどうかを判断する問題である。効率的な整数因数分解アルゴリズムは知られておらず、この事実はRSAアルゴリズムなどのいくつかの現代の暗号システムの基礎となっている。整数因数分解問題は NP とco-NP（さらにはUPと co-UP ^[23]）に存在する。問題が NP 完全である場合、多項式時間階層は最初のレベル（つまり、NP = co-NP）に崩壊する。整数因数分解の最も効率的な既知のアルゴリズムは、一般数体ふるいであり、期待時間は

${\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}$

nビットの整数を因数分解する。この問題に対する最もよく知られている量子アルゴリズムであるショアのアルゴリズムは多項式時間で実行されるが、これは非量子計算量クラスに関して問題がどこにあるのかを示すものではない。

上記の議論では、P は「簡単」を意味し、「P に含まれない」は「難しい」を意味すると仮定しており、これはコブハムのテーゼとして知られています。これは複雑性理論で一般的な仮定ですが、注意点があります。

まず、これは実際には誤りである可能性がある。理論上の多項式アルゴリズムは、非常に大きな定数因子または指数を持つ場合があり、非実用的になる。たとえば、グラフGにHがマイナーとして含まれているかどうかを判断する問題は、Hが固定されている場合、実行時間O ( n ² )で解決できる。 ^[25]ここで、n はGの頂点の数である。しかし、大きな O 表記法は、 Hに超指数的に依存する定数を隠している。定数は よりも大きく(クヌースの上矢印表記法を使用)、hはHの頂点の数である。^[26]${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$

一方、問題がNP完全であることが示され、P ≠ NPであっても、実際には問題に対する有効なアプローチが存在する可能性がある。ナップザック問題、巡回セールスマン問題、ブール充足可能性問題など、多くのNP完全問題には、多くの現実世界のインスタンスを妥当な時間で最適に解くことができるアルゴリズムがある。このようなアルゴリズムの実験的な平均ケースの複雑度（時間対問題サイズ）は驚くほど低い可能性がある。一例として、線形計画法の単体アルゴリズムが挙げられ、これは実際には驚くほどうまく機能する。最悪のケースの時間複雑度は指数関数的であるにもかかわらず、最もよく知られている多項式時間アルゴリズムと同等に動作する。^[27]

最後に、量子計算やランダム化アルゴリズムなど、P と NP が定義されているチューリングマシンモデルに準拠しない計算の種類があります。

クックは『P対NP問題』の中で、この問題を「P = NPか?」と言い換えている。 ^{[28]世論調査によると、 [8] [29]}ほとんどのコンピュータ科学者はP ≠ NPであると考えている。この考えの主な理由は、何十年にもわたるこれらの問題の研究にもかかわらず、3,000を超える重要なNP完全問題（NP完全問題の一覧を参照）のいずれに対しても、多項式時間アルゴリズムを誰も見つけられていないことである。これらのアルゴリズムは、NP完全性の概念が定義されるずっと前から求められていた（最初に見つかった問題のうちのカープの21のNP完全問題はすべて、NP完全であることが示された時点ではよく知られた既存の問題であった）。さらに、結果P = NPは、NP = co-NPやP =  PHなど、現在誤りであると考えられている他の多くの驚くべき結果を暗示している 。

また、解決が難しいが、その解決策の検証が容易な問題の存在は、現実世界の経験と一致すると直感的に主張されている。^[30]

P = NP であれば、世界は私たちが通常想定しているものとは大きく異なる場所になります。「創造的な飛躍」に特別な価値はなく、問題を解決することと、解決策が見つかった後にそれを認識するという間に根本的なギャップはありません。

— スコット・アーロンソン、ユタ州オースティン

一方、P≠NPを信じるのは自信過剰であり、研究者はP=NPの証明も探求すべきだと考える研究者もいる。例えば、2002年には次のような発言があった。^[8]

P ≠ NP を支持する主な議論は、網羅的探索の分野における根本的な進歩がまったくないことです。これは、私の意見では、非常に弱い議論です。アルゴリズムの領域は非常に広く、私たちはその探究の始まりに過ぎません。[...]フェルマーの最終定理の解決は、非常に単純な質問が非常に深い理論によってのみ解決される可能性があることを示しています。

— モーシェ Y. ヴァルディ、ライス大学

憶測に執着することは、研究計画を立てる上で良い指針にはなりません。常にあらゆる問題の両方向を試してみるべきです。有名な数学者たちは、必要な方法をすべて開発していたにもかかわらず、偏見のせいで、予想とは反対の解決法を持つ有名な問題を解決できなかったことがあります。

— アニル・ネロード、コーネル大学

PとNPの定義で「多項式時間」を「マルチテープチューリングマシン上の線形時間」に置き換えると、DLINとNLINのクラスが得られます。DLIN≠NLINであることが知られています^[31]。

この問題がこれほど注目を集める理由の 1 つは、考えられる答えの結果です。どちらの方向の解決でも、理論は大きく前進し、おそらく実用面でも大きな結果をもたらすでしょう。

P = NP の証明は、NP の重要な問題のいくつかを解決するための効率的な方法につながる場合、驚くべき実用的な結果をもたらす可能性があります。さまざまな NP 完全問題が多くの分野で基本的な問題であるため、肯定的および否定的な両方の潜在的な結果が生じます。

また、証明が NP 完全問題に対する実用的なアルゴリズムにつながらない可能性も十分にあります。問題の定式化では、境界多項式が小さいことや、具体的にわかっていることさえ必要ありません。非構成的証明では、解を得るためのアルゴリズムや特定の境界を指定せずに、解が存在することを示すことができます。証明が構成的で、明示的な境界多項式とアルゴリズムの詳細を示していても、多項式の次数がそれほど低くなければ、アルゴリズムは実際には十分に効率的ではない可能性があります。この場合、最初の証明は主に理論家の関心を引くものになりますが、多項式時間による解が可能であるという知識は、それを達成するためのより優れた (そしておそらく実用的な) 方法の研究に確実に拍車をかけるでしょう。

P = NP を示す解は、特定の問題が困難であることを前提とする暗号学の分野をひっくり返す可能性があります。3 -SATなどの NP 完全問題に対する建設的かつ効率的な解^{[注 2]}は、以下を含む既存の暗号システムのほとんどを破ることになります。

• 公開鍵暗号の既存の実装^[32]は、インターネットを介した安全な金融取引など、多くの現代のセキュリティアプリケーションの基盤となっています。
• AESや3DESなどの対称暗号^[33]は通信データの暗号化に使用されます。
• 暗号ハッシュはビットコインなどのブロックチェーン 暗号通貨の基盤であり、ソフトウェアアップデートの認証に使用されます。これらのアプリケーションでは、与えられた値にハッシュされるプリイメージを見つけることは困難で、理想的には指数時間がかかります。P = NPの場合、SATへの還元を通じて多項式時間がかかります。^[34]

これらには、 P ≠ NP を仮定しない 情報理論的に安全なソリューションへの修正または置き換えが必要になります。

また、現在数学的に解決困難な多くの問題を扱いやすくすることで、莫大な利益がもたらされるだろう。例えば、オペレーションズリサーチにおける多くの問題は、整数計画法や巡回セールスマン問題などNP完全である。これらの問題に対する効率的な解決策は、物流に多大な影響を与えるだろう。タンパク質構造予測のいくつかの問題など、他の多くの重要な問題もNP完全である。^[35]これらの問題を効率的に解決できるようにすることで、生命科学やバイオテクノロジーが大幅に進歩する可能性がある。

これらの変化は、NP完全問題を効率的に解くことが数学自体にもたらす革命に比べれば取るに足らないものかもしれない。ゲーデルは計算複雑性に関する初期の考えの中で、どんな問題でも解ける機械的な方法が数学に革命をもたらすだろうと指摘した。^{[36] [37]}

もし本当に φ( n ) ∼ k ⋅ n (あるいは ∼ k ⋅ n ² )の機械があったとしたら、これは極めて重要な結果をもたらすだろう。つまり、決定問題の決定不能性にもかかわらず、はい/いいえの質問に関する数学者の頭脳労働は機械によって完全に置き換えられる可能性があるということが明白に意味する。結局のところ、機械が結果を出さなかったときに問題についてそれ以上考える意味がないほど大きな自然数nを選べばよいだけである。

同様に、スティーブン・クックは（証明だけでなく、実際に効率的なアルゴリズムを前提として）次のように述べています。^[28]

... 形式的な証明は多項式時間で簡単に認識できるため、妥当な長さの証明を持つあらゆる定理の形式的な証明をコンピューターが見つけられるようにすることで、数学を変革するでしょう。例題には、CMI の懸賞問題がすべて含まれる可能性があります。

数学研究者は定理の証明に生涯を費やしますが、問題が提起されてから証明が見つかるまでに数十年、あるいは数世紀もかかることがあります。たとえば、フェルマーの最終定理は証明に 3 世紀以上かかりました。「妥当な」サイズの証明が存在する場合に証明を確実に見つけられる方法があれば、この苦労は実質的に終わるでしょう。

ドナルド・クヌースは、P = NPであると信じるようになったが、証明の可能性の影響については慎重であると述べた。^[38]

[...]有限だが非常に大きい数M を想像すると (たとえば、「有限性への対処」に関する私の論文で説明した 10↑↑↑↑3 のような数)、 n個の特定のビットに対してn ^M個のビット単位または加算またはシフト演算を実行するアルゴリズムが膨大な数存在し、それらのアルゴリズムがすべて失敗するとは到底考えられません。しかし、私の主な論点は、たとえ P = NP という等式が証明されたとしても、それが役に立つとは思えないということです。なぜなら、そのような証明はほぼ確実に非構成的だからです。

P≠NPの証明は、P=NPの証明のような実用的な計算上の利点はないが、計算複雑性理論の大きな進歩を示し、将来の研究の指針となるだろう。多くの一般的な問題は効率的に解決できないことが証明され、研究者の注意を部分的な解決や他の問題の解決に集中させることができる。P≠NPが広く信じられているため、このような研究の集中はすでに多く行われている。^[39]

P ≠ NP では、NP における困難な問題の平均ケースの複雑さは未解決のままである。たとえば、SAT は最悪の場合指数関数的な時間を要する可能性があるが、ランダムに選択されたそのインスタンスのほとんどすべてが効率的に解決可能である。ラッセル・インパグリアッツォは、平均ケースの複雑さの問題に対するさまざまな可能な解決策から生じる可能性のある 5 つの仮説的な「世界」について説明している。^[40]これらは、P = NP で SAT のような問題がすべてのインスタンスで効率的に解決できる「アルゴリズム」から、P ≠ NP で P 以外の問題の困難なインスタンスを生成するのは簡単で、3 つの中間的な可能性が NP 困難な問題のインスタンスの難易度のさまざまな可能な分布を反映している「暗号マニア」まで多岐にわたる。P ≠ NP だが NP のすべての問題が平均ケースで扱いやすい「世界」は、論文では「ヒューリスティック」と呼ばれている。2009年のプリンストン大学のワークショップでは、5 つの世界の状況が研究された。^[41]

P = NP 問題自体は、100 万ドルの賞金と膨大な量の熱心な研究にもかかわらず未解決のままですが、この問題を解決するための取り組みにより、いくつかの新しい手法が生まれました。特に、P = NP 問題に関連する最も実りある研究のいくつかは、既存の証明手法ではこの質問に答えるのに不十分であり、新しい技術的アプローチが必要であることを示唆していることを示しています。

この問題の難しさのさらなる証拠として、計算複雑性理論における既知の証明手法は基本的にすべて、次のいずれかの分類に該当しますが、いずれも P ≠ NP を証明するには不十分です。

これらの障壁は、NP 完全問題が有用であるもう一つの理由です。NP 完全問題に対して多項式時間アルゴリズムを実証できれば、上記の結果によって排除されない方法で P = NP 問題を解決できます。

これらの障壁から、一部のコンピュータ科学者は、P対NP問題はZFCのような標準的な公理系から独立している可能性がある（それらの中では証明も反証もできない）と示唆している。独立性の結果は、P ≠ NPであり、これは（例えば）ZFCでは証明できない、またはP = NPであるが、ZFCでは多項式時間アルゴリズムが正しいとは証明できないことを意味する可能性がある。^{[45]しかし、整数演算の}ペアノ公理を拡張したはるかに弱い仮定でも問題が決定不能である場合、すべてのNP問題に対してほぼ多項式時間アルゴリズムが存在する。^[46]したがって、（ほとんどの複雑性理論家がそうであるように）一部のNP問題には効率的なアルゴリズムがないと仮定すると、それらの手法で独立性を証明することは不可能である。これはまた、現在の手法でPAまたはZFCからの独立性を証明することは、すべてのNP問題に効率的なアルゴリズムがあることを証明することほど簡単ではないことを意味している。

P = NP 問題は、記述的複雑性に関する研究の結果として、特定のクラスの論理ステートメントとして言い換えることができます。

線形順序関係を含む固定シグネチャを持つ有限構造のすべての言語を考えてみましょう。すると、P のそのような言語はすべて、適切な最小固定点コンビネータを追加することで、一階述語論理で表現できます。これと順序関係を使用して、再帰関数を定義できます。シグネチャに、区別された順序関係に加えて少なくとも 1 つの述語または関数が含まれている限り、そのような有限構造を格納するために必要なスペースの量は、実際には構造内の要素の数の多項式であり、これは P を正確に特徴付けます。

同様に、NP は存在的二階述語論理、つまり関係、関数、および部分集合に対する全称量化を除外するように制限された二階述語論理で表現可能な言​​語の集合である。多項式階層PHの言語は、二階述語論理のすべてに対応する。したがって、「P は NP の適切な部分集合であるか」という質問は、「存在的二階述語論理は、最小固定点を持つ一階述語論理ではできない言語 (非自明なシグネチャを持つ有限の線形順序構造の) を記述できるか」と再定式化できる。^[47] P = NP は P = PH の場合にのみ成り立つため、前述の特徴付けから「存在的」という言葉を省くことさえできる (前者は NP = co-NP を確立し、それは NP = PH を意味する)。

NP 完全問題に対する既知のアルゴリズムは、多項式時間で実行されません。ただし、NP 完全問題に対して、P = NP の場合にインスタンスを受け入れるときに多項式時間で実行されるアルゴリズムが知られています (ただし、定数が非常に大きいため、アルゴリズムは非実用的です)。ただし、これらのアルゴリズムは、インスタンスを拒否するときの実行時間が多項式ではないため、多項式時間とは言えません。次のアルゴリズムは、Levinによるものです(引用なし)。これは、そのような例です。NP 完全言語SUBSET-SUM を正しく受け入れます。P = NP の場合に限り、SUBSET-SUM にある入力に対して多項式時間で実行されます。

// NP 完全言語 SUBSET-SUM を受け入れるアルゴリズム。
// 
// これは、P = NP の場合に限り、多項式時間アルゴリズムです。
// 
// 「多項式時間」とは
、答えが「はい」であるべきときに多項式時間で「はい」を返し、「いいえ」の場合は永久に実行されることを意味します。
// 
// 入力: S = 整数の有限集合
// 出力: S の任意のサブセットが 0 になる場合は「はい」。
// それ以外の場合は出力なしで永久に実行されます。
// 注: 「プログラム番号 M」は、
整数 M を 2 進数で書き込んでから、
そのビットの文字列をプログラムと見なすことによって取得されるプログラムです
。考えられるすべてのプログラムは
この方法で生成できますが、ほとんどは構文エラーのために何も実行しません
。
K = 1...∞の場合
  M = 1...Kの場合
    入力Sでプログラム番号MをKステップ実行します。
    プログラムが異なる整数のリストを出力する場合
      そして整数はすべてSに含まれる
      かつ、整数の合計は0になる
    それから
      出力「はい」と停止

これは、P = NP の場合にのみ NP 完全言語を受け入れる多項式時間アルゴリズムです。「受け入れる」とは、多項式時間で「はい」の答えを返すが、答えが「いいえ」の場合は永久に実行できることを意味します (セミアルゴリズムとも呼ばれます)。

このアルゴリズムは、P = NP の場合でも、非常に非実用的です。多項式時間で SUBSET-SUM を解くことができる最短のプログラムがbビット長である場合、上記のアルゴリズムは、最初に少なくとも2 ^b − 1 個の他のプログラムを試します。

決定問題とは、アルファベット Σ 上の文字列 w を入力として受け取り、「はい」または「いいえ」を出力する問題です。長さnの任意の入力文字列に対して最大cn ^kステップで正しい答えを生成するアルゴリズム(チューリング マシン、または無制限のメモリを持つコンピュータ プログラムなど) がある場合 ( kとc は入力文字列に依存しない定数)、その問題は多項式時間で解決できるとされ、クラス P に分類されます。正式には、P は決定論的多項式時間チューリング マシンによって決定できる言語の集合です。つまり、

${\displaystyle \mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}}$

どこ

${\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}}$

決定性多項式時間チューリングマシンとは、次の2つの条件を満たす決定性チューリングマシンMのことである。

1. Mはすべての入力wで停止し、
2. が存在する。ここでOは大文字のO記法を指し、${\displaystyle k\in N}$${\displaystyle T_{M}(n)\in O(n^{k})}$

${\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}}$

${\displaystyle t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.}$

NP は、非決定性チューリングマシン (従来の方法) を使用して同様に定義できます。ただし、最新のアプローチでは、証明書と検証者の概念を使用します。正式には、NP は、多項式時間で実行される有限のアルファベットと検証者を持つ言語のセットです。以下は「検証者」を定義します。

L を有限アルファベット Σ 上の言語と します。

L ∈ NP となるのは、次の 2 つの条件が満たされる 2 項関係と正の整数kが存在する場合のみです。${\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}$

1. すべての に対して、( x , y ) ∈ Rかつ で${\displaystyle x\in \Sigma ^{*}}$${\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}$${\displaystyle |y|\in O(|x|^{k})}$あり、
2. 上記の言語は、決定論的チューリングマシンによって多項式時間で決定可能です。${\displaystyle L_{R}=\{x\#y:(x,y)\in R\}}$${\displaystyle \Sigma \cup \{\#\}}$

L _{R を}決定するチューリングマシンはLの検証者と呼ばれ、 ( x , y ) ∈ RとなるyはLにおけるxのメンバーシップの証明書と呼ばれます。

すべての検証が多項式時間である必要はありません。ただし、L がNP であるためには、多項式時間で実行される検証が必要です。

させて

${\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ for integers }}p,q>1\right\}}$

${\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ and }}y{\text{ divides }}x\right\}.}$

xの値が合成数であるかどうかは、 xが COMPOSITE のメンバーであるかどうかと同じです。COMPOSITE ∈ NP は、上記の定義を満たすことを確認することで示されます (自然数をその 2 進表現と同一視する場合)。

COMPOSITEもPに属しており、この事実はAKS素数判定の発明によって証明されている。^[48]

NP 完全性を記述する同等の方法は多数あります。

Lを有限アルファベットΣ上の言語と する。

L がNP 完全となるのは、次の 2 つの条件が満たされた場合のみです。

1. L∈NPであり、
2. NP 内の任意のL' はL ( と表記)に多項式時間還元可能である。ただし、次の 2 つの条件が満たされる場合に限ります。 ${\displaystyle L'\leq _{p}L}$${\displaystyle L'\leq _{p}L}$
   1. f  : Σ* → Σ*が存在し、Σ*内のすべてのwに対して次が成り立つ。${\displaystyle (w\in L'\Leftrightarrow f(w)\in L)}$
   2. 任意の入力wに対してテープ上のf ( w )で停止する多項式時間チューリングマシンが存在する。

あるいは、L ∈ NP であり、多項式時間でLに還元できる別の NP 完全問題がある場合、Lは NP 完全です。これは、新しい問題が NP 完全であることを証明する一般的な方法です。

P対NP問題は一般に未解決であると考えられているが、^[49]多くのアマチュア研究者と一部のプロの研究者が解決策を主張している。ゲルハルト・J・ヴェーギンガーは1986年から2016年までの116の証明のリストをまとめたが、そのうち61はP = NPの証明、49はP ≠ NPの証明、6つは問題が決定不可能であるなどの他の結果を証明した。^[50] P対NPを解決しようとするいくつかの試みはメディアで一時的に注目を集めたが、^[51]これらの試みは反論されている。

ティモシー・ランゾーン監督の映画『巡回セールスマン』は、P対NP問題を解決するために米国政府に雇われた4人の数学者の物語である。^[52]

シンプソンズの第7シーズン「ツリーハウス・オブ・ホラーVI 」の第6話では、ホーマーが偶然「三次元」に迷い込んだ直後にP = NPという式が見られる。^{[53] [54]}

エレメンタリーシーズン2の第2話「Xを解け」では、シャーロックとワトソンがP対NPを解こうとした数学者の殺人事件を捜査する。^{[55] [56]}

• R対RE問題。ここでRはクラスPの類似物であり、REは類似クラスNPである。これらのクラスは等しくない。なぜなら、決定不可能だが検証可能な問題が存在するからである。例えば、ヒルベルトの第10問題はRE完全である。 ^[57]
• 代数的複雑性の理論にも同様の問題がある。VP対VNP問題である。この問題はまだ解決されていない。^{[58] [57]}

• ゲームの複雑さ
• 数学の未解決問題の一覧
• ユニークなゲームの推測
• コンピュータサイエンスにおける未解決の問題

• レイチェル・クロウェル（2021年5月28日）。「数学における未解決のトップ問題は、ほとんどが謎に包まれたまま。21年前に命名された7つのミレニアム懸賞問題のうち、解決されたのは1つだけ」。www . Scientificamerican.com 。 2021年6月21日閲覧。この問題は、検証しやすい質問（NPと呼ばれるクエリのクラス）には、見つけやすい解決策（Pと呼ばれるクラス）もあるかどうかという問題に関係しています。
• Hosch, William L (2009年8月11日). 「P対NP問題数学」.ブリタニカ百科事典. 2021年6月20日閲覧。
• 「P vs NP問題」。www.claymath.org (Cook, Levin) 。 2021年6月20日閲覧。400人の大学生のグループのために住宅の宿泊施設を手配しているとします。スペースは限られており、寮に入居できるのは100人の学生だけです。問題を複雑にしているのは、学部長があなたに相性の悪い学生のペアのリストを提供し、このリストのどのペアも最終選択に含めないように要求したことです。これは、コンピューター科学者がNP問題と呼ぶものの例です...

• コーメン、トーマス(2001)。アルゴリズムの概要。ケンブリッジ: MIT プレス。ISBN 978-0-262-03293-3。
• ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマン アンド カンパニー。ISBN 9780716710455. MR  0519066. OCLC  247570676.
• Goldreich, Oded (2010). P、NP、NP完全性ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-12254-2。オンラインドラフト
• Immerman, Neil (1987). 「複雑性クラスを捉える言語」SIAM Journal on Computing . 16 (4): 760–778. CiteSeerX  10.1.1.75.3035 . doi :10.1137/0216051.
• パパディミトリウ、クリストス（1994年）。計算複雑性。ボストン：アディソン・ウェスレー。ISBN 978-0-201-53082-7。

• Fortnow, L.; Gasarch, W.「計算の複雑さ」。
• Aviad Rubinstein の「P と NP 間の近似の困難さ」は、ACMの 2017 年度博士論文賞を受賞しました。
• 「P vs. NPと計算複雑性の動物園」。2014年8月26日。2021年11月24日時点のオリジナルよりアーカイブ – YouTube経由。