マックス3SAT

MAX-3SAT は、コンピュータ サイエンスの計算複雑性のサブフィールドにおける問題です。これは、複雑性理論で考慮される決定問題であるブール充足可能性問題(SAT) を一般化したものです。次のように定義されます。

3-CNF式 Φ (つまり、節ごとに最大 3 つの変数)が与えられた場合、最大数の節を満たす割り当てを見つけます。

MAX-3SAT は、複雑性クラスMAXSNPの標準的な完全問題です(Papadimitriou の 314 ページに完全問題として示されています)。

MAX-3SATの決定バージョンはNP 完全です。したがって、多項式時間ソリューションはP = NPの場合にのみ達成できます。この単純なアルゴリズムでは、2 倍以内の近似値を達成できますが、次のようになります。

• すべての変数 = TRUE またはすべての変数 = FALSE の場合、ほとんどの節が満たされるソリューションを出力します。
• すべての節は 2 つのソリューションのいずれかによって満たされるため、1 つのソリューションは少なくとも半分の節を満たします。

Karloff -Zwickアルゴリズムは多項式時間で実行され、7/8以上の節を満たします。このアルゴリズムはランダム化されていますが、 ^[1]などの手法を使用して非ランダム化することができ、同じ近似保証を備えた決定論的（多項式時間）アルゴリズムが得られます。

PCP定理は、MAX-3SATの(1- ε )近似がNP困難となるようなε >0が存在することを意味します。

証拠：

PCP定理により、任意のNP完全問題⁠ ⁠ が${\displaystyle L\in {\mathsf {PCP}}(O(\log(n)),O(1))}$成り立つ。 x ∈ Lに対して、3-CNF式 Ψ _xが次のように構成される。

• x ∈ L ⇒ Ψ _{x は}満足可能である
• x ∉ L ⇒ Ψ _xの (1- ε ) m個以下の節が満たされる。

検証者V は必要なビットをすべて一度に読み取ります。つまり、非適応クエリを実行します。クエリの数が一定であるため、これは有効です。

• クエリの数をqとします。
• すべてのランダムな文字列R _i ∈ Vを列挙すると、各文字列の長さが であるため、poly( x ) 文字列が得られます。${\displaystyle r(x)=O(\log |x|)}$
• 各R _iについて
  • V はq個の位置i ₁ ,..., i _qとブール関数f _R : {0,1} ^q ->{0,1}を選択し、 f _R (π(i ₁ ,...,i _q ))の場合にのみ受け入れます。ここで、π は Oracle から取得した証明を指します。

次に、これをシミュレートするためのブール式を見つけようとします。ブール変数x ₁、...、x _{l を}導入します。ここで、l は証明の長さです。検証者が確率的 多項式時間で実行されることを示すには、満足可能な節の数と検証者が受け入れる確率との間の対応が必要です。

• すべてのRについて、2 ^{q 個の}SAT節を使用してf _R ( x _i1 ,..., x _{iq ) を表す節を追加します。長さ}qの節は、新しい (補助) 変数を追加することで長さ 3 に変換されます。たとえば、x ₂ ∨ x ₁₀ ∨ x ₁₁ ∨ x ₁₂ = ( x ₂ ∨ x ₁₀ ∨ y _R ) ∧ ( y _R ∨ x ₁₁ ∨ x ₁₂ ) などです。これには、最大q 2 ^q個の3-SAT節が必要です。
• z ∈ Lならば​
  • あらゆるR _{iに対して}V ^π ( z )が成立するという証明πが存在する。
  • x _i = π ( i ) であり、補助変数が正しく追加されている場合、すべての節が満たされます。
• 入力z∉Lの場合 ​
  • x ₁、...、x _lおよびy _Rへのすべての割り当てについて、対応する証明 π( i ) = x _iにより、検証者はすべてのR ∈ {0,1} ^{r (| z |)}の半分を拒否します。
    • 各Rについて、f _{R を}表す 1 つの節が失敗します。
    • したがって、一部の節は失敗します。${\displaystyle {\frac {1}{2}}{\frac {1}{q2^{q}}}}$

これがすべてのNP 完全問題に当てはまる場合、 PCP 定理は正しいと結論付けることができます。

Håstad ^[2]は定理1よりも厳密な結果、すなわちεの最もよく知られている値を示しています。

彼は、証明から 3 ビットだけを読み取る 3-SAT用の PCP 検証子を構築します。

すべてのε > 0に対して、長さ⁠ ⁠のランダムな文字列r を読み取り、証明π内のクエリ位置i _r、 j _r、 k _rとビットb _rを計算する3-SAT用の PCP 検証器 M が存在します。これは、 'π ( i _r ) ⊕ π ( j _r ) ⊕ π ( k _r ) = b _rの場合にのみ受け入れます。${\displaystyle O(\log(n))}$

検証器は完全性（1− ε）と健全性1/2 + ε （ PCP（複雑性）を参照）を有する。検証器は以下を満たす。

${\displaystyle z\in L\implies \exists \pi Pr[V^{\pi }(z)=1]\geq 1-\epsilon }$

${\displaystyle z\not \in L\implies \forall \pi Pr[V^{\pi }(z)=1]\leq {\frac {1}{2}}+\epsilon }$

これら 2 つの方程式の最初のものを通常どおり「=1」と等しくすると、 P = NPを意味する線形方程式のシステム ( MAX-3LIN-EQNを参照)を解くことによって π の証明を見つけることができます。

• z ∈ Lの場合、節の割合 ≥ (1 − ε ) が満たされます。
• z ∉ Lの場合、 Rの (1/2 − ε ) 分数に対して、1/4 の節が矛盾します。

これは近似比の難しさを証明するのに十分である。

${\displaystyle {\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '}$

MAX-3SAT(B) は、すべての変数が最大でB個の節に出現するMAX-3SATの制限された特殊なケースです。PCP定理が証明される前に、Papadimitriou と Yannakakis ^[3]は、ある固定定数Bに対してこの問題が MAX SNP 困難であることを示しました。したがって、PCP 定理では、APX 困難でもあります。これは、MAX-3SAT(B) を使用すると、MAX-3SAT では不可能な方法で PTAS 保存削減を得られることが多いため便利です。B の明示的な値の証明には、すべての B ≥ 13 [ 4 ] [ 5 ^]およびすべてのB ≥ 3 ^[6] (これが最良) が含まれます。

さらに、決定問題2SATは多項式時間で解けるが、MAX-2SAT (3)はAPX困難でもある。^[6]

MAX-3SAT(B)の最良の近似比は、Bの関数として、NP = RPでない限り、少なくとも で最大です^[7] 。Bの特定の値に対する近似定数の明示的な境界がいくつか知られています。^{[8] [9] [10] Berman、Karpinski、Scott は、各リテラルが正確に 2 回出現し、各節のサイズが正確に 3 である}MAX-3SATの「臨界」インスタンスの場合、問題は定数係数に対して近似困難であることを証明しました。^[11]${\displaystyle 7/8+\オメガ (1/B)}$${\displaystyle 7/8+O(1/{\sqrt {B}})}$

MAX-EkSAT は、 MAX-3SATのパラメーター化されたバージョンであり、各節にはk ≥ 3 のk個のリテラルが含まれます。これは、 符号理論のアイデアを使用して近似比で効率的に近似できます。 ${\displaystyle 1-(1/2)^{k}}$

MAX-3SATのランダムインスタンスは、係数⁠以内に近似できることが証明されています。8/9⁠ . ^[12]

カリフォルニア大学バークレー校の講義ノート バッファロー大学のコーディング理論ノート