Loading article…
P対NP問題は、理論計算機科学における主要な未解決問題である。簡単に言えば、解を迅速に検証できる問題はすべて、迅速に解くこともできるのか、という問いである。
ここで「迅速に」とは、タスクを解決し、多項式時間で実行されるアルゴリズムが存在することを意味します（例えば、指数時間とは異なります）。つまり、タスクの完了時間は、アルゴリズムへの入力のサイズに関する多項式関数によって上限が定められます。あるアルゴリズムが多項式時間で回答できる質問の一般的なクラスは「P 」または「クラスP」です。一部の質問については、迅速に回答を見つける既知の方法はありませんが、回答が与えられた場合は、迅速に検証できます。回答を多項式時間で検証できる質問のクラスは「 NP」であり、「非決定性多項式時間」を表します。[注1 ] [ 1 ]
P問題とNP問題のどちらが正しいかという問いへの答えは、多項式時間で検証できる問題が多項式時間で解けるかどうかを決定する。広く信じられているように、P ≠ NPであれば、NPには検証するよりも計算する方が難しい問題が存在することになる。つまり、それらの問題は多項式時間で解くことはできないが、その答えは多項式時間で検証できるということだ。
この問題は、コンピュータ科学における最も重要な未解決問題と呼ばれています。[ 2 ]計算理論における重要な問題であることに加えて、どちらの証明も、数学、暗号、アルゴリズム研究、人工知能、ゲーム理論、マルチメディア処理、哲学、経済学、その他多くの分野に大きな影響を与えるでしょう。[ 3 ] これは、クレイ数学研究所が選定した7つのミレニアム懸賞問題の1つであり、それぞれ最初の正解に対して100万米ドルの賞金が授与されます。
次のイエス/ノー問題を考えてみましょう。、行、列、および正方形には1からまでの整数が含まれています候補解が与えられた場合、この一般化された数独問題の「はい」のインスタンスを検証するのは簡単です。しかし、この問題のすべてのインスタンスに対して「はい」または「いいえ」を正しく答えることができる多項式時間アルゴリズムが存在するかどうかは不明です。したがって、一般化された数独はNP（迅速に検証可能）に属しますが、P（迅速に解ける）に属する場合もあれば、属さない場合もあります。（固定サイズの数独には有限個のグリッドしか存在しないため、数独の一般化バージョンを考慮する必要があります。この場合、表を参照することで答えを見つけることができるため、問題はPに属します。）
P対NP問題の正確な記述は、1971年にスティーブン・クックが彼の画期的な論文「定理証明手続きの複雑性」[ 4 ]で、また1973年にレオニード・レヴィンが独立して[ 5 ]で提唱した。
P対NP問題は1971年に正式に定義されたが、その根底にある問題については以前から兆候があった。1955年、数学者のジョン・ナッシュは国家安全保障局に手紙を書き、十分に複雑な暗号を解読するのに必要な時間は鍵の長さに比例して指数関数的に増加すると推測した。[ 6 ]もしこれが証明されれば、[注2 ]これは現在P ≠ NPと呼ばれるものを意味することになる。なぜなら、提案された鍵は多項式時間で検証できるからである。1956年にクルト・ゲーデルがジョン・フォン・ノイマンに 書いた手紙の中で、ゲーデルは定理証明（現在ではco-NP完全であることが知られている）が2次時間または線形時間で解けるかどうかを尋ね、もしそうであれば、数学的証明の発見を自動化できると提唱した。[ 7 ]
計算複雑性クラスPとNPの関係は、計算複雑性理論において研究されています。計算複雑性理論とは、与えられた問題を解決するために計算中に必要となるリソースを扱う計算理論の一部です。最も一般的なリソースは、時間（問題を解決するのに必要なステップ数）と空間（問題を解決するのに必要なメモリ量）です。
このような分析では、分析対象となるコンピュータのモデルが必要となる。一般的に、このようなモデルは、コンピュータが決定論的（コンピュータの現在の状態と入力が与えられた場合、コンピュータが取り得る動作は1つしかない）かつ逐次的（動作を順番に実行する）であると仮定する。
この理論では、クラス P は、入力サイズの多項式時間で決定性逐次マシン上で解けるすべての決定問題 (以下で定義) から構成されます。クラスNPは、適切な情報が与えられた場合に正の解が多項式時間で検証できる、または同等に、非決定性マシン上で多項式時間で解を見つけることができるすべての決定問題から構成されます。[ 8 ]明らかに、P ⊆ NP です。理論計算機科学における最大の未解決問題は、おそらくこれら 2 つのクラスの関係に関するものです。
2001 年以来、ウィリアム・ガサーチはP ≠ NP および関連する問題に関する研究者への 3 回の世論調査を実施しました。[ 9 ] [ 10 ] [ 11 ] P ≠ NP であると信じている回答者の割合は 、2001 年は 61%、[注 3 ] 2011 年は 83%、2018 年は 88% で、それぞれ 100、151、124 の回答がありました。[ 11 ]専門家に限定すると、2018 年の回答者の 99% が P ≠ NP であると信じていました。[ 11 ]これらの世論調査は P = NP であるかどうかを意味するものではありません。ガサーチが述べたように、「これは P=?NP の解決に近づくものでも、いつ解決されるかを知るものでもないが、この時代の主観的な意見に関する客観的な報告を試みている」のです。[ 9 ]
P = NP問題に取り組む上で、NP完全性の概念は非常に有用です。NP完全問題とは、他のNP問題が多項式時間で還元可能であり、かつその解が多項式時間で検証可能な問題のことです。つまり、任意のNP問題は任意のNP完全問題に変換できます。非公式には、NP完全問題とは、NPに属する他のどの問題よりも少なくとも同程度に「難しい」NP問題のことです。
NP困難問題とは、NP問題と同等以上の難しさを持つ問題のことです。つまり、すべてのNP問題は（多項式時間で）NP困難問題に還元できます。NP困難問題は必ずしもNPに属する必要はありません。つまり、解が多項式時間で検証可能である必要はありません。
例えば、クック・レヴィンの定理により、ブール充足可能性問題はNP完全問題であるため、 NPに属するあらゆる問題のインスタンスは、多項式時間で機械的にブール充足可能性問題に変換できます。ブール充足可能性問題は、数多くのNP完全問題の一つです。もしNP完全問題がPに属するならば、P = NPとなるはずです。しかしながら、多くの重要な問題がNP完全問題であり、それらのいずれに対しても高速なアルゴリズムは知られていません。
定義だけでは、NP完全問題が存在することは直感に反するが、自明なNP完全問題は次のように定式化できる。多項式時間で停止することが保証されているチューリングマシンMが与えられたとき、 Mが受け入れる多項式サイズの入力が存在するか？ [ 12 ]これは、(入力が与えられたとき) MをシミュレートすることでMが入力を受け入れるかどうかを簡単にチェックできるため、NPに属する。また、NPに属する問題の特定のインスタンスの検証器は、検証対象の解を入力として受け取る多項式時間マシンMとしてエンコードできるため、NP完全である。そして、インスタンスがはいインスタンスかいいえインスタンスかという問題は、有効な入力が存在するかどうかによって決定される。
NP完全であることが証明された最初の自然な問題は、SATとしても知られるブール充足可能性問題でした。前述のように、これはクック・レヴィンの定理であり、充足可能性がNP完全であることの証明には、NPの定義に関連するチューリングマシンの技術的な詳細が含まれています。しかし、この問題がNP完全であることが証明された後、還元による証明により、先に述べた数独ゲームを含む他の多くの問題もNP完全であることを示すより簡単な方法が提供されました。この場合、証明は、数独を多項式時間で解くことで、ラテン方陣を多項式時間で完成させることもできることを示しています。[ 13 ]これにより、三部グラフを三角形に分割する問題の解が得られ、[ 14 ]これにより、3-SATとして知られるSATの特殊なケースの解を見つけることができ、[ 15 ]これにより、一般的なブール充足可能性の解が得られます。つまり、数独の多項式時間解法は、一連の機械的な変換によって充足可能性問題の多項式時間解法につながり、さらに充足可能性問題を用いて他のあらゆるNP問題を多項式時間で解くことができる。このような変換を用いることで、一見無関係に見える膨大な数の問題が互いに還元可能となり、ある意味で「同じ問題」となるのである。
P = NPかどうかは不明ですが 、P に属さない問題は知られています。クラス P が多項式実行時間で定義されているのと同様に、クラスEXPTIMEは指数実行時間を持つすべての決定問題の集合です。言い換えれば、EXPTIME に含まれる問題は、nの多項式関数p ( n ) である決定性チューリングマシンによってO (2 p ( n ) ) 時間で解くことができます。決定問題が EXPTIME に含まれる場合、その問題はEXPTIME 完全であり、EXPTIME に含まれるすべての問題には、多項式時間で多対一に還元できます。EXPTIME 完全であることが知られている問題がいくつかあります。P ≠ EXPTIMEであることが示せるため、これらの問題は P に属さず、多項式時間よりも長い時間を要します。実際、時間階層定理により、指数時間よりも大幅に短い時間で解くことはできません。例としては、 N × N盤上のチェスの位置に対する完全戦略を見つけること[ 16 ]や、他のボードゲームに関する同様の問題[ 17 ]などがあります。
プレスバーガー算術における命題の真偽判定問題は、さらに長い時間を要する。フィッシャーとラビンは1974年に[ 18 ] 、長さnのプレスバーガー命題の真偽判定を行うすべてのアルゴリズムの実行時間が少なくともであることを証明した。ある定数cに対して。したがって、この問題は指数関数的な実行時間を超える必要があることが知られています。停止問題のような決定不能な問題はさらに困難です。特定のアルゴリズムに対して、そのアルゴリズムが正しい答えを生成しない入力が少なくとも 1 つ存在するという意味で、これらの問題はどのアルゴリズムでも完全に解決することはできません。つまり、間違った答えを生成するか、決定的な答えを出さずに終了するか、あるいは答えを全く生成せずに永遠に実行され続けるかのいずれかになります。
決定問題以外の問題も検討できます。そのようなクラスの1つで、計数問題からなるものは#Pと呼ばれます。NP問題が「解は存在するか？」と問うのに対し、対応する#P問題は「解はいくつ存在するか？」と問うものです。解の数を数えれば、少なくとも1つの解が存在するかどうかがすぐにわかるので、#P問題は対応するNP問題と少なくとも同程度に難しいことは明らかです。解の数が0より大きい場合、解の数を数えることで解が存在するかどうかがわかります。驚くべきことに、難しいと考えられている#P問題の中には、簡単な（例えば線形時間）P問題に対応するものがあります。[ 19 ]これらの問題では、解が存在するかどうかは非常に簡単にわかりますが、解の数を判断するのは非常に難しいと考えられています。これらの問題の多くは#P完全であり、したがって#Pの中で最も難しい問題の一つです。なぜなら、これらの問題のいずれかを多項式時間で解くことができれば、他のすべての#P問題も多項式時間で解けるようになるからです。
1975年、リチャード・E・ラドナーは、 P ≠ NP の場合、NP には P にも NP 完全性にも属さない問題が存在することを示した。[ 20 ]このような問題は NP 中間問題と呼ばれる。グラフ同型問題、離散対数問題、整数因数分解問題は、NP 中間問題であると考えられている問題の例である。これらは、P に属することも NP 完全性も知られていない、ごく少数の NP 問題である。
グラフ同型性問題は、2 つの有限グラフが同型であるかどうかを判定する計算問題です。複雑性理論における重要な未解決問題は、グラフ同型性問題が P、NP 完全、または NP 中間に属するかどうかです。答えはわかっていませんが、少なくとも NP 完全ではないと考えられています。[ 21 ]グラフ同型性が NP 完全である場合、多項式時間階層は第 2 レベルに縮退します。[ 22 ]多項式階層は有限レベルに縮退しないと広く考えられているため、グラフ同型性は NP 完全ではないと考えられています。この問題に対する最良のアルゴリズムは、László Babaiによるもので、準多項式時間で実行されます。[ 23 ]
整数因数分解問題は、与えられた整数の素因数分解を求める計算問題です。決定問題として表現すると、入力がkより小さい因数を持つかどうかを判定する問題です。効率的な整数因数分解アルゴリズムは知られておらず、この事実はRSAアルゴリズムなどのいくつかの現代的な暗号システムの基礎となっています。整数因数分解問題は NP およびco-NP (さらにUPおよび co-UP [ 24 ]にも)に属します。問題が NP 完全である場合、多項式時間階層は最初のレベル (つまり NP = co-NP) に縮退します。整数因数分解のための最も効率的な既知のアルゴリズムは、一般的な数体篩法であり、期待時間で計算できます。
nビット整数を因数分解する。この問題に対する最もよく知られた量子アルゴリズムであるショアのアルゴリズムは多項式時間で実行されるが、これは非量子複雑性クラスに関して問題がどこにあるかを示すものではない。
上記の議論はすべて、Pが「簡単」を意味し、「Pに含まれない」が「難しい」を意味するという前提に基づいています。これはコブハムのテーゼとして知られる前提です。これは複雑性理論では一般的な前提ですが、注意点があります。
まず、実際には誤りとなる可能性があります。理論的な多項式アルゴリズムは、非常に大きな定数因子や指数を持つ場合があり、実用的ではありません。たとえば、グラフGがHをマイナーとして含むかどうかを判定する問題 ( Hは固定)は、 O ( n 2 )の実行時間で解決できます[ 26 ] 。ここでnはGの頂点数です。しかし、ビッグ O 表記は、Hに超指数関数的に依存する定数を隠しています。この定数は、（クヌースの上向き矢印表記を使用）、ここでhはHの頂点の数である。[ 27 ]
一方、問題がNP完全であることが示されていても、P ≠ NPであっても、実際にはその問題に対する効果的なアプローチが存在する可能性がある。ナップサック問題、巡回セールスマン問題、ブール充足可能性問題など、多くのNP完全問題に対して、妥当な時間で多くの実世界のインスタンスを最適に解くことができるアルゴリズムが存在する。このようなアルゴリズムの経験的な平均ケース複雑度（時間対問題サイズ）は驚くほど低い場合がある。線形計画法のシンプレックス法は、実際には驚くほどよく機能する。指数関数的な最悪ケースの時間複雑度にもかかわらず、最もよく知られている多項式時間アルゴリズムと同等の速度で動作する。[ 28 ]
最後に、量子計算やランダム化アルゴリズムなど、PとNPが定義されているチューリングマシンモデルに適合しないタイプの計算も存在する。
クックは、「P 対 NP 問題」でこの問題を「P はNP か？」と言い換えている[ 29 ]。世論調査によると[ 9 ] [ 30 ]、ほとんどのコンピュータ科学者は P ≠ NP であると信じている。この信念の主な理由は、これらの問題を何十年も研究してきたにもかかわらず、3,000 を超える重要な既知の NP 完全問題のいずれに対しても多項式時間アルゴリズムを見つけることができていないことである ( NP 完全問題のリストを参照)。これらのアルゴリズムは、NP 完全性の概念が定義されるずっと前から求められていた (最初に発見された21 の NP 完全問題は、すべて NP 完全であることが示された時点でよく知られた既存の問題であった)。さらに、P = NP という結果は、NP = co-NPや P = PHなど、現在誤りであると考えられている他の多くの驚くべき結果を意味することになる。
また、解決が難しいが解決策の検証が容易な問題の存在は、現実世界の経験と一致すると直感的に主張されている。[ 31 ]
P=NPであれば、世界は私たちが普段考えているものとは全く異なる場所になるだろう。「創造的な飛躍」に特別な価値はなく、問題を解決することと、解決策が見つかった後にそれを認識することには根本的な隔たりはなくなるだろう。
一方、P ≠ NP を信じるのは過信であり、研究者は P = NP の証明も探求すべきだと考える研究者もいる。例えば、2002 年に次のような発言がなされた。[ 9 ]
P ≠ NPを支持する主な論拠は 、網羅的探索の分野における根本的な進歩が全く見られないという点である。しかし、これは私の意見では非常に弱い論拠である。アルゴリズムの空間は非常に広大であり、私たちはまだその探求の始まりに過ぎない。[...]フェルマーの最終定理の解決は、非常に単純な問題でさえ、非常に深い理論によってのみ解決され得ることを示している。
憶測に固執することは、研究計画を立てる上で良い指針とは言えません。あらゆる問題について、常に両方の方向性を試みるべきです。偏見のために、著名な数学者たちが、必要な手法をすべて開発していたにもかかわらず、予想とは正反対の解法で有名な問題を解決できなかった例があります。
PとNPの定義において「多項式時間」を「マルチテープチューリングマシン上の線形時間」に置き換えると、クラスDLINとNLINが得られる。DLIN ≠NLINであることは知られている[ 32 ] 。
この問題がこれほど注目を集める理由の一つは、考えられる解答がもたらす結果にある。どちらの解決策も理論を大きく前進させるだけでなく、おそらく実務面でも大きな影響を与えるだろう。
P = NPの証明は、 NPに属する重要な問題のいくつかを効率的に解決する方法につながる場合、驚くべき実用的な影響をもたらす可能性がある。NP完全問題は多くの分野で基礎的なものであるため、その潜在的な影響は、肯定的側面と否定的側面の両方を含む。
証明がNP完全問題に対する実用的なアルゴリズムにつながるとは限らないことも十分に考えられます。問題の定式化では、境界多項式が小さいことや、特定の値が既知であることさえ要求されません。非構成的な証明では、解を求めるアルゴリズムや特定の境界を指定せずに解が存在することを示すことができます。たとえ証明が構成的で、境界多項式とアルゴリズムの詳細が明示されていたとしても、多項式の次数が低次でない場合、アルゴリズムは実際には十分な効率を発揮しない可能性があります。この場合、最初の証明は主に理論家にとって興味深いものとなるでしょうが、多項式時間解法が可能であるという知識は、それを実現するためのより良い（そしておそらく実用的な）方法の研究を確実に促進するでしょう。
P = NPを示す解法は、特定の難問を前提とする暗号学 の分野を根底から覆す可能性がある。3 -SATのような NP 完全問題に対する建設的かつ効率的な解法[注 4 ]は、以下を含む既存のほとんどの暗号システムを破ることになる。
これらは、P ≠ NPを仮定しない情報理論的に安全なソリューションに修正または置き換える必要があるだろう。
現在数学的に解決不可能な多くの問題を扱いやすくすることで、計り知れないほどのメリットも生まれます。例えば、オペレーションズリサーチにおける多くの問題はNP完全であり、整数計画法や巡回セールスマン問題などが挙げられます。これらの問題に対する効率的な解決策は、物流に計り知れない影響を与えるでしょう。タンパク質構造予測におけるいくつかの問題など、他の多くの重要な問題もNP完全です。[ 36 ]これらの問題を効率的に解決できるようにすることで、生命科学やバイオテクノロジーを大幅に進歩させることができるでしょう。
これらの変化は、NP完全問題を効率的に解くことが数学自体にもたらす革命に比べれば取るに足らないものかもしれない。ゲーデルは、計算複雑性に関する初期の考察の中で、あらゆる問題を解決できる機械的な方法が数学に革命をもたらすだろうと述べている。[ 37 ] [ 38 ]
もし本当にφ( n ) ∼ k ⋅ n (あるいは ∼ k ⋅ n 2 )のような機械が存在するならば、それは極めて重要な結果をもたらすだろう。すなわち、決定問題の不確定性にもかかわらず、イエス・ノー問題に関する数学者の思考作業は、機械によって完全に置き換えられることになる。結局のところ、機械が結果を出力しない場合、その問題についてそれ以上考える意味がなくなるほど大きな自然数nを選択すればよいだけなのだ。
同様に、スティーブン・クックは（証明だけでなく、実用的に効率的なアルゴリズムを前提として）次のように述べている。[ 29 ]
… これは、形式的な証明は多項式時間で容易に認識できるため、妥当な長さの証明を持つ定理であれば、コンピュータが形式的な証明を見つけることを可能にすることで、数学を変革するだろう。例としては、CMI賞のすべての問題が含まれる可能性がある。
研究数学者は定理の証明に生涯を費やしますが、問題提起から証明の発見まで数十年、あるいは数世紀を要する場合もあります。例えば、フェルマーの最終定理の証明には3世紀以上を要しました。「妥当な」規模の証明が存在する場合に必ず証明を見つける方法があれば、この苦労は事実上終結するでしょう。
ドナルド・クヌースは 、P = NPであると信じるようになったと述べている が、証明の可能性がもたらす影響については慎重な姿勢を示している。[ 39 ]
[...] 有限ではあるが途方もなく大きな数Mを想像してみてください。例えば、私の論文「有限性への対処」で議論した 10↑↑↑↑3 のような数です。すると、与えられたnビットに対してn Mビットごとの演算、加算、またはシフト演算を行うアルゴリズムが膨大な数存在し、それらのアルゴリズムすべてが失敗するとは到底考えにくいでしょう。しかし、私の主な主張は、P = NPという等式が証明されたとしても役に立つとは思えないということです。なぜなら、そのような証明はほぼ確実に非構成的になるからです。
P ≠ NPの証明は、P = NP の証明のような実用的な計算上の利点はないものの、計算複雑性理論における大きな進歩であり、今後の研究の指針となるだろう。多くの一般的な問題は効率的に解決できないことが示され、研究者の注意は部分的な解決策や他の問題の解決策に集中できるようになる。P ≠ NP が広く信じられているため、こうした研究の集中化は既に多く行われている。[ 40 ]
P ≠ NP では、NP の難問の平均ケースの複雑さは 未解決のままです。たとえば、SAT は最悪の場合指数時間を要する可能性がありますが、ランダムに選択されたインスタンスのほぼすべてが効率的に解ける可能性があります。Russell Impagliazzo は、平均ケースの複雑さの問題に対するさまざまな解決策から生じる可能性のある 5 つの仮想的な「世界」について説明しています。[ 41 ]これらは、P = NP で SAT のような問題がすべてのインスタンスで効率的に解ける「Algorithmica」から、 P ≠ NP で P 外の問題の難問インスタンスの生成が容易な「Cryptomania」まで、NP 難問インスタンスの難易度のさまざまな分布を反映した 3 つの中間の可能性まであります。P ≠ NP ですが、NP のすべての問題が平均ケースで扱いやすい「世界」は、論文では「Heuristica」と呼ばれています。2009年にプリンストン大学で行われたワークショップでは、5 つの世界の状況が研究されました。[ 42 ]
分離はないが、そして が既知であるが、より大きなリソースの制約と計算の制限されたモデルに対しては、より強い分離が既知である。たとえば、時間階層定理は、 。
関連する主要なプログラムでは、非一様ブール回路に対する下限を研究します。多項式サイズで一定の深さを持つ回路ファミリーで構成され、無制限のファンインを持つANDゲートとORゲート、NOTゲート、およびモジュラカウントゲートを使用する。 固定定数の場合。
2011年から2014年にかけて、ライアン・ウィリアムズは[ 43 ] [ 44 ]を証明した。
そして結果として
この証明は、充足可能性アルゴリズムと 非決定論的時間階層定理を持つ回路：小さな回路を仮定すると、充足可能性アルゴリズムは非決定論的指数時間の不可能なシミュレーションに変換されます。
マレーとウィリアムズは後に、非決定性準多項式時間という領域をさらに拡大した。
ここはどこ意味する チェンはその後、平均的なケースの強化を証明した。すべての定数に対して言語の一部利点をもって近似することはできない多項式サイズによるランダム推測よりも回路。
これらの結果はP対NPを解決するものではありません。これらはより大きな均一複雑性クラスを制限された非均一回路クラスから分離しますが、からまた、それらは無制限の多項式サイズの回路の下限を確立するものではない。 。
P = NP問題自体は、100万ドルの賞金と膨大な研究努力にもかかわらず未解決のままだが、この問題の解決に向けた努力は、いくつかの新しい手法を生み出してきた。特に、P = NP問題に関する最も実りある研究のいくつかは、既存の証明手法ではこの問題に答えるには不十分であることを示し、斬新な技術的アプローチが必要であることを示唆している。
問題の難しさを示す追加的な証拠として、計算複雑性理論における既知の証明手法はほぼすべて以下のいずれかの分類に該当し、いずれもP ≠ NPを証明するには不十分である。
これらの障壁は、NP完全問題が有用であるもう一つの理由です。NP完全問題に対して多項式時間アルゴリズムが実証できれば、上記の結果によって排除されない方法でP = NP問題を解決できるからです。
これらの障壁から、一部のコンピュータ科学者は、P 対 NP 問題はZFCのような標準的な公理系とは独立している可能性があると示唆している(それらの内部では証明も反証もできない)。独立性の結果は、P ≠ NP であり、これは (例えば) ZFC では証明できないか、P = NP であるが、多項式時間アルゴリズムが正しいことは ZFC では証明できないことを意味する可能性がある。[ 48 ]しかし、整数演算のペアノ公理を拡張するはるかに弱い仮定でも問題が決定不能である場合、ほぼすべての NP 問題に対して多項式時間アルゴリズムが存在する。[ 49 ]したがって、(ほとんどの計算複雑性理論家がそうであるように) いくつかの NP 問題には効率的なアルゴリズムがないと仮定すると、これらの手法による独立性の証明は不可能である。これはまた、現在の手法で PA または ZFC からの独立性を証明することは、すべての NP 問題に効率的なアルゴリズムがあることを証明するよりも容易ではないことを意味する。
記述的複雑性の研究の結果として、P = NP問題は特定の論理命題のクラスとして再定式化することができる。
線形順序関係を含む固定シグネチャを持つ有限構造のすべての言語を考えます。すると、P に含まれるそのような言語はすべて、適切な最小不動点コンビネータを追加することで一階述語論理で表現できます。再帰関数は、これと順序関係を用いて定義できます。シグネチャに、区別された順序関係に加えて少なくとも 1 つの述語または関数が含まれている限り、つまり、そのような有限構造を格納するために必要な空間の量が、構造内の要素数に対して多項式である限り、これは P を正確に特徴づけます。
同様に、NP は存在二階述語論理で表現可能な言語の集合です。つまり、関係、関数、部分集合に対する全称量化を除外するように制限された二階述語論理です。多項式階層PHの言語は、二階述語論理のすべてに対応します。したがって、「P は NP の適切な部分集合か」という質問は、「存在二階述語論理は、最小不動点を持つ一階述語論理では記述できない言語 (非自明なシグネチャを持つ有限線形順序構造の言語) を記述できるか」と再定式化できます。[ 50 ]「存在」という言葉は、P = NP であるのは P = PH である場合のみであるため、前の記述から削除することもできます(前者は NP = co-NP を確立し、これは NP = PH を意味します)。
NP完全問題に対する既知のアルゴリズムは、多項式時間で実行されるものはありません。しかし、NP完全問題に対して、P = NP の場合、受理インスタンスに対して多項式時間で実行されるアルゴリズムは知られています（ただし、定数が非常に大きいため、実用的ではありません）。しかし、これらのアルゴリズムは、拒否インスタンスの実行時間が多項式時間ではないため、多項式時間とは言えません。Levin による以下のアルゴリズム（引用なし）は、そのような例です。このアルゴリズムは、NP完全言語 SUBSET-SUM を正しく受理します。入力 が SUBSET-SUM に含まれる場合、かつその場合に限り、このアルゴリズムは多項式時間で実行されます 。
// NP完全言語SUBSET-SUMを受け入れるアルゴリズム。// // これは、P = NPの場合に限り多項式時間アルゴリズムです。// // 「多項式時間」とは、答えが「yes」であるべき場合に多項式時間で「yes」を返し、「no」の場合は永久に実行されることを意味します。 // // 入力: S = 有限個の整数の集合// 出力: Sの任意の部分集合の合計が0になる場合は「yes」。 // それ以外の場合は出力なしで永久に実行されます。// 注: 「プログラム番号M」は、整数Mをバイナリで書き、// そのビット列をプログラムとみなすことで得られるプログラムです。 // 可能なすべてのプログラムをこの方法で生成できますが、構文エラーのためほとんどは何も実行しません。 K = 1...∞ の場合 M = 1...K の場合 入力Sを用いてプログラム番号MをKステップ実行する。 プログラムが異なる整数のリストを出力する場合 そして、整数はすべてSに属します そして、それらの整数の合計は0になる。 それから 出力「yes」と停止
これは、NP完全言語をP = NPの場合にのみ受理する多項式時間アルゴリズムです。「受理する」とは、多項式時間で「はい」の答えを返すことを意味しますが、「いいえ」の答えの場合は無限に実行が継続されます（半アルゴリズムとも呼ばれます）。
このアルゴリズムは、P = NPの場合でも、非常に非実用的です 。SUBSET-SUM を多項式時間で解ける最短のプログラムがbビット長の場合、上記のアルゴリズムは少なくとも2 b − 1 個の他のプログラムを最初に試すことになります。
決定問題とは、アルファベット Σ 上の文字列wを入力として受け取り、「はい」または「いいえ」を出力する問題です。任意の長さnの入力文字列に対して、最大でcn kステップで正しい答えを生成するアルゴリズム(チューリングマシン、または無制限のメモリを持つコンピュータ プログラムなど) が存在する場合、その問題は多項式時間で解けるといい、クラス P に分類します。形式的には、P は決定性多項式時間チューリング マシンで決定できる言語の集合です。つまり、
どこ
決定性多項式時間チューリングマシンとは、次の2つの条件を満たす決定性チューリングマシンMのことである。
NPは、非決定性チューリングマシン（従来の方法）を用いて同様に定義することもできます。しかし、現代的なアプローチでは、証明書と検証器の概念を用います。形式的には、NPは有限アルファベットと多項式時間で実行される検証器を持つ言語の集合です。以下は「検証器」の定義です。
L を有限アルファベット Σ 上の言語とする。
L ∈ NP は、二項関係が存在する場合に限り成り立つ。そして、以下の2つの条件を満たす正の整数kが存在する。
L ∈ Rを判定するチューリングマシンはLの検証器と呼ばれ、 ( x , y ) ∈ Rとなるyは、 xがLに属していることの証明書と呼ばれます。
すべての検証器が多項式時間である必要はありません。しかし、LがNPに属するためには、多項式時間で動作する検証器が存在しなければなりません。
させて
xの値が合成数であるかどうかは、 xがCOMPOSITEの要素であるかどうかと同等である。自然数をその二進数表現と同一視すれば、COMPOSITEが上記の定義を満たすことを検証することで、COMPOSITE ∈ NPであることが示される。
COMPOSITE も P に属しており、この事実はAKS 素数判定法の発明によって証明されている。[ 51 ]
NP完全性を説明する方法は数多く存在する。
Lを有限アルファベットΣ上の言語とする。
LがNP完全であるのは、以下の2つの条件が満たされる場合に限る。
あるいは、L ∈ NP であり、 Lに多項式時間で還元できる別の NP 完全問題が存在する場合、Lは NP 完全である。これは、新しい問題が NP 完全であることを証明する一般的な方法である。
P 対 NP 問題は一般的に未解決と考えられているが、[ 52 ]多くのアマチュア研究者や一部のプロの研究者が解決策を主張している。ゲルハルト J. ウォエギンガーは、1986 年～ 2016 年にかけての 116 件の証明とされるものをリストアップしたが、そのうち 61 件は P = NP の証明、49 件は P ≠ NP の証明、6 件はその他の結果、例えば問題が決定不能であることを証明したものであった。[ 53 ] P 対 NP 問題を解決しようとする試みのいくつかは、短期間メディアの注目を集めたが、[ 54 ]これらの試みは反駁されている。
ティモシー・ランゾーン監督の映画『トラベリング・セールスマン』は、P対NP問題を解決するために米国政府に雇われた4人の数学者の物語である。[ 55 ]
シンプソンズ第7シーズンの第6話「ツリーハウス・オブ・ホラーVI 」では、ホーマーが偶然「3次元」に迷い込んだ直後に、方程式 P = NP が見られる。 [ 56 ] [ 57 ]
『エレメンタリー』シーズン2の第2話「Xを解け」では、ホームズとワトソンがP対NP問題を解こうとしていた数学者たちの殺人事件を捜査する。[ 58 ] [ 59 ]
アニメシリーズ『フューチュラマ』のシーズン2のエピソード「Put Your Head on My Shoulders 」では、P対NP問題への視覚的な言及が背景に登場します。フライと同僚のエイミー・ウォンが内緒話をするために物置に引きこもるシーンで、彼らの後ろの「緊急用ビーンズ」とラベルの貼られた箱の横の棚に、同じサイズの2冊の本が置かれており、1冊には「P」、もう1冊には「NP」と書かれています。[ 60 ] [ 61 ]
検証が容易な問題 (NP と呼ばれるクエリのクラス) には、簡単に見つけられる解決策 (P と呼ばれるクラス) があるかどうかという問題に関係しています。
人の大学生の寮の手配をしているとしましょう。スペースには限りがあり、寮に入れるのは100人だけです。さらに厄介なことに、学部長から相性の悪い学生のペアのリストが渡され、最終的な選択にこのリストのペアを含めないように求められています。これは、コンピュータ科学者がNP問題と呼ぶものの例です。
![{\displaystyle {\mathsf {NTIME}}[n^{\log ^{O(1)}n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/344c3a9cf9feb5d3024068ebc98242dc3f0f7ca5)
