3 SAT - Summer498 の頭ん中

3 SAT

CNF-SAT の全ての節が高々 3 リテラルを持つよう制限したもの

ホントは他の SAT の制限と同様に 3 という条件を分離したいが、1文字しか無いので 3 SAT で一塊

3(スリー): 全ての節が高々 3 リテラルを持つ

解の相転移現象

ランダム生成した 3SAT において、節数$ mと変数の個数$ nの比$ \frac{m}{n}が$ 4.26になるのを境に解の存在確率と難易度が劇的に変化するらしい

$ nを固定したとき、$ mが小さいと殆どの問題が SAT に、$ mが大きいと殆どの問題が UnSAT になる

境界付近で DPLL の呼び出し回数が劇的に増える = 劇的に難しくなる

小さな$ nでは、やや大きい$ \frac{m}{n}で相転移する

4. 2 ランダム k-SAT と相転移

$ 4.26={213}/{50}

$ 4.26\approx{85}/{20}

$ 4.26\approx{71}/{17}

$ 4.26\approx{30}/{7}

$ 4.26\approx{17}/{4}

$ 4.26=3.15+1.11\approx\pi+\frac19

何の意味があるのかは謎。特に意味はなさそう

3 ORを使って1-in-3 SATに帰着すると$ 1個の節から$ 3個の節に、$ 3個の変数から$ 7個の変数に増える

$ \frac{m}{n}\to\frac{3m}{\frac{7}{3}n}=\frac{9}{7}\frac{m}{n}

$ \frac{9}{7}\cdot\frac{m}{n}=\frac{9}{7}\cdot4.26=5.48

3 ORを使って正1-in-3 SATに帰着すると$ 1個の節から$ 5個の節に、$ 3個の変数から$ 7個の変数に増える

$ \frac{m}{n}\to\frac{5m}{\frac{7}{3}n}=\frac{15}{7}\frac{m}{n}

$ \frac{15}{7}\cdot\frac{m}{n}=\frac{15}{7}\cdot4.26=9.13

きれいな数字になるかと思ったが特にそうはならないっぽい

3 SAT への帰着

任意の 2 項演算子を CNF に帰着できる(充足可能性保存変換)

任意の CNF は 3 CNF に帰着できる

$ (a+b+c+d+e)\overset{\rm SAT}=(a+b+x)(\overline x+c+y)(\overline y+d+e)