1. 序章

コンピュータサイエンスには、いくつかの有名な未解決の問題があり、最も研究されている問題の1つです。 これまで、その問題に対する答えは主に「いいえ」です。 そして、これは学術界の大多数によって受け入れられています。 なぜこの問題がまだ解決されていないのか疑問に思うかもしれません。

このチュートリアルでは、この学術的な問題の詳細を説明します。  また、と問題の両方を示します。 次に、との定義も追加します。 そして最終的には、なぜまだ未解決の問題であるのかをよりよく理解できることを願っています。

2. 分類

、などを説明するために、実際の問題を分類するために使用するのと同じ考え方を使用してみましょう。 問題を分類するためにさまざまな用語を使用できますが、ほとんどの場合、「簡単から難しい」スケールを使用します。

現在、理論計算機科学のでは、一般的な問題定義の分類と複雑さには、「多項式」時間であると「非決定論的多項式」時間であるの2つの主要なセットがあります。 より洗練された問題を表現するために使用するセットもあります。 簡単から難しいまでの評価の場合、これらに「簡単」、「中」、「難しい」、そして最後に「最も難しい」というラベルを付けることができます。

  • 簡単
  • 中くらい
  • 難しい
  • 最も難しい

また、それらの関係を視覚化することもできます。

この図を使用して、とは同じセットではないと仮定します。つまり、。と仮定します。 これは明らかに真実ですが、まだ証明されていない主張です。 もちろん、この図のもう1つの興味深い側面は、との間にいくつかの重複があることです。 問題がこれらのセットの両方に属する場合に呼び出します。

さて、、を「簡単」、「中」、「難しい」、「最も難しい」にマッピングしましたが、各カテゴリに特定のアルゴリズムをどのように配置しますか？ そのためには、次のセクションでもう少し正式なものにする必要があります。

この記事の残りの部分では、通常、「秒」や「ミリ秒」などの単位は使用しないことをお勧めします。 代わりに、 Big-O表記を使用して、、、、、などの比例式を使用します。 これらの数式は、問題のアルゴリズムの複雑さについての手がかりを与えてくれます。

3. 問題の定義

いくつかの一般的なBig-O値を簡単に確認しましょう。

  • –定数時間
  • –対数時間
  • –線形時間
  • –二次時間
  • –多項式時間
  • –指数時間
  • –階乗時間

ここで、は定数で、は入力サイズです。 のサイズは、問題の定義によっても異なります。 たとえば、サイズが。の数値セットを使用すると、使用中のデータ構造に応じて、探索問題の線形時間と対数時間の平均的な複雑さが増します。

3.1. 多項式アルゴリズム

最初の一連の問題は、対数、線形、または2次時間などの多項式時間で解くことができる多項式アルゴリズムです。 アルゴリズムが多項式の場合、その時間計算量を正式に次のように定義できます。

ここで、ここで、およびは定数であり、は入力サイズです。 一般に、多項式時間アルゴリズムの場合、よりも小さいと予想されます。 多くのアルゴリズムは多項式時間で完了します。

前に説明したように、これらはすべて、一部の複雑さを持っており、その事実により、すべてがに配置されます。 もちろん、入力が1つだけであるとは限りません。 ただし、各入力が多項式である限り、それらを乗算しても多項式になります。 たとえば、グラフでは、エッジと頂点に使用します。これにより、ベルマンフォードの最短経路アルゴリズムが得られます。 エッジセットのサイズがである場合でも、時間計算量は多項式であるため、まだです。

アルゴリズムのBig-Oを常に特定できるとは限りません。 Big-O以外では、問題の説明について考えることができます。 たとえば、チェッカーのゲームを考えてみましょう。 特定のターンで最適な動きを決定することの複雑さは何ですか？ ボードのサイズをに制限すると、これはが多項式時間問題であると信じられ、。に配置されます。 しかし、それがボードだと言えば、はにはもうありません。 この場合、検索スペースをどのように制約するかは、検索スペースを配置する場所に影響します。 同様に、ハミルトン閉路問題には、一部のタイプの入力グラフに対してのみ多項式時間解があります。

または別の例は、安定したルームメイトの問題です。 ネクタイなしで一致するのは多項式時間ですが、ネクタイが許可されている場合や、夫婦のようなルームメイトの好みを含める場合はそうではありません。 （これらのバリアントは実際にはですが、これについては後で説明します。）考慮すべきさらに別の要因は、に対する相対的なサイズです。 入力サイズがに近い場合、アルゴリズムは指数関数のように動作します。

3.2. NPアルゴリズム

問題の2番目のセットは、多項式時間では解決できません。 ただし、多項式時間で検証（または認定）することができます。 これらのアルゴリズムには指数関数的な複雑さが予想されます。これを次のように定義します。ここで、およびここで、、は定数であり、は入力サイズです。 は、少なくともとの場合の指数時間の関数です。 その結果、が得られます。 たとえば、この一連の問題には、、などの複雑さが見られます。 この説明に適合するアルゴリズムがいくつかあります。 それらの中には：

これらは両方とも2つの重要な特性を持っています：それらの複雑さはいくつかのものであり、それらの結果は多項式時間で検証することができます。 これらの2つの事実は、それらすべてを、つまり「非決定論的多項式」アルゴリズムのセットに配置します。 さて、正式には、これらの問題は決定問題でなければならないと述べています-はいまたはいいえの答えがあります-実際には、すべての関数問題は決定問題に変換できることに注意してください。 この区別は、「検証済み」の意味を明確にするのに役立ちます。

正確に言えば、アルゴリズムは多項式時間で解けない場合にあり、決定問題の解のセットは「決定論的チューリングマシン」によって多項式時間で検証できます。 素因数分解とグラフ同型を興味深いものにしているのは、それらがにあると信じている間、それらがとにあるかどうかの証拠がないということです。 通常、すべてのアルゴリズムはに含まれていますが、問題と比較してより複雑になる別のプロパティがあります。

次のセクションでその違いを続けましょう。

3.3. NP完全アルゴリズム

次のセットは前のセットと非常によく似ています。 図を見ると、これらはすべてに属していますが、セットの中で最も難しいものの1つです。 現在、これらの問題は3000以上あり、理論計算機科学のコミュニティはすぐにリストに追加されます。 それらが他の問題と異なるのは、完全性と呼ばれる便利な区別です。 完全な問題には、問題を他の完全な問題に変換できる多項式時間アルゴリズムが存在します。 この変換要件は、削減とも呼ばれます。

すでに述べたように、完全であることが証明された多くの問題があります。 それらの中には：

不思議なことに、彼らが共通しているのは、にいることを除いて、それぞれが多項式時間で他に還元できるということです。 これらの事実は一緒にそれらをに配置します。 の主要かつ主要な作品はKarpに属しています。 そして彼の問題は、この理論計算機科学のトピックの基本です。 これらの作品はクック-レビンの定理に基づいており、充足可能性（SAT）問題が次のとおりであることを証明しています。

3.4. NP困難アルゴリズム

私たちの最後の一連の問題には、コンピュータサイエンスで最も困難で最も複雑な問題が含まれています。 それらは解決するのが難しいだけでなく、検証するのも難しいです。 実際、これらの問題のいくつかは決定可能でさえありません。 最も難しいコンピュータサイエンスの問題には、次のものがあります。

これらのアルゴリズムには、のアルゴリズムと同様のプロパティがあります。これらはすべて、の問題に還元できます。 そのため、これらはにあり、少なくとも他の問題と同じくらい難しいです。 問題はとの両方にある可能性があります。これは、の別の側面です。

この特徴は、巡回セールスマンが実際にそうであるかどうかについての議論につながりました。 と問題は多項式時間で検証できるので、アルゴリズムを多項式時間で検証できないことを証明することも、アルゴリズムをに配置するのに十分です。

4. では、 P = NP ですか？

多くのコンピューター科学者を魅了する質問は、すべてのアルゴリズムがに属するかどうかです。これは興味深い問題です。たとえば、任意の問題を多項式時間で解決できるということです。 これまでのところ、それがとらえどころのないことが証明されていることを証明しています。 この問題の陰謀のために、それはミレニアム賞問題の1つであり、賞金は$1,000,000です。

ただし、私たちの定義では、可能性があると想定しました。 もしそうなら、多項式時間で解ける問題は別として、の特定のアルゴリズムも劇的に単純化するでしょう。 たとえば、それらのベリファイアがまたはである場合、それらは多項式時間でも解ける必要があり、それらもに移動する必要があります。

これは、コンピュータサイエンス、さらには実際のシナリオにおける根本的な変化を意味すると結論付けることができます。 現在、一部のセキュリティアルゴリズムは、計算時間が長すぎるという要件に基づいています。 暗号化における多くの暗号化スキームとアルゴリズムは、指数関数的に複雑な最もよく知られているアルゴリズムである数値因数分解に基づいています。 多項式時間アルゴリズムが見つかった場合、これらのアルゴリズムは攻撃に対して脆弱になります。

5. 結論

この記事では、コンピュータサイエンスの有名な問題について紹介します。 この記事では、さまざまな問題セットに焦点を当てました; 、、、、および。 また、将来の研究とwhat-ifシナリオの良い出発点を提供しました。 読んだ後、簡単に次のように一般化された分類を結論付けることができます。

  • 問題はすぐに解決できます
  • 問題の検証は迅速ですが、解決には時間がかかります
  • 問題の検証も迅速で、解決も遅く、他の問題に減らすことができます
  • 問題の検証は遅く、解決も遅く、他の問題に減らすことができます

最後に、将来的に証拠があれば、人類はコンピュータ時代のセキュリティ面の新しい方法を構築する必要があります。 これが発生した場合、現在よりも新しい硬度レベルを特定するために、別の複雑さのレベルが必要です。