NJU TCS Workshop'25 | Lecture 1. Lovasz Local Lemma

Posted on Edited on

Abstract.

本文收录于 NJU 4th “计算理论之美” 暑期学校笔记。

引入

$k\text{-SAT}$ 问题可谓是计算机科学中最经典、最重要的问题之一，我们默认读者熟悉关于该问题的描述和相关术语。根据 Cook-Levin 定理，当 $k\geq 3$ 时有 $k\text{-SAT}\in \mathbf{NP}\text{-complete}$。因此现阶段，难以找到一种可高效判定的充分必要条件。但显然有如下一些有 $m$ 条子句的 $k$-合取范式可满足的充分条件：

  1. 若任意两子句没有重复变元，则该合取范式可满足。
  2. 若 $m < 2^k$，则该合取范式可满足。

断言 2 的证明是一个经典的概率方法证明。我们给每个文字独立均匀随机赋值为真、假，对于 $i = 1, 2, …, m$，定义“坏事件” $A_i$ 为子句 $C_i$ 不被满足。则根据 union bound：

$$
\Pr\left[\bigvee_{i=1}^m A_i\right] \leq m2^{-k} < 1 \quad \Rightarrow \quad \Pr\left[\bigwedge_{i=1}^m \overline{A_i}\right] > 0
$$

这蕴含存在一组赋值满足了全部的子句。

注意，在上述证明中我们使用了 union bound。然而熟知 union bound 在事件比较独立之时是松的。是否有一种更为细致、更为局部的 union bound？

原始定理陈述和证明

Lovasz Local Lemma 是一种更局部的 union bound 类似物。

定理 2.1（Lovasz Local Lemma）. 令 $A_1, …, A_m$ 是 $m$ 个“坏事件”，满足对于任意的 $i$，$\Pr[A_i] \leq p$，且每个 $A_i$ 与除至多 $d$ 个 $A_j$ 外的其余坏事件都独立。那么，若 $ep(d + 1)\leq 1$，则存在一个样本使得这 $m$ 个事件都不发生，即

$$
ep(d + 1)\leq 1 \quad \Rightarrow \quad \Pr\left[\bigwedge_{i=1}^m \overline{A_i}\right] > 0
$$

事实上，上述陈述还是不够局部。因为这里的 $p, d$ 都是全局的信息。我们称 $\Gamma(A_i)$ 为和 $A_i$ 相关的集合的下标（即 $A_i$ 和 $A_j, \forall j\notin \Gamma(A_i)$ 都独立），并定义 $\Gamma^+(A_i) = \Gamma(A_i)\cup \{A_i\}$。形象地，你可以想象一张无向图，其点集为 $\{ A_1, …, A_m \}$，边集为 $\{(u, v) : v \in \Gamma(u)\}$，称作相关性图。一种更强的版本为：

定理 2.2（Asymmetric Lovasz Local Lemma）. 令 $A_1, …, A_m$ 是 $m$ 个“坏事件”。若存在 $\alpha_1, …, \alpha_m\in [0, 1)$，满足对于任意的 $i$ 都有

$$
\Pr[A_i] \leq \alpha_i\prod_{A_j\in \Gamma(A_i)} (1 - \alpha_j) \label{ALLLcondition}
$$

则有

$$
\Pr\left[\bigwedge_{i=1}^m \overline{A_i}\right] \geq \prod_{i=1}^m (1 - \alpha_i) > 0
$$

Remark. 易见定理 2.2 蕴含定理 2.1。只需取 $\alpha_i = \frac{1}{d + 1}$ 然后用 $e$ 的定义即可得证。

证明. 首先根据链式法则有

$$
\Pr\left[\bigwedge_{i=1}^m \overline{A_{i}}\right] = \prod_{i=1}^m\left(1 - \Pr\left[A_i \bigg| \bigwedge_{j=1}^{i - 1}\overline{A}_{j}\right]\right)
$$

现在来放缩这个条件概率。令 $S\subseteq \{1, 2, …, m\}$。我们证明对于任意的 $S$ 都有

$$
\Pr\left[A_i \bigg| \bigwedge_{j\in S}\overline{A}_{j}\right]\leq \alpha_i
$$

为此，施归纳于 $S$ 之大小，当 $|S| = 0$ 时结论显然成立。当 $S = \{j_1, …, j_m\}$，其中 $m > 0$ 时，有

$$
\begin{aligned}
\Pr\left[A_i \bigg| \bigwedge_{k=1}^{i - 1}\overline{A}_{j_k}\right] &= \frac{\Pr\left[ A_{i}\wedge \left(\wedge_{k\in \Gamma(A_i)} \overline{A_k}\right) | \wedge_{k\in S\setminus \Gamma(A_i) }\overline{A_k}\right]}{\Pr[\wedge_{k\in \Gamma(A_i)} \overline{A_k} | \wedge_{k\in S\setminus \Gamma(A_i)} \overline{A_k}]} \\
&\leq \frac{\Pr\left[A_i | \wedge_{k\in S\setminus \Gamma(A_i) }\overline{A_k}\right]}{\Pr[\wedge_{k\in \Gamma(A_i)} \overline{A_k} | \wedge_{k\in S\setminus \Gamma(A_i)} \overline{A_k}]}
\end{aligned}
$$

分子就是 $\Pr[A_i]$，继续用链式法则拆开分母后由归纳假设和条件 $(\ref{ALLLcondition})$ 立即得证。$\blacksquare$

这样一来我们证明了 SAT 有解的一个充分条件：

推论 2.3. 对于任意的 $k$-合取范式 $\phi$，若每个变量至多在 $2^{k - 2} / k$ 个子句中出现，则 $\phi$ 可满足。

证明. 套用定理 2.1 即可。$\blacksquare$

Moser-Tardos 算法

在判定之外，我们还希望搜索一组解。然而这里的判定算法是一个充分条件，所以直接用 decide-search 规约似乎是不可行的。所幸对于满足 LLL 条件的坏时间，存在搜索样本高效算法。本节我们将在一个具体的样本空间——独立变量上的 CSP 问题中探索如何搜索一组解。

定义 3.1（变量框架下的 LLL）. 给定以下资料：

  • 相互独立的变量集合 $\mathcal{X} := \{X_1, …, X_n\} \in [q]^n$；
  • 一系列坏事件 $\mathcal{A} := \{A_1, …, A_m\}$，约束某些变量不能同时取某些值。其中每个 $A_i$ 涉及的变量集合记作 $\textsf{vbl}(A_i)\subseteq \mathcal{X}$，$A_i$ 可以被集合 $[q]^{\textsf{vbl}(A_i)}$ 刻画：若 $\textsf{vbl}(A_i)$ 的取值落在其中，坏事件发生；
  • 相关性图 $\Gamma(A_i) := \{ A_j \ne A_i : \textsf{vbl}(A_j) \cap \textsf{vbl}(A_i)\ne \varnothing \}$。

目标：高效求解一个变量的赋值，使得所有坏事件都不发生。

求解该问题的算法出奇地简单：

算法 3.1（Moser-Tardos）.
输入. 一个由 $\mathcal{X}, \mathcal{A}$ 刻画的 CSP 问题。
输出. 一组满足该 CSP 的解。

  1. 为每个 $\mathcal{X}$ 中的变量随机赋值；
  2. while 存在某个 $A_i$ 发生：
  3. $\qquad$ 重新采样 $\textsf{vbl}(A_i)$。
  4. 返回当前赋值。

现在来分析该算法。我们将证明：

定理 3.1（Algorithmic Lovasz Local Lemma）. 若条件 $\ref{ALLLcondition}$ 成立，则 Moser-Tardos 算法的期望重采样次数为

$$
\sum_{i=1}^m \frac{\alpha_i}{1 - \alpha_i}
$$

Remark 1. 这个算法是非常高效的。在对称的情况下，这个数是 $m / d$。

Remark 2. 注意算法假设了 $X_i$ 的采样器和判断 $A_i$ 发生的高效算法存在。这很可能是 non-trivial 的。

方便起见，首先提取出整个算法的随机性：

定义 3.2（Moser-Tardos 算法的重采样表）. Moser-Tardos 算法的重采样表是一个写在 $n$ 条只可单向阅读的纸带上的随机表格：

$$
\begin{aligned}
X_1 &: X_1^{(1)}, X_1^{(2)}, … \\
\vdots & \\
X_n &: X_n^{(1)}, X_n^{(2)}, …
\end{aligned}
$$

表示重采样使用的随机变量。每次重采样 $A_i$，便将 $\textsf{vbl}(A_i)$ 的读写头右移一位。

然后将算法期望的重采样轮数和每个 $A_i$ 联系起来：

定义 3.3（Moser-Tardos 算法的运行日志）. Moser-Tardos 算法的运行日志是系指随机变量序列 $\Lambda\in \mathcal{A}^*$，表示算法运行过程中重采样的坏事件。

我们要放缩的无非是

$$
\mathbb{E}\left[\text{$\#$ of $A_i$ in $\Lambda$}\right]
$$

那么，每个 $A_i$ 出现在某个位置上的因果关系可以用一颗树刻画（一定是前面某个与之相关的重采样打乱了这个约束，它才会不被满足）：

定义 3.4（Moser-Tardos 算法的 witness tree）. 根据运行日志 $\Lambda$，可以构造一棵儿子有顺序的有根树 $T(\Lambda, t)$ 表示前 $t$ 个时刻的重采样的因果关系。树中每个节点 $u$ 都被标记为一个事件 $A_{[u]}$。构造方法如下：

  1. 初始时，树中仅包含一个标记为 $\Lambda_t$ 的根；
  2. for $i = t - 1, t - 2, …, t$
  3. $\qquad$ if 存在 $u\in T$ 使得 $\Gamma_i \in \Gamma^+(A_{[u]})$；
  4. $\qquad \qquad$ 在最深、最左边的满足条件的 $u$ 下面挂一个标记为 $\Lambda_i$ 的儿子。

记 $\mathcal{T}(A_i)$ 为全体可能的以 $A_i$ 为根的 witness tree 的集合。

引理 3.2. 对于任意的 $\Lambda$ 和 $s < t$，都有 $T(\Lambda, s) \ne T(\Lambda, t)$。

证明. 分类讨论。若 $\Lambda_s\ne \Lambda_t$，则树根不同。否则显然 $T(\Lambda, t)$ 更大。$\blacksquare$

因此，计数的组合对象可以改为 witness tree：

$$
\mathbb{E}\left[\text{$\#$ of $A_i$ in $\Lambda$}\right] = \sum_{\tau \in \mathcal{T}(A_i)} {\color{red} \Pr_{\Lambda}\left[\exists t, T(\Lambda, t) = \tau\right]}
$$

现在只需要放缩红色概率的上界。

引理 3.3. 对于任意的 $\tau$，有

$$
\Pr_{\Lambda}\left[\exists t, T(\Lambda, t) = \tau\right] \leq \prod_{u\in \tau} \Pr[A_{[u]}]
$$

证明. 这其实很显然。因为如果 $T(\Lambda, t) = \tau$，那么“$\tau$ 中的每个节点被重采样时一定没被满足”（记作事件 $S(\tau, \Lambda)$），而且我们已经将算法使用的随机性提取到了重采样表中，我们要求每次重采样必须使用崭新的随机比特，所以对于固定的 $\Lambda$，“$\tau$ 中的节点 $u$ 重采样时没被满足”相互独立，概率为 $\Pr[A_{[u]}]$。这推出

$$
\Pr[S(\tau, \Lambda)] = \prod_{u\in \tau} \Pr[A_{[u]}]
$$

而显然事件 $\exists t, T(\Lambda, t) = \tau$ 蕴含事件 $S(\tau, \Lambda)$，明所欲证。$\blacksquare$

继续推进证明。现在

$$
\begin{aligned}
\mathbb{E}\left[\text{$\#$ of $A_i$ in $\Lambda$}\right] &= \sum_{\tau \in \mathcal{T}(A_i)} { \Pr_{\Lambda}\left[\exists t, T(\Lambda, t) = \tau\right]} \\
{\color{blue}\text{(Lemma 3.3)}} &\leq \sum_{\tau \in \mathcal{T}(A_i)} \prod_{u\in \tau} \Pr[A_{[u]}] \\
{\color{blue}\text{(LLL Condition)}} &\leq \sum_{\tau \in \mathcal{T}(A_i)}{\color{red}\prod_{u\in \tau} \alpha_u \prod_{j\in \Gamma(A_{[u]})} (1 - \alpha_j)}
\end{aligned}
$$

我们现在建立一些关于红色部分的直觉。

引理 3.4. 考虑一个定义在相关性图上的分支过程：

  1. 初始时，队列中只有一个节点 $A_i$。
  2. 每一时刻，对于每个队列中的节点 $u$，对于 $i\in \Gamma(u)$，独立以概率 $a_i$ 在其下方挂上儿子 $i$ 后 $u$ 出队。
  3. 将所有新增的儿子加入队列，重复上方过程。

则

  1. 该过程能生成一切 $T\in \mathcal{T}(A_i)$。
  2. 该过程生成 $\tau$ 的概率恰为
    $$
    \frac{1 - \alpha_i}{\alpha_i}\prod_{u\in \tau} \alpha_u \prod_{j\in \Gamma(A_{[u]})} (1 - \alpha_j)
    $$

证明. 断言 1 显然。断言 2 只需在树上仔细计算即可。$\blacksquare$

因为上述分支过程产生一个良定义的概率分布，$\mathcal{T}(A_i)$ 是其支撑集的一个子集，所以

$$
\sum_{\tau \in \mathcal{T}(A_i)}\frac{1 - \alpha_i}{\alpha_i}\prod_{u\in \tau} \alpha_u \prod_{j\in \Gamma(A_{[u]})} (1 - \alpha_j) \leq 1
$$

这表明

$$
\mathbb{E}\left[\text{$\#$ of $A_i$ in $\Lambda$}\right] \leq \frac{\alpha_i}{1 - \alpha_i}
$$

至此，定理 3.1 得证！

Moser 算法及其信息论证明

Moser 算法是 Moser-Tardos 在 $k\text{-SAT}$ 上的变种。为便于分析，我们对寻找坏事件的方法稍作修改。

算法 4.1（Moser）. 输入. 一个 $k$-CNF $\phi$，满足推论 2.3 的条件。
输出. 一组满足其的赋值。

  1. 均匀随机为每个变量赋值 True / False
  2. while 存在 $C_i$ 未被满足：
  3. $\qquad$ $\mathrm{Fix}(C_i)$；

$\mathrm{Fix}(C_i)$ 定义如下：

  1. 重采样 $C_i$；
  2. while 存在 $j\in \Gamma^+(C_i)$，$C_j$ 未被满足：
  3. $\qquad$ $\mathrm{Fix}(C_j)$。

现在来分析此算法高概率的重采样次数上界。我们的核心直觉是：

  1. 随机串是不可压缩的（Kolmogrov）。
  2. 若重采样次数过多，则会用很多随机比特。而可以通过输出少量的信息来还原这些随机比特。

定理 4.1（Kolmogrov 不可压缩准则）. 设 $X\in \{0, 1\}^n$。对于任意的 $f : \{0, 1\}^n \rightarrow \{0, 1\}^*$ 都有

$$
\Pr[|f(X)| \leq n - l] \leq 2^{1 - l}
$$

证明. 直接数。$\blacksquare$

以此推进算法 4.1 的分析。注意每次重采样的子句 $C_i$ 都是不被满足的，因此 $\textsf{vbl}(C_i)$ 中的变量取值唯一，进而可以知道使用的随机比特的值。接下来顺次注意到：

  1. 每个 $C_i$ 在 Moser 算法顶层至多被 Fix 一次。
  2. 通过输出第一次采样使用的比特、顶层进入 Fix 函数时的下标和 Fix 递归时进入了第几个儿子，可以指导一个 decoder 通过这些输出还原出使用的随机比特序列。
  3. 若进行了 $t$ 次重采样：
    • 使用的随机比特总量为 $n + tk$；
    • 用于指导 decoder 的字符串长度为 $n + m\log m + t\log kd$。
  4. 回忆 $\log kd \leq k - 2$。

若重采样的次数超过 $t_0 = m\log m + \log n$ 时，有我们将一个长度为 $n + t_0k$ 的随机字符串压缩成了一个长度为 $n + m\log m + t_0\log kd$ 的字符串，其概率不超过

$$
2^{m\log m + t_0\log kd - t_0k} \leq 2^{-\log n} = 1/n
$$

因此算法重采样次数高概率不超过 $m\log m + \log n$。