導入
複雑さPのアルゴリズムのクラスと複雑さNPのアルゴリズムのクラスの間の関係は、理論コンピューター科学における未解決の問題であり、多くの研究者によって、この分野、さらには数学においても最も重要な問題の 1 つであると考えられています。一般的な。そのため、数学的知識の開発と普及に専念しているクレイ数学研究所は、この問題をミレニアム賞の問題のリストに含めました。
この問題は、これら 2 つのクラスが同等であるかどうかが問題であるため、 P = NP問題と呼ばれることがよくあります。クラスPアルゴリズムは、処理される要素の数(たとえば、 T ( N ) = N 2 ) に応じて、処理時間が多項式によって増加する可能性があるアルゴリズムです。 NPクラス アルゴリズムは、結果が判明した後の検証に多項式時間を必要とするアルゴリズムです。
アルゴリズムの複雑性理論では、多項式の実行時間を必要とするアルゴリズムは (たとえば、指数関数的な実行時間と比較して) 「高速」であると考えられます。 P=NP の関係が証明された場合、問題の解決策が「迅速に」検証できる場合は、必然的に「迅速に」計算可能である必要があることを意味します。そうすれば、多くの重要なアルゴリズムを大幅に高速化できることがわかります。その影響は、暗号学、コンピュータサイエンス、数学、工学、経済学など、多くの分野で重大なものとなるでしょう。
P がNPに等しくないことが真実である場合、これは、いくつかの問題が決定的かつ根本的に合理的な時間内に計算の範囲を超えており、それらを強制的に raw で処理するより優れたアルゴリズムはないことを意味します。
P ≠ NP の意味
P ≠ NPであることが示された場合、これは、指数関数的な数の解の中から問題に対する最適な解を見つけるために、総当たり検索よりも優れた、またははるかに優れた方法を実行することが不可能な状況があることを意味します。
これは、問題の解決策を検証することよりも、問題の解決策を探すことの方が根本的に難しいことも意味します。
しかし、この状況にはデメリットがあるだけではありません。公開鍵暗号化と銀行のセキュリティは保証されますが、さらにそれ以上です。 P ≠ NPの場合、各 NP 問題 (P ではない) には、保証され実証された知識のゼロ開示証明があることが実証されており、これにより、それが優れたサービスになります。認証条件。
P ≠ NPの証明は、アルゴリズムの複雑さの理論の深化にもなるでしょう。それは間違いなく、特定の問題に対して総当たりよりも優れた処理を実行することがなぜ不可能なのかという疑問に答えを与えるでしょうし、すべてを改善するための道を提供するでしょう。 NP -Complete アルゴリズムの有効性 (もちろん、アルゴリズムを多項式にすることはありません) を検証し、暗号システムのセキュリティをより正式に実証します。
ただし、 Stephen Cook は、たとえP ≠ NPであっても、ほとんどの場合、多項式時間で NP-Complete 問題を解決するアルゴリズムが存在する可能性が依然としてあると指摘しています。そうすれば、P=NP 問題のより弱い形式を推測し、おそらく証明することが可能になります。問題は、次のようなNP完全問題を平均多項式時間で解くアルゴリズムが存在するかどうかを知ることになります。症例の合理的な分布。
