随机游动算法解决kSAT问题

input：n个变量的k-CNF公式

ouput：该公式的一组满足赋值或宣布没有满足赋值

算法步骤：

1. 随机均匀地初始化赋值 a ∈ { 0 , 1 } n a\in\{0,1\}^n a∈{0,1}n.
2. 重复t次（后面会估计这个t）：
   a. 如果在当前赋值下公式满足，则停止并输出满足赋值；
   b. 找到某个C是不可满足的子句；
   c. 显然C中不超过k个文字，随机选择其中一个，改变其赋值.

以上就是完整算法，很简洁且暴力。下面主要分析它的时间复杂度。

首先问题变量的状态空间是$2^n$的（每个变量取0或1），所以其穷举算法的时间为$O(2^n)$。而上述的随机游动算法可以将这个底数2优化为$c\in (1,2)$即时间复杂度为$O(c^n)$，因此我们称其为改进的指数时间算法。这对于kSAT这些npc问题是很好的优化了。下面我们找出这个c的表达式。

Part 1:

假设公式可满足，某个满足赋值为$x^{\ast }$，定义随机变量X为当前赋值$x$和$x^{\ast }$不同变量的个数，显然X服从二项分布B(n,0.5).当X=d时，将$x$变成$x^{\ast }$​需要改变赋值的变元个数为d.

赋值改变这个过程可以看成马尔科夫链，状态0,1，…，n表示$x$和$x^{\ast }$之间的汉明距离（i.e. 不同变量的个数）,算法步骤1的随机初始化就是从开始状态到状态d，转移概率为$C_n^j{2}^{-n}$.

算法步骤2.3中因为C是不可满足的子句，在C中的至多k个变量中，至少有一个的赋值和$x^{\ast }$不同，该操作从状态d到d-1的概率至少为$p=\frac{1}{k}$，到d+1的概率至多为$1-p=\frac{k-1}{k}$.至此我们得到了一个广义的Gambler’s ruin问题.

Part 2:

定义从状态d随机移动到状态0的概率为$P(d)$​，从Part 1的讨论中我们可以得到问题的转移方程：
$$P(d)=pP(d-1)+(1-p)P(d+1)$$
其中$P(0)=1$.（区别于赌徒破产问题，我们只有状态0这一个吸收态）虽然状态没有拓扑序，无法从初始状态直接递推，但注意到这是一个线性齐次递推式，我们可以通过解对应的特征方程$(1-p)r^2-r+p=0$构造通解。方程的两个根为$\frac{p}{1-p}$和$1$. 我们有：
$$P(n)=A{\left(\frac{p}{1-p}\right)}^n+B(1{)}^n=A{\left(\frac{p}{1-p}\right)}^n+B$$
代入$P(0)=1$有$A+B=1$，同时由于概率的非负性，$A<1$否则我们一定可以找到一个n使得$P(n)<0$，这样我们可以得到一个下界：
$$P(d)=A{\left(\frac{p}{1-p}\right)}^d+1-A\ge {\left(\frac{p}{1-p}\right)}^d$$
代入p得到$P(d)\ge (k-1{)}^{-d}$

Part 3：

所以当满足赋值为$x^{\ast }$存在时，我们通过随机游动找到它的概率为：
$$P^{\ast }\ge \sum _d^n{C}_n^d{2}^{-n}(k-1{)}^{-d}=2^{-n}{\left(1+\frac{1}{k-1}\right)}^n(二项式定理)$$
因此重复次数t的期望为$\frac{1}{P^{\ast }}$，算法的复杂性为
$$poly(n)\times \frac{1}{P^{\ast }}=poly(n)\times {\left(2\left(1-\frac{1}{k}\right)\right)}^n$$
以上，我们通过随机游动算法给出了kSAT的改进的指数时间的随机算法.

参考材料：

屈婉玲, 刘田, 张立昂, 王捍贫. 算法设计与分析习题解答与学习指导[M]. 第2版. 北京: 清华大学出版社, 2016.3. ISBN 9787302364924.