说点 Unique Games Conjecture

前几天正好听了一次 Irit Dinur 的 seminar, 试着写点 UGC 相关的东西. 下面主要介绍 UGC 的来源 ( $\mathsf{NP}$-hardness 和 PCP 定理), 以及和 UGC 直接相关的进展.

PCP 定理, UGC 和不可近似性

故事应该从 PCP 定理之后讲起. 上世纪九十年代初证明的 PCP 定理刻画了不可近似性 (hardness of approximation), 准确地说是证明某些问题的近似算法能做到某个近似比是 $\mathsf{NP}\text{-hard}$ 的. 比如说 Johan Håstad 在 1996 年给出的一系列结果^[1] 中 3-LIN:

给定有限域 $\mathbb{F}_2$ 上的线性方程组, 并且每个方程至多涉及三个不同变量. 那么判定满足的方程比例是 $\geq 1-o(1)$ 还是 $\geq 1/2+o(1)$.

这一结果证明了近似比为 2 的近似算法是最优的. 那么下一个问题是, 我们能否对每一个近似问题都给出类似的精确刻画?

Subhash Khot 在 2002 年提出了 Unique Game Conjectures, 因此他获得了 2014 年的 Nevanlinna Prize (每次都在国际数学家大会上颁发). UGC 给出的结果要比直接用 PCP 定理强一些:

• 2003 年, Khot 和 Regev 证明 ^[2] 如果 UGC 成立, 那么已知的 Vertex-Cover 的近似算法是最优的.
• 2004 年, Kindler, Khot, Mossel 和 O’Donnell 证明 ^[3] 如果 UGC 成立, 那么已知的 Max-Cut 的近似算法 (Goemans-Williamson) 是最优的.
• … (懒得继续查 reference 就不写了, 相关工作应该很多, 毕竟是目前证明不可近似性的标准工具之一)

简而言之, 如果 UGC 是对的, 那么我们对不可近似性的理解会大大加深, 并且证明一批经典问题没有更好的近似算法. 如果 UGC 是错的, 那么一定有新的近似算法技术存在.

值得一提的是, 05 年 O’Donnell 在 UW 开了门关于 PCP 定理和不可近似性的课^[4], 并且写了某篇著名的 A History of PCP Theorem – 一个冷知识是, 当年 Muli Safra 在加州开会, 结果被走错房间的缉毒警察搜查 PCP (一种毒品, 应该是普斯普剂) – 于是 PCP 定理就有个这么个"糟糕"的名字, 如果叫 locally testable proof 之类的名字的话, 也许要方便顾名思义得多.

什么是 UGC and d-to-1 games

然后展开说一下 Label Cover 吧. LC 实例 $G=(A,B,E,\Pi,\Sigma_A,\Sigma_B)$ 说的是在一个二分图 $(A,B,E)$ 上,

• 顶点集合 $A$ 和 $B$ 可以涂得颜色集合 (即字母表) 分别是 $\Sigma_A$, $\Sigma_B$.
• 二分图的边用约束集合 $\Pi=\{\pi_{u,v}\}_{(u,v)\in E}$ 刻画, 其中每条边 $(u,v)$ 对应的约束满足 $\pi_{u,v}\subseteq \Sigma_A\times\Sigma_B$, 简而言之就是我们知道每条边的两个顶点只能涂哪些颜色.
• 然后找到顶点的染色方案 (赋值) $c: A\cup B\rightarrow \Sigma_A\cup\Sigma_B$, 其中每一条边满足约束, 意味着 $(c(u),c(v))\in \pi_{uv}$. 当然如果找到的方案只能满足 $\alpha (0 \leq \alpha \leq 1)$ 的约束的话, 其实就给出了这一问题的近似.

上面这个问题可以规约到 gap-$\mathsf{3SAT}$ 上, 让二分图左边对应子句, 右边对应变量, 边呢对应每个子句是否被满足. 实际上, 诸如 3-SAT 或 Label Cover 或 3-Lin 都是 CSP (约束可满足问题) 的特例, 这里不再展开. Irit Dinur 的 PCP 定理证明 ^[5] 就是对 gap-CSP 利用 expander 做 gap amplification.

顺着上面的 Label-Cover 接着说 UGC 的定义. 每个 LC 实例 $G=(A,B,E,\Pi,\Sigma_A,\Sigma_B)$ 都可以看成一个 2-Player-1-Round game, 即两个玩家和一个裁判. 裁判首先挑一条边 (约束) 提问, 然后两个玩家 A 和 B 分别根据边两端的顶点给出对应的可能的染色方案 (赋值), 裁判认为玩家胜利当且仅当玩家的答案满足约束.

为了定义 UGC, 我们先考虑 $d\text{-to-}1$ games. 即 $\Sigma_A$ 可以划分为 $r$ 个 (不相交) 集合 $S_1,\cdots,S_r$. 那么这个时候的约束 $\Pi$ 可以写成 $\pi_{uv}=\cup_{i=1}^{r} S_i \times \{b_i\}$, 即字母表满足 $|\Sigma_A|=dr$,$|\Sigma_B|=r$. 如果 $\Pi$ 里的所有约束都满足上述形式的话, 那么对应的 2P1R game 是 $d\text{-to-}1$ 的. 如果 $d=1$ 的话 (这也是为什么名字里有 unique), 那就是 Subhash Knot 提出的 Unique Games Conjecture ^[6], 事实上这时候给出了一个二分图的完美匹配.

如果读者熟悉 PCP 定理的几种等价表述的话, 就会觉得和上述 UGC 的定义很相似, 除了 UGC 增加了关于字母表的奇怪约束. 不过很明显这东西跟 $\mathsf{P}\overset{?}{=}\mathsf{NP}$ 没什么逻辑关系, 除了 $\mathsf{P}=\mathsf{NP}$ 的话所谓的 hardness 将不复存在. 从另一个方面看 UGC 和 PCP 的"联系"也很明显, 因为做 UGC 的几个人多数是做 PCP 定理的那帮人以及他们的学生 – 最终用 composition 证明了 PCP 定理的是 Sanjeev Arora 和 Muli Safra, Subhash Khot 是 Arora 的学生, Kindler, Dinur 和 Minzer 都是 Safra 的学生, 其中 Minzer 还是在读 PhD.

证明/推翻 UGC 的进展

把 UGC 当假设给出其他结果的工作很多, 但是试图证明或者推翻 UGC 的工作寥寥可数:

• 2008 年, Arora, Khot, Kolla, Steurer, Tulsiani 和 Vishnoi ^[7] 证明如果 CSP 对应的图是 expander 的话, 那么 UG 可以在多项式时间内求解.
• 同年, Kempe, Regev 和 Toner 证明 ^[8], 如果两个玩家直接可以共享纠缠的话, 那么 UG 可以在多项式时间内求解. 如果 UGC 被最终证明的话, 这应该也算是 quantum advantage 了.
• 2010 年, Arora, Barak 和 Steurer ^[9] 给出了部分 UG 实例的 sub-exponential time algorithm. (回忆一下关于 3SAT 的 Exponential Time Hypothesis)
• 2012 年, Barak, Brandao, Harrow, Kelner, Steurer 和 Zhou (这位周源) ^[10] 基于 Sum-of-squares 和 SDP 给出了能够求解已知 UG 困难实例的多项式时间算法.
• 2016 年, Khot 和 Moshikovitz 给出了新的 UG 困难实例 ^[11].
• 2017 年, Dinur, Kindler, Khot, Minzer 和 Safra 用 Grassman graph 和 agreement test 证明了 $2\text{-to-}1$ games ^[12], 两篇工作均被今年 STOC 接受.
• 2018 年 Khot, Minzer 和 Safra 用 DKKMS 的技术证明了 2\text{-to-}2 games ^[13].

2016 年之前的结果多是支持 UGC 不成立, 直到最后两个结果直接证明了部分 UGC. 他们证明了 UGC 的下述弱化情形:

判定给定的 UG 实例中约束被满足的比例是 $\geq\frac{1}{2}-\epsilon$ 还是 $\leq \epsilon$ 是 $\mathsf{NP}\text{-hard}$ 的.

参见 Boaz Barak 的博客 ^[14] 中给的图, completeness 和 soundness 分别是约束被满足的比例的两种情况, 显然 completeness > soundness. halfway 大概是因为, 下面的三角形终于被填了$1/4$:

UG(c,s), 图片来自 Boaz Barak 的博客 ^[14:1]

稍微说两句证明, Boaz Barak 在他们的 Reading Group 给过两次报告, 并且整理了 Lecture Notes ^[15]. DKKMS^[12:1] 设法联系了 argument test 和 Grassman graph 上的 expansion, 具体技术细节我也 follow 不来, 也就不说了.

不过这个观点本身很有意思, 我们可以把 linearity test (好像可以翻译成线性检测) 的 robustness 对应到 high-dimension expander 的 expansion 上. Linearity test 说的是这么件事 (通常称为 Blum-Luby-Rubinfeld 定理), 即如何检测一个函数是不是几乎线性的:

$\forall f: \mathbb{F}_2^n\rightarrow \mathbb{F}_2$, 如果 $\mathrm{Pr}_{x,y\in\mathbb{F}_2^n} [f(x)+f(y)+f(x+y) \neq 0]<\epsilon$, 那么存在线性函数 $g:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$ 使得 $\text{Pr}_{x\in\mathbb{F}_2^n}[f(x)\neq g(x)] < \epsilon/\alpha$.

通常 linearity test 的 soundness 分析是 analysis of Boolean function 的典型应用, 如果知道一点群表示论的话, 那么其实这里用到的就是近似群表示 (approximate group representation). 但是实际上如果我们用合适的方式定义链复形 (complex) $C^0,C^1,C^2$ 和 boundary operator $\delta$ 的话, 我们也能类似地定义 (expander graph 中的) expansion, 使得 $\|\delta f\|/\|[f]\| > \alpha$. 更多的细节不再展开, Irit Dinur 的 Lecture Notes ^[16] 上有一些介绍.

参考文献