1. 概要

ブール充足可能性問題、つまりSATは、NP-Completeであることが示された最初の問題です。 このチュートリアルでは、充足可能性問題について詳しく説明し、クック-レビンの定理を示します。

さらに、 3-SAT問題について説明し、SAT問題に還元することでNP完全であることを証明する方法を示します。

2. SAT入門

このセクションでは、SAT問題の一般的な定義について説明します。

式がtrueである変数に真の代入が存在するかどうかを判断する、与えられたブール式は、充足可能性問題として定義されます。

さらに議論するために例を見てみましょう。

ここでは2つの表現を取りました。 変数への真の代入が存在するかどうかをテストするために、、、、すべての可能な代入をテストしました。

上記の式には満足のいく真理の割り当てがあるため、充足可能です。

しかし、式はすべての可能な真理の割り当てに対して false であるため、不満足です。

これには時間がかかります。 これは、真理値表メソッドと呼ばれます。 ブール式に変数がある場合、真理値表メソッドは、式trueを作成する真理値代入があるかどうかを判断するのに時間がかかります。

3. 連言標準形（CNF）

SATの問題について話し合うときは、連言標準形（CNF）について知ることが不可欠です。 このセクションでは、CNFの概念について簡単に説明します。

ブール式は、各句がリテラルの論理和（論理和）として定義されている一連の句の接続詞である場合、CNF形式であると言われます。 リテラルを変数または変数の否定として定義できます。 上記の例では、すべてリテラルです。

すべてのブール式は、ドモルガンの法則、二重否定の法則、およびANDとORの下での分配法則を繰り返し使用することにより、CNFとして表現できます。

   

どこ、

   

上記のCNFは-CNFです。つまり、すべての句に最大のリテラルがあります。 変数のセットから各リテラルを選択します。

   

4. SATバリアント

SATのバリエーションはたくさんあります。 このセクションでは、いくつかをリストアップしました。

4.1. 2-SAT

2-SAT問題では、すべての節に2つのリテラルがあり、多項式時間問題で解くことができます。

変数を選択して、trueを割り当てることができます。 trueを。を使用してすべての句の他の変数に割り当てます。 これらの条項が満たされている場合は、またはを持たない残りの条項を選択して、プロセスを続行します。

一方、この時点での句がすべて満たされていない場合は、 false を割り当てて、上記のプロセスを繰り返します。 およびを含むすべての条項がすべて満たされていない場合、2-SATは満たされません。

2-SATの重要なアプリケーションは、完全な2部グラフおよび独立集合として表すことができる無向グラフを識別することです。 これは、インターネットの自律サブシステム間のビジネス関係を特定するのに役立ちます。

自動ラベル配置問題の多くのアルゴリズムは、2-SATの概念を使用しています。

4.2. 加重2-SAT

句ごとのリテラルと整数を持つCNFが与えられた場合、CNFが満たされるtrueに設定された最大の変数で真理代入があるかどうかを判断する問題。

この問題はNP完全です。 多くのアルゴリズムは、頂点被覆問題を解決するために重み付けされた2-SATの概念を使用します。

4.3. 3-SAT

3-SAT問題では、各句には多くてもリテラルが含まれます。 この問題はNP完全です。

3-SAT問題は、Karpの21のNP完全問題の一部であり、他の問題もNP完全であることを証明するための開始点として使用されます。 一例は、独立集合問題です。 独立集合問題は、3-SATが独立集合問題に多項式的に還元可能であることを示すことにより、NP完全であることを示すことができます。

4.4. 正確に1つの3-SAT

3-SAT問題の各句には、少なくともtrueでなければならないリテラルがあります。 しかし、正確に1つの3-SAT問題では、すべての句の3つのリテラルの1つが true で、他の2つが false である場合、CNFが充足可能かどうかを判断します。 この問題はNP完全です。

正確に1つの3-SATは既知のNP完全問題であり、他の問題をNP完全であることを証明するために削減に使用されます。

5. クックの定理-レビンの定理

このセクションでは、SATがNP完全問題であることを証明する方法を示すクックの定理について説明します。

クックの定理のステートメントは、ブール充足可能性問題がNP完全であるというものです。

与えられた真理の代入に対して、CNFまたはブール式が多項式時間で充足可能かどうかを検証できます。

決定問題が決定論的チューリングマシンによって多項式時間で検証できる場合、非決定論的アルゴリズムによって多項式時間で解決できます。 この声明の証拠は、複数の教科書にあります。

多項式時間でそれを解くことができる非決定性チューリングマシンがある場合、SATはNPにあります。

NPの問題を多項式時間でSAT問題に還元できる場合、それはNP完全です。任意の言語を取り、多項式時間でSATに還元することで証明できます。 なぜなら、多項式時間で決定問題を検証できる検証器が存在するからです。

ベリファイアが出力がyesまたはnoまたは（または）であるかどうかをチェックする入力とします。 多項式時間で動作するため、すべてのタイムステップで、アルゴリズムはハードウェアに一定数のメモリユニットに影響を与えます。

タイムステップの後、アルゴリズムはメモリユニットに影響を与えます。 AND、OR、NOT論理ゲートを使用して、すべてのタイムステップでこれらの各操作を表すことができます。 したがって、任意の言語の多項式で回路を構築することが可能です。 これは、入力に存在するビット数の多項式時間になります。

決定問題は、上記で構築された回路が出力する入力があるかどうかを決定することになります（ true ）。 AND、OR、およびNOTゲートに相当するCNFを以下に示します。 この削減は、ド・モルガンの法則、重要な含意、および二重否定を使用して行われます。

ANDゲートから始めましょう。 、を入力、を出力とします。

CNF形式の上記のANDゲートの機能は次のとおりです。

   

   

   

   

ORゲートの場合、を入力、出力を次のようにします。

CNF形式の上記のORゲートの機能は次のとおりです。

   

   

   

   

NOTゲートの場合、入力を出力とします。

CNF形式の上記のNOTゲートの機能は次のとおりです。

   

   

   

上記のゲートから、回路を同等のCNF形式に変換できることがわかります。

したがって、すべての NP困難問題をCNFに減らすことができます。つまり、SAT問題に減らすことができます。 したがって、SATはNP完全です。

6. 3-SATの概要

3-SATは、各句に最大でリテラルが含まれている特定のCNFが充足可能かどうかを判断する問題を定義します。

3-SAT問題は、ブール式の各括弧に最大3つの変数が存在する可能性がある2-SAT問題を解決しようとするため、2-SATよりも単純です。 それでも、3-SATには多項式時間アルゴリズムは存在しません。

例を見てみましょう。 SAT問題を取り上げて、3-SATにします。

SAT問題の例を取り上げます。

   

真理値に充足可能です：、、、、、、、、

与えられたSAT問題を3-SAT問題にするために、2つの新しい変数を導入できます。

   

真理値、、、、、、、、、、で充足可能です。 実際、とのどちらの値でも、3-CNFは充足可能です。

7. NP-3SATの完全性

このセクションでは、3-SATがNP完全であることを証明する方法を見てみましょう。

あらゆる問題を多項式時間でSAT問題に変換できます。 つまり、ブール式として表現でき、すべてのブール式を対応するCNF形式に変換できます。

SATから3-SATへの削減には多項式時間がかかります。 つまり、対応するCNFから3-CNFには多項式時間がかかります。 元のSAT問題のCNF表現を次のようにします。

   

すべての節が充足可能である場合、充足可能です。

一般性を失うことなく、句にリテラル以上のものがあると仮定しましょう。

   

ここで、それぞれはリテラルのセットから選択されます。

   

させて

   

   

次のように定義します。

   

ここで、は新しい変数であり、リテラルを使用して句を作成するためにそれを導入します。 この同じ手順を、3つを超えるリテラルが残っている句がなくなるまで、の2番目の句に繰り返し適用できます。

今、私たちはそれを証明する必要があり、そして同等である。

ケース1の場合、充足可能であり、次に充足可能であることを示す必要があります。 この証明を始めましょう：

充足可能であり、次に充足可能である

   

もしも

   

   

(1)  

もしも

   

(2)  

のいずれかの値について、満足できるようにするために、またはのいずれか。 （ 1 ）と（ 2 ）から、。

充足可能であれば、充足可能です。

またはの場合、次の理由で割り当てることができます。

   

との一方または両方がです。

の場合、。 を割り当てることで、満足できるものにすることができます。

上記の手順を使用すると、リテラルの数が、最大で等満足可能な変数を持つ句に変換できる数よりも多くなります。 上記の証明から、これにはすべての句のリテラル数で多項式時間がかかることがわかります。

したがって、多項式時間でSATを3-SATに減らすことができます。 クックの定理から、SATはNP完全です。 したがって、3-SATもNP完全です。

8. 結論

このチュートリアルでは、SAT問題の詳細な説明を示しました。 SATがNP完全問題であることを示すために、クックの定理について説明しました。

さらに、3-SAT問題について簡単に紹介し、SATが3-SATに減少することを示しました。