高级算法之Lovász Local Lemma

Posted on

Lovász Local Lemma

CSP见上一个笔记末尾.

k-SAT问题: 给定一个$k-CNF$公式$\phi$, 判定是否可满足
CNF:

  • $n$个布尔变量: $x_1,\cdots,x_n\in\{\text{true, false}\}$
  • $m$个从句: $C_1\land C_2\land\cdots\land C_m$.
  • 每个从句形式为$C_i=l_{i_1}\lor l_{i_2}\lor \cdots\lor l_{i_{k_i}}$
  • 每个字符$l_{i_j}\in \{x_s,\neg x_s\}$, $s\in\{1,2,\cdots, n\}$
  • k-CNF: 每个从句恰好$k$个变量
  • 度$d$: 每个从句和$\le d$个从句相交(分享变量).
  • 相变: 对于随机$k$-CNF, 其中从句数量为$m=\alpha n$, 随机CSP的满足性存在相变现象, 即$\alpha$超过某个值时, 可行解突然消失.

The Lovász Sieve

  • k-SAT的Lovász Local Lemma:
    如果$d\le 2^{k-2}$, 则$\phi$一定是可满足的.
    • 可以通过概率法证明, 详见组合数学之LLL.

一般情况:

  • $m$个坏事件$A_1,\cdots,A_m$, 每个$A_i$和除了$\le d$ 个坏事件以外的事件独立. 目标证明$\Pr[\land_{i=1}^m\overline{A_i}]>0$
  • 可以用union bound或者容斥原理
  • LLL:
    • $\forall i: \Pr[A_i]\le \frac{1}{4d}$则$\Pr[\land_{i=1}^m\overline{A_i}]>0$.
    • $\forall i: \Pr[A_i]\le \frac{1}{e(d+1)}$则$\Pr[\land_{i=1}^m\overline{A_i}]>0$.
    • 非对称版本: 存在$a_1,\cdots,a_m\in [0,1)$, $\forall i:\Pr[A_i]\le a_i\prod_{j\sim i}(1-a_j)$, 则$\Pr[\land_{i=1}^m\overline{A_i}]>\prod_{i=1}^m (1-a_i).$

Algorithmic LLL

k-SAT的算法LLL
存在$c>0$, 如果$d\le 2^{k-c}$, 则满足限制的赋值大概率(w.h.p)可以再$O(n+km)$时间内找到.

Moser’s Algorithm

输入: $\phi:$一个度为$d$的k-CNF, $m$从句, $n$变量

函数$Solve(\phi)$:

  • 随机采样一个均匀赋值$X_1,\cdots,X_n$
  • while 存在不满足的从句$C$:
    • $Fix(C)$
      子函数$Fix(C)$:
  • 重随机$C$中的变量
  • while 存在和$C$相交的(包含$C$自己)不满足的从句$D$
    • $Fix(D)$

分析:

  • 一旦结束, 一定返回满足解
  • 最外层(Solve函数中): 一旦$Fix(C)$返回后, 在Solve函数中看, $C$一直被满足.
  • Solve中每次调用$Fix(C)$的过程可以看做一个递归树, 递归树的总数$\le m$, 所有树中总共$T$个结点
  • $T$: $Fix(C)$的总调用次数
  • 总复杂度: $n+kT$(按照总的随机数比特数来计算时间复杂度.)
  • 根据最终的赋值和所有的递归树, 可以完全复原$n+kT$个随机比特
  • 而根据$n+kT$个随机比特, 也可以编码所有的递归树和最终的赋值.
  • 最终的赋值: $n$ bits
  • 如果寻找不满足的从句的时候是按照字典序的, 那么所有的递归树: $m+T(\log_2 d+O(1))$ bits(每棵树的根结点要$1$比特, 只要存有没有在最外层函数中被Fix过就行, 树中每个结点$O(1)$比特记录栈操作以还原树的结构, $\log_2 d$比特记录结点身份(因为一个结点至多d+1个邻居(含自己), 记录是第几个邻居即可))
  • 而根据信息论中的Incompressibility Theorem, $N$个均匀随机位不能用少于$N-l$比特以至少$1-O(2^{-l})$的概率被编码.
  • 所以w.h.p: (左边减去的$\log_2n$是对应w.h.p)
  • 如果存在$c$满足$d\le 2^{k-c}$, 代入得$T\le m+\log_2 n$.
  • 所以w.h.p可以在$O(n+k(m+\log n))$内找到满足的解.
  • k-SAT的算法LLL得证.
    问题:
  • 如果$T$是无限的呢?
    • 固定随机数比特数$t=2(m+\log n)$, 一旦用完, 算法停止(可能并不满足)
    • 仍然是对固定个数的随机比特的有效的编码

非对称版本的LLL

非对称版本的LLL:
存在$a_1,\cdots,a_m\in [0,1)$, $\forall i:\Pr[A_i]\le a_i\prod_{j\sim i}(1-a_j)$, 则$\Pr[\land_{i=1}^m\overline{A_i}]>\prod_{i=1}^m (1-a_i).$

  • $n$ 个完全独立的随机变量$X_1,\cdots,X_n$
  • $m$ 个坏事件: $A_1,\cdots,A_m$, 由$X_1,\cdots,X_n$决定
  • vbl($A_i$): 定义$A_i$的变量集
  • 邻居$\Gamma (A_i)\triangleq \{A_j|j\ne i\land vbl(A_j)\cap vbl(A_i)\ne\emptyset\}$

存在$a_1,\cdots,a_m\in [0,1)$, $\forall i:\Pr[A_i]\le a_i\prod_{A_j\in \Gamma(A_i)}(1-a_j)$, 则存在赋值$X_1,\cdots,X_n$, 避免了所有坏事件$A_1,\cdots,A_n$
寻找这样的$X_1,\cdots,X_n$的算法为Moser-Tardos Algorithm

Moser-Tardos Algorithm

算法如下:

  • 随机采样所有的$X_1,\cdots,X_n$的一组赋值$x_1,\cdots,x_n\in\{\text{true, false}\}$;
  • while $\exists$ 发生了的坏事件$A_i$
    • 随机采样所有的$X_j\in vbl(A_i)$

假设: 下列事件可以高效完成:

  • 独立随机此采样$X_j$
  • 检测在当前的$X_1,\cdots,X_n$下$A_i$是否发生

Lovász Local Lemma (Moser-Tardos 2010):

存在$a_1,\cdots,a_m\in [0,1)$, $\forall i:\Pr[A_i]\le a_i\prod_{A_j\in \Gamma(A_i)}(1-a_j)$, 则期望上可以在$\sum_{i=1}^m \frac{a_i}{1-a_i}$次重采样内返回满足的赋值.

若$d\le 2^{k-2}$ 则 可以在$O(n+km/d)$的期望时间内找到满足的赋值

算法分析:

更换表述形式:

Moser-Tardos Algorithm:

  • sample all $X\in \mathscr X$
  • while $\exists$ an occcurring event $A\in\mathscr A$:
    • resample all $X\in vbl(A)$

定义运行日志execution log $\Lambda$:

  • $\Lambda_1,\Lambda_2,\cdots\in\mathscr A$, 为重采样时间的随机序列

定义witness tree证据树:

  • 证据树是一个有标记的树, 每个结点$v$标记为一个事件$A_v\in\mathscr A$, 姐妹一定是不同的标记
  • 根据运行日志$\Lambda $构造证据树$T(\Lambda, t)$:
    • 初始, $T$是一个根结点, 标记为$\Lambda_t$:
    • for $i=t-1,t-2,\cdots,1$:
      • 如果存在标记为$A_v\in\Gamma^+(\Lambda_i)$的结点$v\in T$,

证明看讲义吧.