1. 序章

かどうかの問題の証拠はまだありません。 答えは「いいえ」である可能性があります。

このチュートリアルでは、を想定して、問題の完全性を証明する方法を学習します。 また、実際のアルゴリズムの問題を取り上げて、それらが-Completeであることを証明します。

最後に、 Big-O 表記を使用して、時間計算量を記述します。

2. NP困難およびNP完全問題

決定問題–「はい」または「いいえ」の答えがある問題を分類しましょう。

2.1. PとNP

問題は、多項式時間で解決できる場合、クラスに属します。

同様に、問題が非決定論的多項式時間で解ける場合、問題はクラスに属します。 直感的には、この一連の問題は「難しい」問題と見なされます。 技術的には、多項式時間でそれらを解くことはできません。 ただし、それらの「実行時間」は多項式である可能性があります。

2.2. 割引

問題から問題への還元は、問題の入力から問題の入力への変換です。この変換は、多項式時間アルゴリズム自体です。 複雑さは入力の長さによって異なります。

決定問題の入力を分類してみましょう。 「はい」–問題の入力は、「はい」と答えたものです。 同様に、「いいえ」–問題への入力は、「いいえ」の答えがあるものです。

その場合、すべての「はい」–の入力は「はい」–の入力に変換されます。 そして、すべての「いいえ」-の入力は「いいえ」に変換されます-削減アルゴリズムを使用した入力。 ただし、別の方法として、入力なしで作業する代わりに、すべての「はい」（入力）が「はい」（入力）に変換されることを証明することもできます。 この記事の後半で、独自の削減アルゴリズムを実装します。

知っておくべき重要なことですが、多項式の縮小は推移的な関係です。 つまり、問題がアルゴリズムで減少し、問題がアルゴリズムで減少する場合、問題はアルゴリズムで減少します。 これは、問題への入力に最初にアルゴリズムを適用することで実現できます。 次に、問題への入力を取得し、アルゴリズムを適用してそれらの入力を問題への入力に変換できます。

2.3. NP困難

問題は-多項式からのすべての問題がそれに還元される場合は難しい。 -難しい問題は、少なくとも他の問題と同じくらい難しく、さらに難しいかもしれません。 ただし、-Hard問題はに属している場合と属していない場合があります。

2.4. NP完全性

問題は-に属している場合は-Completeであり、多項式からのすべての問題はそれに還元されます。

お気づきかもしれませんが、すべての-Complete問題は-Hardです。 しかし、すべての-Hard問題が-Completeであるとは限りません。 -Hardの例は、-Complete問題ではなく、 HaltingProblemです。 この問題は難しいですが、に属していません。 ブール充足可能性（SAT）は、-Completeであることが証明された最初の問題です。 クックの定理について読んでいるときに、3SAT問題の定義を見つけることもできます。

3. 問題がNP完全であることを証明するアルゴリズム

-完全な問題とは、-ハードの両方にある問題です。

したがって、問題が-Completeであることを証明するには、問題が次のことを示す必要があります。

  1. 属する
  2. は難しい

3.1. 問題を示す方法はNPですか？

問題がに属していることを示す証明書検証戦略があります。 証明書は私たちの問題に対する答えです。 Verifierは、問題の答えが「はい」か「いいえ」かを判断できる多項式アルゴリズムです。

たとえば、ハミルトン閉路問題を考えてみましょう。 問題の証明書は、ハミルトン閉路トラバーサルの順序の頂点である可能性があります。 このサイクルが線形時間でハミルトニアンであるかどうかを確認できます。 これを検証と呼びます。 したがって、問題はに属します。 さらに、この問題を3SATに減らすことにより、ハミルトン閉路が-Completeであることを証明できます。

3.2. 問題を示す方法NP困難ですか？

問題が-Hardであることを示すには、別の-Hard問題を選択し、選択した問題を自分たちのものに減らす必要があります。 重要なのは、すべての-Hard問題は-Completeです。 したがって、-Completeの問題を減らすこともできます。

多項式縮小の関係は推移的であることを忘れないでください。 したがって、のすべての問題ではなく、1つの問題だけを減らすことができます。

3.3. 証明戦略

問題が-Completeであることを証明するために達成する必要がある主な目標は次のとおりです。

前述のように、まず、問題がクラスにあることを証明する必要があります。 それを証明できなければ、それ以上進むことはできません。 -完全な問題は常にに属します。

証明書を選択するときは、多項式の長さである必要があります。 したがって、問題への入力がであるが、証明書の長さがである場合、この証明書を検証することはできません。 検証アルゴリズムは、証明書の長さに基づいて多項式の時間計算量を持っている必要があります。

問題がにあることを確認した後、問題が-Hardであることを証明する必要があります。 -Completeクラスの問題は、と-Hardの共通部分です。 どんな-難しい問題でも、多項式からのすべての問題がそれに還元されることを私たちは知っています。

また、削減アルゴリズムは、選択した-Hardまたは-Complete問題の「Yes」-および「No」-入力を、問題の同等の「Yes」-および「No」-入力に変換する必要があることも覚えておく必要があります。

問題が-Completeであることを証明する2つの例を見てみましょう。 3SATを4SATおよび独立集合の問題に減らします。

4. 3SATから4SATへの削減

4SAT問題の定義は次のとおりです。

「節で構成されるブール式を考えると、各節は4つのリテラルまたはそれらの否定の論理和です。  すべての条項が満たされるような変数の解釈はありますか？」

4.1. 4SATの証明書検証

まず、問題がに属していることを証明しましょう。 数式に入力変数があるとします。これは、回答と証明書が変数の解釈であることを意味します。これらはtrueまたはfalseに設定されている可能性があります。 さらに、式が線形時間で満たされているかどうかを確認できます。 その結果、多項式時間で証明書を検証します。 したがって、問題はにあります。

4.2. 3SATから4SATへの削減

次に、4SATが-Hardであることを証明する必要があります。 -Completeである3SATを取得し、3SATを4SATに減らします。

削減ガジェットは、3SATの入力を4SATの入力に変換するアルゴリズムになります。

入力3SAT式が与えられた場合、新しい変数で各句を展開することにより、4SATの入力式を作成します。

多項式時間でそれができることは明らかです。 ここで、「はい」（3SATの入力）が「はい」（4SATの入力）に変換されていること、またはその逆に変換されていることを確認しましょう。

与えられた節が満たされる場合、それは満たされます。 変数は、trueまたはfalseのいずれかです。 したがって、が充足可能である場合、充足可能です。

満足しているとしましょう。 変数の充足可能な解釈を。 各変数の割り当てで構成されます。  次に、。変数の下の true であり、異なる値を持っている必要があります。 変数がtrueの場合、 false であり、その逆も同様です。 したがって、trueの下にもある必要があります。 したがって、充足可能です。

その結果、3SATの入力を4SATの入力に変換する多項式アルゴリズムを作成しました。 これは、4SATが-Hardであることを意味します。

最後に、4SATがハードであることが証明されました。 したがって、4SATは-Completeであると言えます。

5. 3SATから独立集合の削減

グラフ理論では、独立集合は、グラフ内のサイズの頂点のセットを見つける問題であり、その2つは隣接していません。

5.1. 独立集合の証明書検証

この問題がに属することを証明しましょう。 問題の証明書は、選択された頂点のセットである可能性があります。 2つが隣接しているかどうかを、多項式時間で確認できます。 したがって、問題はにあります。

5.2. 3SATの独立集合への削減

次の句で構成される3SAT入力式があるとします。

グラフを作成して、3SATを独立集合に減らしましょう。グラフを作成すると、指定された数式が満たされた場合にのみ、サイズの独立集合が作成されます。これを行うには、各句に対して、三角形のグラフを作成します。変数とその否定で構成される頂点のすべてのペアにエッジを追加します。

与えられた式が満たされる場合、各節の少なくとも1つの変数はtrueです。 そのようなtrue変数のセットであるとします。 式は句で構成されます。 したがって、はのサイズであり、構築されたグラフ内の対応する頂点のセットは独立しており、サイズは。です。

次に、グラフに独立したサイズのセットがある場合、各「節の三角形」から1つのノードがあることがわかります。 選択した変数をtrueに設定できます。 これが可能なのは、2つが互いに否定でなく、ブール式が満たされるためです。

独立集合の問題があり、-Hardであることはすでに証明されています。 したがって、独立集合は-Completeであると言えます。

6. 結論

このチュートリアルでは、複雑性の理論の最も重要な定義を学びました。 また、証明書の検証と削減戦略を使用して、問題の完全性を証明する方法を学びました。 さらに、-完全性の証明の2つの例を示しました。