Sen(Qian)’s Memo

前回📄(講義ノート)乱択アルゴリズム第4回 もDNFについてアルゴリズムを考えたが、今回もDNFについて別のアルゴリズムを考えて、解析をする。

まず、変数が$\mathbf{x} = (x_1, \cdots, x_n)$である。

そして、関数全体を

1. 節は$x_1 \land \cdots \land x_i$のようにする。このようにANDでつなげる。
2. 節全体をORつまり$\lor$でつなげる。

充足可能性の判定自体は線形時間でできるが、解が何個存在するのか？

#P困難である。

なお、節の中身がORで、節全体をつなげるのがANDの場合はCNF=連言標準形であり、それの充足可能性はSATである。

解の個数を$S(\phi)$とする。このとき、多項式関数$f$が存在し、

の時間で動作し、その出力は高確率(1/2より高ければよい)で$S(\phi)$の$1 \pm \epsilon$近似である。

ここで$n, m$を出したのはDNFの解の個数の推定をやりたいから。

$O(n m^2/\epsilon ^ 2)$のアルゴリズムである。

• $S_i$は$i$番目の節を充足する解の集合
• 推定したいのは$A = |\bigcup_{i=1}^m S_i |$である。ORなのでいずれかの$S_i$に入れば解である。
• $|S_i| = 2^{n - l_i}$。$l_i$は$S_i$のリテラルの個数。
  • 全体で$n$個の変数がある中で、$i$番目の節を充足するのは、節の中の$l_i$の変数からなる1通りの配置だけ。その節の外はどうなろうが問題ないので、任意に配置していい。
• $B = \sum_{i=1}^m |S_i|$は単純に加算すればいいので簡単である。

ここで、$A / B \in[0, 1]$を推定することを考える。

https://users.soe.ucsc.edu/~sesh/Teaching/2020/CSE290A/Slides/Lecture4.pdf

for j in [1, t]: 
		節iを確率|Si|/Bで選ぶ。(ここで重点サンプリング)
		節iを充足する解xを選ぶ。(節に含まれない変数は一様にランダムに決める)
		あるkがあって、k < iでxが節kをみたすのならばX_j=0
		それ以外ならばX_j=1

(sum(X, [1, t]))/tがA/Bの推定値

そして、前回ではこれは$O(nm / \epsilon^2)$に計算量を落とせるという改良もあるというわけだった。

今回は、別のアルゴリズムを考える。

$C(x)$を