介绍:\(k-sat\)
\(k-sat\) 问题:
我们可以用 Conjunctive Normal Form(CNF) 来描述一个 \(k-sat\)问题:
\[\Phi=(x_1\vee x_2\vee \neg x_4)\wedge(\neg x_2\vee x_3 \vee x_4)\wedge\cdots \wedge(x_6\vee x_8\vee x_9)
\]
这里的例子是一个 \(3-sat\),这意味着每个条件有三个变量。如果我们能使 \(\Phi\) 等于 \(1\),那么它就是可满足的。否则,它就不成立。
我们都知道我们可以在 \(O(n+m)\) 内解决 \(2-sat\) 问题,其中 \(n\) 是布尔变量的数量,\(m\) 是条款的数量。
我们也知道一般的 \(k-sat (k\ge 3)\) 是 \(NP-hard\)。但让我们看看一些特殊情况,这些情况有简单的方法来解决。
不相交情况
如果没有一个变量出现在一个以上的子句中,那么我们可以满足所有单元的要求,这是非常简单的。
\(m<2^k\)
考虑一个条件能做什么。如果且仅当其中的所有变量都与目标值相反时,它将导致不好的结果。
因此,如果我们有 “条件 \(x\) 被违反”,这意味着 \(2^k\)的变量已经被确定。剩下的 \(2^{n-k}\) 个是自由的。所以,每个条件最多 Ban 掉 \(2^{n-k}\) 个答案。而如果 \(m<k\),则 \(m\) 个条件 Ban 掉的答案就不超过 \(m(2^{n-k})<2^k(2^{n-k})=2^n\) 种。所以在余下的答案中一定存在合法的。
概率法
我们设事件 \(A_i\) 为“条件 \(i\) 被违反”。而我们其实就是要求“所有条件都不被违反”,也就是事件 \(\bigwedge_{i\le m} \bar{A_i}\) 是否会发生。
我们知道,\(A_i\) 发生的概率是 \(2^{-k}\),也就是其中的任何条件都不被满足。那么 \(\bar {A_i}\) 发生的概率就是 \((1-2^{-k})\)。而
\[\Pr\left[\bigvee_{i\le n} A_i\right]+\Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]=1
\]
\[\Pr\left[\bigvee_{i\le n} A_i\right]\le \prod_{i\le n}\Pr\left[A_i\right]=m2^{-k}<1
\]
\[\Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]>0
\]
因此,我们想要的“所有条件都不被满足”在 \(m\le 2^k\) 的时候,发生概率是不为 \(0\) 的,也就是这种情况一定是存在的。
依赖性限制
我们假设每个条件至多和另外的 \(d\) 个条件有公共变量。
那么,如果 \(e(d+1)2^{-k}\le 1\) 或者 \(4d2^{-k}\le 1\) 一样可以导出当前的问题是有解的。支撑它的即是 Lovázs Local Lemma,即 Lovázs 局部引理。
存在性: Lovázs 局部引理
Lovázs 局部引理是在“单个坏事件发生概率小”且“每个坏事件和其他坏事件关联较少”的条件上对形如 \(\bigwedge_{i\le m} \bar{A_i}\) 的事件发生可能性进行分析。
独立关系和独立图
首先,由概率我们知道,我们称事件 \(A\) 和事件 \(B\) “独立”,则有 \(P(A|B)=P(A)\) 且 \(P(B|A)=P(B)\)。
而在 Lovázs 局部引理中,我们更关注“不独立”的事件。如果两个事件之间不独立,我们就在它们之间连一条边,称最终得到的图为“独立关系图”。而每个事件代表的点的所有邻居代表的事件和当前事件不独立。
称事件 \(A\) 的邻居集合为 \(\Gamma(A)\),Lovázs 局部引理即要求 \(|\Gamma(A)|\le d\)。
Lovázs 局部引理:非对称形式
考虑有 \(m\) 个事件 \(A_i\),每个事件有权值 \(\alpha_i\in[0,1)\),使得满足
\[\Pr\left[A_i\right]\le \alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)
\]
那么
\[\Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]\ge \prod_{i\le m}(1-\alpha_i)
\]
证明
首先,我们重复用若干次链式法则展开,
\[Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]=\prod_{i\le m}\Pr\left[\bar{A_i}|\bigwedge_{j<i}\bar{A_j}\right]=\prod_{i\le m}(1-\Pr\left[A_i|\bigwedge_{j<i}\bar{A_j}\right])
\]
然后,我们来证明对任意的 \(S\subseteq [m],i\notin S\), \(\Pr\left[A_i|\bigwedge_{j\in S}\bar{A_j}\right]\le \alpha_i\)。
假设 \(j<i\) 的所有条件 \(k\) 个中,有 \(l\) 个是 \(A_i\) 的邻居,剩下的 \(k-l\) 个不是。
如果 \(l=0\),那么答案是显然的,因为所有条件都和当前事件无关,则
\[\Pr\left[A_i|\bigwedge_{j\in S}\bar{A_j}\right]=\Pr\left[A_i\right]\le \alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)\le \alpha_i
\]
否则,强制这些条件是前 \(l\) 个,我们有
\[\Pr\left[A_i|\bigwedge_{j\in S}\bar{A_j}\right]=\dfrac{\Pr\left[A_i\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]}{\Pr\left[\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]}
\]
\[\Pr\left[A_i\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]\le \Pr\left[A_i|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]=\Pr\left[A_i\right]\le \alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)
\]
\[\Pr\left[\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]=\prod_{p\le l} \Pr\left[\bar{A_{j_p}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]=\prod_{p\le l} (1-\Pr\left[A_{j_p}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right])
\]
我们发现,其中的每个都是我们初始问题的形式,然而因为 \(l>0\),所以 \(k\) 变少了。又 \(k=0\) 条件显然成立,所以考虑归纳法,假设对任意更小的 \(k\) 都满足此引理,故有
\[\prod_{p\le l} (1-\Pr\left[A_{j_p}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right])\ge \prod_{p\le l}(1-\alpha_{j_p})
\]
因此:
\[\Pr\left[\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]\ge \prod_{p\le l}(1-\alpha_{j_p})=\prod_{j\in \Gamma(A_i)}(1-\alpha_j)
\]
\[\dfrac{\Pr\left[A_i\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]}{\Pr\left[\bar{A_{j_1}}\bar{A_{j_2}}\cdots \bar{A_{j_l}}|\bar{A_{j_{l+1}}}\cdots\bar{A_{j_k}}\right]}\le\dfrac{\alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)}{\prod_{j\in \Gamma(A_i)}(1-\alpha_j)}=\alpha_i
\]
因此得证 \(\Pr\left[A_i|\bigwedge_{j\in S}\bar{A_j}\right]\le \alpha_i\)。
因此
\[Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]=\prod_{i\le m}(1-\Pr\left[A_i|\bigwedge_{j<i}\bar{A_j}\right])\ge \prod_{i\le m}(1-\alpha_i)
\]
即得证 Lovázs Local Lemma (asymmetric case)。
Lovázs 局部引理:对称形式
考虑有 \(m\) 个坏事件 \(A_i\),\(\Pr[A_i]\le p\),\(|\Gamma(A_i)|\le d\)。那么只要满足 \(ep(d+1)\le 1\),则一定存在所有坏事件都不发生的情况。
证明
我们通过非对称形式导出对称形式。
首先,我们设 \(\alpha_i=\dfrac{1}{d+1}\)。
那么如果有
\[\alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)\ge \dfrac{1}{d+1}(1-\dfrac{1}{d+1})^d=\dfrac{1}{d+1}(\dfrac{d}{d+1})^d=\dfrac{1}{d+1}(1+\dfrac{1}{d})^{-d}\ge \dfrac{1}{e(d+1)}\ge p\ge \Pr[A_i]
\]
就满足了非对称形式的条件,然后
\[\Pr\left[\bigwedge_{i\le m} \bar{A_i}\right]\ge \prod_{i\le m}(1-\alpha_i)=(1-\dfrac{1}{d+1})^m>0
\]
所以,当 \(ep(d+1)\le 1\) 的时候,原问题一定有解。
或者,在 \(d\) 较小的时候,有更强的条件:
设 \(\alpha_i=\dfrac{1}{2d}\)
那么如果有
\[\alpha_i\prod_{j\in \Gamma(A_i)}(1-\alpha_j)\ge \dfrac{1}{2d}(1-\dfrac{1}{2d})^d=\dfrac{1}{2d}(\dfrac{2d-1}{2d})^d=\dfrac{1}{2d}(1+\dfrac{1}{2d-1})^{-d}\ge \dfrac{1}{4d}\ge p\ge \Pr[A_i]
\]
也就是,在 \(4pd\le 1\) 的时候,原问题一定有解。
算法: Moser-Tados
算法: Moser's Fix-it Algorithm