Application:A Randomized Algorithm for 2-SAT

2-SAT 问题定义与算法

• 2-SAT: 每个子句有且仅有两个文字
• 算法:
  • 初始化：随机对所有变量赋值
  • 重复以下操作$2mn^2$次, 如果所有子句都被满足则终止:
    (a) 任意选择一个未满足的子句
    (b) 随机选择子句中的一个变量并改变其值
  • 如果找到了一组满足表达式的赋值，返回该赋值
  • 否则返回该表达式无法被满足.
• $n$: 变量总数
• $m$: 与算法正确率有关的一个参数

复杂度分析

注：以下讨论均假设输入表达式是可以被满足的

符号与标记

• $S$:一个满足表达式的赋值
• $A_i$: 第$i$轮之后变量的取值
• $X_i$: 第$i$轮后$A_i$与$S$赋值相同的变量个数，$X_i=n$表明算法得到一组满足表达式的变量赋值并终止

算法复杂度分析

当$X_i=0$，无论改变哪个变量的值，都可以得出：$Pr(X_{i+1}=1|X_i=0)=1$

当$1\leq X_i\leq n-1$，在每一步中，我们选择一个未满足的语句（该语句中至少有一个变量的赋值与$S$不同），因为这个语句最多只有两个变量，所以至少有$1/2$的概率将匹配数提高$1$；如果$A_i$与$S$关于该语句两个变量的赋值都不一样，则有$1$的概率将匹配数提升$1$. 由此可知匹配数减少$1$的概率小于等于$1/2$. 于是得到以下关系式：

$$ \begin{aligned} Pr(X_{i+1}=j+1|X_i=j)\geq 1/2\\ Pr(X_{i+1}=j-1|X_i=j)\leq 1/2 \end{aligned} $$

注意到随机过程$X_0,X_1,X_2…$并不构成马尔科夫链：过去的行动会影响当前转移概率矩阵
但是可以考虑以下马尔科夫链：

$$ \begin{aligned} Y_O &=X_0\\ Pr(Y_{i+1}=1|Y_i=0) &=1\\ Pr(Y_{i+1}=j+1|Y_i=j) &= 1/2\\ Pr(Y_{i+1}=j-1|Y_i=j) &= 1/2 \end{aligned} $$

这个马尔可夫链$Y_0,Y_1,Y_2,…$实际上是$X_0,X_1,X_2,…$的消极情况. 显然，无论初始状态是什么，随机过程$Y$相比随机过程$X$都将要花费更多时间达到$Y_i=n$

为马尔可夫链$Y$构建图$G=(V,E)$,$0\sim n$为$G$中顶点，顶点$i$与顶点$i-1，i+1$分别有边连接
，用$h_j$表示从顶点$j$开始到达$n$的期望轮数.显然有$h_0=h_1+1,h_n=0$.
对于$1\leq j\leq n-1$，有

$$ h_j=\frac{h_{j-1}+1}{2}+\frac{h_{j+1}+1}{2}=\frac{h_{j-1}}{2}+\frac{h_{j+1}}{2}+1 $$

于是得到以下等式：

$$ \begin{aligned} h_0 &=h_1+1\\ h_j &=\frac{h_{j-1}+1}{2}+\frac{h_{j+1}+1}{2}=\frac{h_{j-1}}{2}+\frac{h_{j+1}}{2}+1\\ h_n &= 0 \end{aligned} $$

推导得到：

$$ h_j=h_{j+1}+2j+1 $$

因此得出结论：

$$ \begin{aligned} h_0&=h_1+1=h_2+1+3=...=n^2\\ h_j&=n^2-j^2 \end{aligned} $$

Lemma 1
假设2-SAT表达式可以被满足，那么该算法找到满足条件的赋值所需要的期望轮数小于等于$n^2$
Lemma 2
如果2-SAT表达式无法被满足，则算法总是返回正确结果. 如果表达式可以被满足，那么有至少$1-2^{-m}$的概率该算法返回一组可以满足表达式的变量赋值；在其他情况下，该算法返回错误结果，认为该表达式是无法被满足的
证明：
当该表达式可以被满足时，将算法运行的每$2n^2$轮分成一组。假设进行完前$i-1$没有得到满足该2-SAT表达式的解，用$Z$表示算法从第$i$组开始直到最终找到一个满足表达式的解所用的轮数，运用马尔可夫不等式可得

$$\begin{aligned} Pr(Z\gt 2n^2)&\leq\frac{n^2}{2n^2}=\frac{1}{2}\\ (Markov's inequality)\ \ Pr(X\geq a)&\leq \frac{E[X]}{a},\forall a\gt 0\end{aligned} $$

因此$m$组循环内无法找到可行解的概率小于等于$(1/2)^m$