Application:A Randomized Algorithm for 3-SAT

基础版算法

3-SAT 算法（基础版）:
1. 初始化：对变量随机赋值.
2. 将以下过程重复m次，如果所有子句都被满足则停止：
    (a) 选择任意一个未被满足的子句
    (b) 随机选择子句中的一个变量并改变其值
3. 如果找到了一组满足表达式的赋值，返回该赋值
4. 否则返回该表达式无法被满足.

• 标记与符号同2-SAT算法
• 注意到这个基础班3-SAT算法与2-SAT算法高度类似，但是众所周知3-SAT是NP-hard，所以这个算法的时间复杂度是指数级而非多项式

算法复杂度分析

分析方法与2-SAT问题类似，以下部分保留关键步骤：

• 假设输入表达式是可以被满足的，当$1\leq j\leq n-1$时，有
  $$ \begin{aligned} Pr(X_{i+1}=j+1|X_i=j)\geq 1/3 \\ Pr(X_{i+1}=j-1|X_i=j)\leq 2/3 \end{aligned} $$
• 将以上约束条件转化为马尔科夫链（消极化处理）
  $$\begin{aligned} Pr(Y_{i+1}=1|Y_i=0) &=1\\ Pr(Y_{i+1}=j+1|Y_i=j) &=1/3\\ Pr(Y_{i+1}=j-1|Y_i=j) &=2/3 \end{aligned} $$
• 得到递推关系式：
  $$ h_j=2^{n+2}-2^{j+2}-3(n-j) $$
• 所以这个算法的平均时间复杂度是$\Theta(2^n)$

寻求改进

观察基础版算法不难有以下两个发现：

• 因为初始化时我们对变量随机进行赋值，所以$A_0$与$S$赋值匹配的变量个数服从二项分布. 初始化后$A_0$与$S$赋值匹配的变量个数显著多于$n/2$虽然是指数级小概率事件，但不应该被忽视
• 当算法开始运行，$A_i$与$S$的匹配数倾向于向0移动而非向n移动. 这说明在完成初始化赋值后，算法运行轮次越多，我们获得正确结果的概率越小. 一个更好的解决方式是进行多次初始化赋值，并减少每次初始化后循环次数

基于以上事实，可以提出改进版3-SAT算法

改进版算法

3-SAT 算法（改进版）:
1. 重复以下过程m次，如果所有子句都被满足则终止：
    (a) 初始化：对变量随机进行赋值
    (b) 重复以下过程3n次，如果所有子句都被满足则终止：
        i. 随机选择一个未被满足的子句
        ii.随机选择子句中的一个变量并改变其值
3. 如果找到了一组满足表达式的赋值，返回该赋值
4. 否则返回该表达式无法被满足.

算法复杂度分析

首先定义两个符号：

• $q$: 初始化后在$3n$轮之内达到$S$(或其他满足表达式的赋值)的概率
• $q_j$: 初始化$A_0$恰好有$j$个变量与$S$赋值不同时，在$3n$轮之内达到$S$的概率下限

在每一步中，有$1/3$的概率匹配数加1，有$2/3$的概率匹配数减1. 所以可以用

$$ {j+2k\choose k}\Big(\frac{2}3{}\Big)^k\Big(\frac{1}{3}\Big)^{j+k} $$

表示通过$k$轮减少，$j+k$轮增加达到$n$的概率.
因此得到关于$q_j$的表达式：

$$ \begin{aligned} q_j \geq \max_{\substack{k=0, \dots, j \\ j+2k\leq 3n}}{j+2k \choose k}\Big(\frac{2}{3}\Big)^k\Big(\frac{1}{3}\Big)^{j+k} \end{aligned} $$

如果选取$k=j$，则可以得到$q_j$的一个下限：

$$ q_j \geq {3j \choose j}\Big(\frac{2}{3}\Big)^j\Big(\frac{1}{3}\Big)^{2j} $$

接下来的讨论需要用到Stirling’s Formula.

• $(Stirling’s\ Formula)\ For\ m>0,\ m!=\sqrt{2\pi m}\Big(\frac{m}{e}\Big)^m(1\pm o(1))$

• 特别地，对于$m>0$，有$\sqrt{2\pi m}\Big(\frac{m}{e}\Big)^m\leq m!\leq 2\sqrt{2\pi m}\Big(\frac{m}{e}\Big)^m$

  (Stirling’s Formula证明感兴趣的可以看一下)

因此，当$j>0$，

$$\begin{aligned} {3j\choose j} &=\frac{(3j)!}{j!(2j)!}\\ &\geq\frac{\sqrt{2\pi(3j)}}{4\sqrt{2\pi j}\sqrt{2\pi(2j)}}\Big(\frac{3j}{e}\Big)^{3j}\Big(\frac{e}{2j}\Big)^{2j}\Big(\frac{e}{j}\Big)^j\\ &=\frac{\sqrt{3}}{8\sqrt{\pi j}}\Big(\frac{27}{4}\Big)^j \\&=\frac{c}{\sqrt{j}}\Big(\frac{27}{4}\Big)^j,\ 取\ c=\frac{\sqrt{3}}{8\sqrt{\pi}} \end{aligned} $$

所以在$j>0$时，可以得到

$$\begin{aligned} q_j &\geq{3j \choose j}\Big(\frac{2}{3}\Big)^j\Big(\frac{1}{3}\Big)^{2j} \\&\geq\frac{c}{\sqrt{j}}\Big(\frac{27}{4}\Big)^{j}\Big(\frac{2}{3}\Big)^{j}\Big(\frac{1}{3}\Big)^{2j}\\ &\geq \frac{c}{\sqrt{j}}\frac{1}{2^j} \end{aligned} $$

同时，$q_0=0$

现在我们可以得到$q$的下限

$$\begin{aligned} q &\geq\sum_{j=0}^nPr(a\ random\ assignment\ has\ j\ mismatches\ with\ S)\cdot q_j\\ &\geq \frac{1}{2^n}+\sum_{j=1}^n{n\choose j}\Big(\frac{1}{2}\Big)^n\frac{c}{\sqrt{j}}\frac{1}{2^j}\\ &\geq \frac{c}{\sqrt{n}}\Big(\frac{1}{2}\Big)^n\sum_{j=0}^{n}{n\choose j}\Big(\frac{1}{2}\Big)^j(1)^{n-j}\\ &=\frac{c}{\sqrt{n}}\Big(\frac{1}{2}\Big)^n\Big(\frac{3}{2}\Big)^n \\&=\frac{c}{\sqrt{n}}\Big(\frac{3}{4}\Big)^n \end{aligned} $$

假设3-SAT表达式存在一组满足条件的变量赋值，在找到这组变量赋值前，算法尝试的随机变量赋值次数满足几何分布. 所以赋值次数的数学期望为$1/q$. 而在每组随机赋值中，算法最多循环$3n$次，所以得到算法的平均时间复杂度$O(n^{3/2}(4/3)^n)$.

• Remark：注意这里是bounded by，而不是exactly！并且这里并没有用$m$来控制外循环次数，只是单纯在讨论算法平均时间复杂度的上限