複雑さクラスの図は
複雑さクラスの図は、 P ≠ NP という条件を与えました。 NP と NP の両方の外側に問題が存在することは、その仮定のもとで、ラドナーの定理によって確立されました。
P vs. NP問題は、コンピュータサイエンスにおける主要な未解決問題です。その解決策が迅速に検証できる（技術的には、多項式時間で検証できる）すべての問題もまた迅速に（また、多項式時間で）解決できるかどうかを尋ねます。
根本的な問題は、John Forbes Nash Jr.から国家安全保障局へ、そしてKurtGödelからJohn von Neumannへの手紙で1950年代に最初に議論されました。 P NP 問題の正確な記述は、1971年にスティーブン・クックが自身の論文「定理証明手続きの複雑さ」[2]（および独立してLeonid Levinによって1973年[3]）そして多くの人にコンピューター科学の最も重要な未解決問題であると考えられている。[4] クレイ数学研究所によって選ばれた7つのミレニアム賞問題のうちの1つである。最初の正しい解決策。
上記で使用された非公式の用語は、多項式時間で実行されるタスクを解くアルゴリズムの存在を意味し、タスクを完了する時間は次式のサイズの多項式関数として変化します。 （指数関数的な時間とは対照的に）アルゴリズムへの入力。あるアルゴリズムが多項式時間で答えを出すことができる一般的な種類の質問は、「クラス P 」または単に「 P 」と呼ばれます。いくつかの質問では、答えを素早く見つけるための既知の方法はありませんが、答えが何であるかを示す情報が提供されていれば、答えを素早く検証することが可能です。多項式時間で答えを検証することができる質問のクラスは NP と呼ばれ、これは「非決定性多項式時間」を表します。 [Note 1] [edit]
数独を考えてみましょう。プレイヤーは数字で部分的に埋められたグリッドを与えられ、特定のルールに従ってグリッドを完成しようとします。任意のサイズの不完全な数独グリッドを考えると、少なくとも1つの法的な解決策はありますか？提案されたどの解も容易に検証され、解がチェックされるまでの時間はグリッドが大きくなるにつれてゆっくりと（多項式的に）長くなります。しかし、解を見つけるための既知のアルゴリズムはすべて、難しい例では、グリッドが大きくなるにつれて指数関数的に成長する時間がかかります。ですから、数独は NP にあります（すぐに確認できます）が、P にはいません（すぐに解決できます）。他の何千もの問題は似ているように見えますが、それらはチェックするのは速いですが解決するのは遅いです。研究者らは、NP の問題の多くは、 NP の他の問題に対する素早い解決策を構築するために、それらのうちの1つに対する高速な解決策を使用できるという特別な性質を持っていることを示しました。 NP 完全性と呼ばれる特性。何十年にもわたる検索では、これらの問題のいずれに対しても迅速な解決策は得られていません。したがって、ほとんどの科学者は、これらの問題のどれも迅速に解決できないと考えています。しかしこれは証明されたことがない。
P = NP の質問に対する答えは、数独のように多項式時間で検証できる問題も多項式時間で解決できるかどうかを決定するでしょう。 P ≠ NP であることが判明した場合、それは検証するよりも計算するのが難しい問題があることを意味するでしょう。それらは解決することができませんでした。多項式時間で、しかし答えは多項式時間で確かめることができます。
計算理論における重要な問題であることは別として、どちらの方法でも証明は数学、暗号学、アルゴリズム研究、人工知能、ゲーム理論、マルチメディア処理、哲学、経済学および他の多くの分野に深い意味を持つだろう。 edit
P 対 NP の問題は、1971年に正式に定義されましたが、関連する問題の以前の墨塗り、難しさがありました証明の可能性と潜在的な結果。 1955年に、数学者のJohn NashがNSAに手紙を書き、十分に複雑なコードを解読するにはキーの長さに指数関数的な時間が必要であると推測しました。提案された鍵は多項式時間で容易に検証できるので、現在は P ≠ NP と呼ばれます。根本的な問題についての別の言及は、KurtGödelがJohn von Neumannに宛てて書いた1956年の手紙で起こりました。ゲーデルは、定理証明（現在 co-NP – 完全であることが知られている）を2次または線形時間で解くことができるか[7] 、そして最も重要な結果の1つを指摘した。数学的証明の発見は自動化することができます。
Context [ edit ]
P と NP の関係は、計算の複雑さの理論で研究されています。与えられた問題を解決するために計算中に必要とされるリソースを扱う計算の理論。最も一般的なリソースは、時間（問題を解決するために必要なステップ数）とスペース（問題を解決するために必要なメモリ量）です。
このような分析では、時間を分析しなければならないコンピュータのモデルが必要です。典型的には、そのようなモデルはコンピュータが決定論的であると仮定している（コンピュータの現在の状態と何らかの入力が与えられると、コンピュータが取る可能性のある動作は1つだけである）およびシーケンシャル（19459017）シーケンシャルであると仮定する。他の後）。
この理論では、クラス P は多項式である時間の量で決定論的逐次マシンで解くことができるすべての決定問題から成ります。入力のサイズクラス NP は、正しい情報が与えられれば正の解が多項式時間で検証できる、またはそれと等価な非決定的機械の多項式時間で見つけることができる決定問題すべてから成ります。明らかに、 P ⊂NP 。理論的なコンピューター科学における最も大きな未解決の問題は、おそらくこれら2つのクラス間の関係に関するものです。
P NP に等しい？
2002年の100人の研究者の調査では、61人が答えがいいえ、9人が答えがはい、22と答えた。わからない。 8この質問は現在受け入れられている公理とは無関係であり、したがって証明または反証することは不可能である可能性があると考えていた。 [9]
10年後の2012年に、同じ世論調査が繰り返されました。回答した研究者の数は151人：126人（83％）がその答えはノーと答え、12人（9％）がその答えはイエスと答え、5人（3％）はその質問が現在受け入れられている公理と無関係であると信じた立証も立証も不可能、8人（5％）が、答えが「はい」であっても問題も解決されないようにするか知らないか、気にしないかのいずれかを言った。[10]
NP-completeness[ edit ] P 、、 NP、– 完了、および – 完全集合のオイラー図 （ P に属するが – 完全ではない）空の言語とその補数を除く
Pを攻撃するには = ] NP 問題、 NP – 完全性の概念は非常に有用です。 NP – 完全問題とは、他の問題を多項式時間で縮めることができる問題の集まりであり、その解は多項式時間で検証することができます。つまり、任意の NP 問題は、 NP – 完全問題のいずれかに変換できます。非公式には、 NP – 完全問題は、 NP の他の問題と少なくとも同じくらい「難しい」 NP問題です。
NP – 難しい問題は、少なくとも NP問題と同じくらい難しい問題です。すなわち、NP のすべての問題は、それらに対して（多項式時間で）減らすことができます。 。 NP – 厳しい問題は NPにある必要はないすなわち、それらは多項式時間で検証可能な解を持つ必要はない。
例えば、ブール充足可能性問題はクック・レヴィンの定理により NP完全であるため、 any any NPの問題は、多項式時間でブール充足可能性問題のインスタンスに機械的に変換できます。ブール充足可能性の問題は、このような完全な問題の1つです NP 。 NP – 完全な問題が P にある場合は、 P = NP となります。しかしながら、多くの重要な問題が NP 完全であることが示されており、それらのどれについても高速なアルゴリズムは知られていません。
定義だけでは、 NP – 完全な問題が存在することは明白ではありません。しかし、自明で考案された NP 完全問題は次のように定式化できます。多項式時間で停止することが保証されたチューリング機械の記述を考えると、多項式サイズは存在しますか M は受け付けますか？[11] NP にあります。 M が、 M をシミュレートして入力を受け付けるかどうかを確認するのは簡単だからです。 １９４５９０１６］ Ｍ ［１９４５９０１７］； Ｍ．これは NP の問題の特定のインスタンスに対する検証子を多項式時間マシンとしてエンコードできるため、 NP 完全です。 M 入力として検証されます。次に、インスタンスが「はい」または「いいえ」のインスタンスであるかどうかという問題は、有効な入力が存在するかどうかによって判断されます。
NP – 完全であることが証明された最初の自然問題は、SATとしても知られているブール充足可能性問題でした。上記のように、これはクック・レヴィンの定理です。充足可能性があるという証明 NP – 完全 NPの定義に関連しているため、完全なチューリング機械に関する技術的詳細が含まれています。しかし、この問題がNP 完全であることが証明された後、簡約証明は他の多くの問題も簡単であることを示す簡単な方法を提供しました。NP 。この場合、多項式時間での数独の解は多項式時間でのラテン方格の完成にも使用できることが証明されています[12] これにより、3部グラフを三角形に分割する問題に対する解決策が得られます。これは、3-SATとして知られているSATの特別な場合に対する解を見つけるために使用することができ、[14] は一般的なブール充足可能性に対する解を提供します。そのため、数独への多項式時間解は、一連の機械的変換により、充足可能性のある多項式時間解を導き出し、それを多項式時間における他の完全問題を解くために使用することができます。このような変換を使用すると、一見無関係な問題の膨大なクラスはすべて互いに縮約可能であり、ある意味では「同じ問題」です。
より困難な問題 編集
P = NP 、以外の問題 ]知られています。クラス P が多項式実行時間に関して定義されているように、クラス EXPTIME は、実行時間が指数関数であるすべての決定問題の集合です。言い換えれば、 EXPTIME のいかなる問題も、O（2 p （ n ））の決定論的チューリング機械によって解決可能です。 ] p （ n ）は、 n の多項式関数です。決定問題はそれが EXPTIME の中にあれば – 完全であり、 EXPTIME の中のすべての問題はそれに対する多項式多対数の縮約を持ちます。いくつかの問題がEXPTIME 完全であることが知られています。 P ≠ EXPTIME であることを示すことができるため、これらの問題はP の外側にあり、多項式時間以上の時間が必要です。実際、時間階層定理では、指数時間よりもはるかに短い時間で解くことはできません。例としては、 N N N ボード上のチェスポジションの完璧な戦略や、他のボードゲームのための同様の問題を見つけることが挙げられます。 [16]
Presburgerの算術演算で文の真理を決定する問題は、さらに時間がかかります。 FischerとRabinは、1974年に長さのPresburgerステートメントの真実を決定するすべてのアルゴリズム n
いくつかの定数に対して c 。したがって、この問題は指数関数的な実行時間以上の時間を必要とすることが知られています。さらに難しいのは、停止問題など、決定不可能な問題です。特定のアルゴリズムに対して、そのアルゴリズムで正しい答えが得られないような入力が少なくとも1つあるという意味で、それらはどのアルゴリズムでも完全には解決できません。それは間違った答えを生み出すか、決定的な答えを与えずに終わるか、さもなければ全く答えを生み出さずに永遠に走ります。
いくつかの定数に対して c 。したがって、この問題は指数関数的な実行時間以上の時間を必要とすることが知られています。さらに難しいのは、停止問題など、決定不可能な問題です。特定の決定問題以外の質問を検討することも可能です。問題を数えることからなるそのようなクラスの1つは #P と呼ばれています。一方、 NP 問題は「対応策はありますか？」という質問に対応する #P 問題「いくつの解決策がありますか？」と尋ねます。明らかに、 #P 問題は、対応する NP 問題と少なくとも同じくらい難しいものでなければなりません。ゼロ。驚くべきことに、難しいと考えられているいくつかの問題は簡単な問題に対応しています（例えば、線形時間） P これらの問題については、言うことは非常に簡単です。解決策が存在するかどうか、しかしどれだけ多くを見分けるのが非常に難しいと考えました。これらの問題の多くは #P – 完全であり、したがって #P で最も困難な問題の1つです。これらの問題に対する多項式時間解は他のすべての多項式時間解を可能にするからです。 #P 問題。
NPの問題がPまたはNP完全であることが知られていない ]
P ≠ NP NP にも NP – 完結にもない問題が存在する NP NP ] – 中間の問題グラフ同型性問題、離散対数問題および整数分解問題は、中間的問題であると考えられる問題の例である。それらは P または NP – 完全であることが知られていない非常に少数の NP 問題のいくつかです。
グラフ同型性問題は、2つの有限グラフが同型かどうかを判断する計算上の問題です。複雑性理論における重要な未解決問題は、グラフ同型性問題が P NP -complete、または NP 中間にあるかどうかです。答えは知られていませんが、問題は少なくとも NP – 完全ではないと考えられています – [4] NP – 完全であれば、多項式時間階層は次のように崩壊します。多項式の階層構造はどの有限レベルにも崩壊しないと広く信じられているので、グラフ同型性は完全ではないと考えられている NP 。 LászlóBabaiとEugene Luksによるこの問題に対する最良のアルゴリズムは、次のグラフに対して実行時間2 √[√ log n ）です。 n 頂点。
整数分解問題は、与えられた整数の素因数分解を決定する計算問題です。決定問題と言いますと、それは入力が k より小さい因数を持つかどうかを決定する問題です。効率的な整数因数分解アルゴリズムは知られていません、そしてこの事実はRSAアルゴリズムのようないくつかの現代の暗号システムの基礎を形成します。整数因数分解問題は NP と co-NP （そして UP と co-UP [22]）にもあります。問題がＮＰ ［１９４５９００７］ – 完全である場合、多項式時間階層はその第１のレベルに崩壊する（すなわち、［１９４５９００６］ ＮＰ ［１９４５９００７］ ＝ ［１９４５９００６］ ｃｏ − ＮＰ ［１９４５９００７］）。整数分解のための最もよく知られているアルゴリズムは、一般的な数体篩です。
n – ビット整数。ただし、この問題に対する最もよく知られている量子アルゴリズムであるShorのアルゴリズムは多項式時間で実行されますが、これは問題が非量子複雑性クラスに関してどこにあるのかを示すものではありません。
Pは「簡単」を意味しますか？ [ edit ]
グラフには、ナップザック問題の時間（933 MHz Pentium IIIを使用して平均100インスタンスms）が表示されます。最先端の特殊なアルゴリズムのために。二次近似は、50〜10,000の変数を持つインスタンスの経験的なアルゴリズムの複雑さはO（（log（ n ）） 2 ）であることを示唆しています。 P P は「易しい」を意味し、「not in 」は「難しい」を意味し、Cobhamの論文として知られている仮定です。これは複雑性理論における一般的かつ合理的に正確な仮定です。ただし、いくつか注意点があります。
第一に、実際には必ずしもそうではありません。理論的多項式アルゴリズムは極端に大きい定数係数または指数を持つことがあるため、実用的ではありません。一方、問題が NP – 完全であると示されたとしても、≠ NP であっても、取り組むための有効なアプローチがまだあるかもしれません。実際の問題です。ナップザック問題、巡回セールスマン問題、ブール充足可能性問題など、多くの NP 完全問題に対して、合理的な時間で多くの実世界のインスタンスを最適化するために解くことができるアルゴリズムがあります。そのようなアルゴリズムの経験的な平均的ケースの複雑さ（時間対問題サイズ）は驚くほど低い可能性があります。一例は、線形計画法のシンプレックスアルゴリズムであり、実際には驚くほどうまく機能します。指数関数的に最悪の場合の時間的複雑さを有するにもかかわらず、それは最もよく知られている多項式 – 時間アルゴリズムと同等に実行されます。 [24]
第二に、量子計算やランダム化されたアルゴリズムのような、 P と NPが定義されているチューリング機械モデルに適合しない種類の計算があります。
P≠NPと信じる理由
世論調査によると、[9][25] ほとんどのコンピュータ科学者は、 P ≠ NP と考えています。 ]。この信念の主な理由は、これらの問題を何十年も研究してきた後で、3000以上の重要な既知の問題のいずれに対しても多項式時間アルゴリズムを見つけることができなかったことです（のリストを参照）。 ] NP – 完全な問題）これらのアルゴリズムは、 NP – 完全性の概念が定義されるまでもなくずっと前に探求されていました（最初に見つかったKarpの21 NP – 完全問題は、当時よく知られている既存の問題です）。それらは NP – 完全であることが示された）。さらに、結果 P = NP は、 NP = のように、現在誤っていると考えられている他の多くの驚くべき結果を暗示します。 および P = PH 。
If P = NP
= もし、解決するのは難しいが解決策を検証するのは簡単である問題の存在は、現実の経験と一致すると直観的に議論されます。 、それから世界は私たちが通常それがあると仮定しているものとは全く異なる場所になるでしょう。 「創造的な飛躍」に特別な価値はなく、問題を解決してからその解決策を認識するまでの基本的なギャップもありません。
一方で、 P を信じることには自信過剰があると考えています。 ]≠ NP そして研究者はP = NP の証明も探求すべきである。例えば、2002年にこれらのことが述べられた。[9]
