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^{?}$，定義隨機變量X為當前賦值$x$和$x^{?}$不同變量的個數，顯然X服從二項分布B(n,0.5).當X=d時，將$x$變成$x^{?}$?需要改變賦值的變元個數為d.

賦值改變這個過程可以看成馬爾科夫鏈，狀態0,1，…，n表示$x$和$x^{?}$之間的漢明距離（i.e. 不同變量的個數）,算法步驟1的隨機初始化就是從開始狀態到狀態d，轉移概率為$C_n^j{2}^{?n}$.

算法步驟2.3中因為C是不可滿足的子句，在C中的至多k個變量中，至少有一個的賦值和$x^{?}$不同，該操作從狀態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^{?}$存在時，我們通過隨機游動找到它的概率為：
$$P^{?}\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^{?}}$，算法的復雜性為
$$poly(n)\times \frac{1}{P^{?}}=poly(n)\times {\left(2\left(1?\frac{1}{k}\right)\right)}^n$$
以上，我們通過隨機游動算法給出了kSAT的改進的指數時間的隨機算法.

參考材料：

屈婉玲, 劉田, 張立昂, 王捍貧. 算法設計與分析習題解答與學習指導[M]. 第2版. 北京: 清華大學出版社, 2016.3. ISBN 9787302364924.