k-SAT问题的随机算法
Table of Contents
算法 1(随机游走模型)
几天前上将向我安利了一下 \(2\) -SAT 的一个随机算法, 感觉非常有(玄)趣(学),后来在 google 上找到了一篇 UCSD 的 Lecture Notes: lec-15-0520.pdf, 提到了相关的一些东西.
\(2\) -SAT 的随机算法流程大致如下:
令 \(\phi(x)\) 为所给定的 CNF.
- 随机给每个变量 \(x_i\) 赋值 \(0\) 或 \(1\) .
- 如果 \(\phi(x)=1\) , 结束.
- 找到一个使得 \(\phi(x)=0\) 的 clause, 随机地 flip 其中一个变量, 转到 2.
简单地说就是瞎蒙一组解，然后不断根据错误的 clause 调整，看起来这个过程非常无脑，但实际上有着多项式级别的期望时间复杂度.
为了方便分析，假设这个 2-SAT 问题只有一组赋值 \(x^{*}\) 满足 \(\phi(x^{*})=0\) , 那么对于任意一赋值 \(x\) , 定义解的距离 \(dis(x)\) 为它到 \(x^{*}\) 的 Hamming 距离.
注意到每当一个 clause 为 0 时，其中必有一个变量的赋值与 \(x^{*}\) 中的不同，所以随机修改该 clause 中的一个值时, \(\Delta dis(x) = 1\) , 且 \(P(dis(x)=-1)\geq \frac{1}{2}\) , 这个问题规约到了在一个长度为 \(n\) 的链( \(n\) 为变量的数目)上的随机行走问题, 每步以大于 \(\frac{1}{2}\) 的概率向 \(0\) 的方向运动, 以小于 \(\frac{1}{2}\) 的概率向相反的方向运动.
o<—>1<—>2<—>3<—>4<—>…<—>(n-1)
令 \(E(k)\) 为一组赋值 \(x\) 的 \(dis(x)=k\) 时到达 \(dis(x)=0\) 所需要的期望操作数.
\[ E(n) = \frac{1}{2}E(n-1) + \frac{1}{2}E(n+1) + 1 \]
\(E(n)\) 的二阶差分为非零常数, 因此对于有 \(0\) 个变量的 2-SAT 的问题, 此算法在任意初始状态下, 期望操作步数为 \(O(n^2)\) . 如果 clause 数量为 \(m\) , 总的时间复杂度为 \(O(n^2m)\)（讲道理还是很大的).
不像基于 SCC 的算法, 这个算法一看就可以推广到 \(k\) -SAT 问题, 由于所有 \(k\) -SAT 都可以规约到 \(3\) -SAT, 所以先考虑此算法用于 \(3\) -SAT 问题的期望终止次数.
唯一的不同在于 \(P(dis(x)=-1)\geq \frac{1}{3}\) , 因此 \(E(k)\) 的递推式变成了:
\[ E(n)=\frac{1}{3}E(n-1)+\frac{2}{3}E(n+1)+1\]
它的解为 \(O({\frac{4}{3}}^n)\) , 仍然没有逃出指数级的范畴. 类似的, 可以计算出: 将此算法直接用于 \(k\) -SAT, 期望操作步数为 \(O(2^{n\left(1-O\left(\frac{1}{k}\right)\right)})\) .
补注
基于期望的分析不够严格(为什么在转移的概率不确定的条件下可以这样写递推式?), 更严谨的分析需要基于 Coupling(共用随机性)以及构造 Martingale(鞅), 或者计算链的 Covering time, 详见概率与计算第三次作业的第二题.
算法 2(编码压缩模型)
一通大师在他的第二节课上讲了两个优美的有一定限制条件的针对 \(k\) -SAT 问题的算法，它们都出自于 Robin Moser 的论文( Moser 2009, Moser-Tardos 2010 ) 1.
由 Lovász Local Lemma 得到对于一个有 \(n\) 个变量与 \(m\) 个 clauses, 最大度为 \(d\) (此处的 \(d\) 表示与一个 Clause 有公共变量 Clause 个数)的 \(k\) -CNF 问题, 如果 \(d\leq2^{k-2}\) , 则一定有可行解.
Moser 的结论是, 当 \(d<2^{k-3}\) 时, 存在一个期望时间复杂度为 \(O\left(n+km\log(m)\right)\) 的算法.
*Moser*提出的算法:
\(\textit{Solve}(\phi)\)
- Pick a random assignment \(x_1, x_2, \cdots, x_n\) .
- while \(\exists\) unsatisfied clause \(C\) , \(Fix(C)\) .
\(\textit{Fix}(C)\)
- replace all variables in \(C\) with random values.
- while \(\exists\) unsatisfied clause \(D\) overlapping with \(C\) , \(Fix(D)\) .
下面考虑这个算法的递归树, 由于顶层 \(\textit{Solve}\) 的存在, 整个算法执行过程中 \(\textit{Fix}\) 的节点构成一个森林, 每个 Clause 在根节点中最多出现一次, 因此 \(\# \textit{Trees} \leq m\) .
令 \(\# Nodes = t\) . 注意到, 每次我们调用 \(\textit{Fix}(C)\) 的时候, \(C\) 的赋值已经确定(必然是全 \(0\) ), 这就我们编码这棵递归树的时候就不需要记录子节点的编号了(假设算法每次都 fix 所有候选 \(D\) 中最小的那个, 那么可以根据它的赋值为 \(0\) 唯一确定它).
编码 1(正向)
第一种编码方式, 只记录初始的随机赋值和每次 fix 节点的赋值(根据上面的讨论, 这种编码可以唯一还原递归过程), 总的 bit 数为:
\[\# \textit{random bits} = n + tk \]
这是一个 mutually independent 的随机串.
编码 2(反向)
现在, 我们来反向编码这个随机串, 假设我们知道了最后的赋值, 如何还原这个过程?
最后的赋值需要 \(n\) bits, 由于是逆向过程, 每次我们只需要把一个 Clause 赋为全 \(0\) 即可(不需要记录该 Clause 取证的任何信息), 因此我们需要一个这个节点的编号.
所以我们的编码需要做到:
- 还原整个树的结构(包括左右兄弟信息).
- 确定每个节点的编号.
根节点可以使用 \(\log(m)\) 个 bits 来确定编号, 非根节点可以用它是父节点的第几个邻居也就是 \(\log(d)\) 个 bits 来编号, 剩下的问题是, 如何唯一地表示树的结构?
现在只考虑树的结构, 一棵树的 DFS 序(先序遍历)中相邻两个节点 \((v_i, v_{i+1})\) 的关系是:
- \(v_{i+1}\) 是 \(v_{i}\) 的子节点.
- \(v_{i+1}\) 是 \(v_{i}\) 的兄弟节点.
- \(v_{i+1}\) 是 \(v_{i}\) 的某个父亲的子节点.
这三种关系都可以归结为一种: \[v_{i+1} = \textit{f}(v_{i}, k_{i})\]
其中 \(f(v, k)\) 代表 \(v\) 的第 \(k\) ( \(k\) 可以为 \(0\) )代父节点的子节点, 有了 \(k_{i+1}\) 就可以根据当前构造的树 \(T_i\) 和 \(v_{i}\) 得出 \(v_{i+1}\) .
因此每个节点 \(v_i\) 的位置都可以用 \(\log(k_i + 1)\) 个 bits 来编码, 由此算出:
\[\frac{1}{t}\sum_{i=1}^{t}\log(k_i + 1) < \frac{1}{t}\sum_{i=1}^{t} k_i < \frac{1}{t}t = 1\]
因此均摊下来每个非根节点节点只需要多 \(1\) bit 记录位置信息.
因此这个编码的总长度 \(\leq n + m\log(m) + t\left(\log(d) + O(1)\right)\) , 这里是 \(O(1)\) 的原因是为了编码可逆还需要一些 \(bits\) 来对齐, 在 Morse 的论文中, 这个 \(O(1)\) 的值为 \(3\) .
不可压缩定理
编码 \(1\) 生成的是实打实的随机串, 由 Kolmogorov 的 Incompressibility Theorem , 以很高的概率我们有:
\[t(k-3-\log(d)) \leq m\log(m) + \log(n) \]
当 \(d<2^{k-3}\) 时, \(t\leq\frac{m\log(m) + \log(n)}{k-3-\log(d)}\) , 此时总的期望时间复杂度为:
\[n + tk = O(n + km\log(m)) \]
一通大师课上提到这个分析是基于算法会停止的假设下得出的, 但实际上两个编码在算法执行到任何一个阶段时都是 well-define 的, 因此分析并没有问题. 固定 \(t\) , 可以由 Incompressibility Theorem 算出此时算法仍然不终止的概率.
算法 3(LLL 的通用构造算法)
这个算法针对的不仅是 SAT 问题, 而是面向通用的CSP问题, 如果 Generalized Lovász Local Lemma 能说明它有解, 那么下面这个算法就可以将它采样出来.
先明确一些记号:
- 事件 \(A_i\) 表示 CSP 中 \(C_i\) 不被满足.
- \(\mathcal{A} = \{A_i\}\).
- \(\textit{vbl}(A)\) 表示 \(A\) 中涉及的变量集合.
- \(\Gamma(A)\) 表示所有 \(A\) 的邻域, 即 \(\left\{B\mid \textit{vbl}(A)\cap \textit{vbl}(B) \not= \emptyset\right\}\)
- \(\Gamma^{+}(A) = Gamma(A) \cup \{A\}\) .
这个算法来自 Moser-Tardos 2010 , 过程比刚刚的 \(\textit{Solver}\) 更简单:
\(\textit{Random Solver}\)
- Sample all \(X\in \mathcal{X}\).
- while \(\exists\) a non-violated bad event \(A\in\mathcal{A}\) : resample all \(X\in \textit{vbl}(A)\) .
Paper 中的结论是若能找到一组赋值 \(\alpha: \mathcal{A}\rightarrow [0,1)\) , 且满足 LLL 的条件 \(Pr[A] \leq \alpha_{A}\prod\limits_{B\in \Gamma(A)}\left(1-\alpha_{B}\right)\) , 则该算法的期望 resample 次数为: \(\sum\limits_{A\in\mathcal{A}}\frac{\alpha_{A}}{1-\alpha_{A}}\) .
没空填坑 = =
参考文献
- UCSD lecture
- 尹一通老师概率与计算课程的课件
Footnotes:
Moser 和 Tardos 两位作者由于相关工作的贡献于 2020 年获得哥德尔奖。