结果族 102：The Unique Games Conjecture and optimal approximation thresholds · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
街区装监控：每条街道至少一端要有摄像头，问最少装几个。教科书技巧（贪心配对）保证”装的个数不超过真正最优的 2 倍”；这篇论文证明：想把 2 倍哪怕改进一丝一毫（比如做到 1.99 倍），都是 NP-难的——贪心看似粗糙，实则已经封顶。
关键词卡片
看个具体例子
定理取 @@M@@m=1000@@：
@@M@@ \text{YES}:\ \tau(G)<0.501\,|V|,\qquad \text{NO}:\ \tau(G)>0.999\,|V| @@
两阈值之比 @@M@@\approx 1.994@@：任何因子 @@M@@\alpha<1.994@@ 的近似算法，在 YES 情形返回 @@M@@\le\alpha\cdot0.501|V|<0.999|V|@@，在 NO 情形返回 @@M@@\ge 0.999|V|@@，一刀就分出 YES/NO，等于解了 3SAT。@@M@@m\to\infty@@ 时比例趋于 2，故一切小于 2 的固定因子都难。
为什么值得关心
“极大匹配给因子 2”这个课堂级算法从此被钉死为最终答案，且证明不依赖唯一博弈猜想。
已 Lean 形式化
第一级台阶
导读的”街区装监控”精确化：对象是一张图，摄像头是顶点、街道是边；操作是挑选一批顶点，使每条边至少有一端被选中，目标是最少化挑选个数。课堂技巧”取极大匹配的全部端点”保证不超过最优的两倍，本文回答的问题是：这个”两倍”还能不能压低。
第二级台阶
| 图的最小点覆盖数记为 τ(G)；极大匹配的端点集给出 τ 的因子 2 近似。α-近似算法指总能返回大小不超过 α·τ(G) 的覆盖的多项式算法。硬度通过间隙归约表达：把 3SAT 实例映射成图，使得公式可满足时 τ(G)<(1/2+1/m) | V | ，不可满足时 τ(G)>(1−1/m) | V | ，其中 m 是预设整数、 | V | 是顶点数。 |
第三级台阶
定理 1.1 在此语境陈述：对每个固定整数 m≥4，存在从 3SAT 到简单无权图的确定性多项式归约实现上述两种界，图的顶点与边全部显式列出。”固定 m”挡住了归约常数随输入增长的漏洞；”简单无权”排除了用权重作弊的辅助结构。两个阈值之比为 2−6/(m+2)，随 m 趋于 2，于是推论 1.2 成立：对每个固定 α<2，α-近似都是 NP-难的；而极大匹配给出因子 2 的上界——除非 P=NP，阈值恰好钉死在 2。
本文无条件证明：在简单无权图上，最小 Vertex Cover 对每个固定因子 @@M@@\alpha<2@@ 都 NP 难近似。教科书级的”极大匹配给因子 @@M@@2@@“由此成为最终阈值，且结论不再依赖唯一博弈猜想。
Vertex Cover（点覆盖）求覆盖所有边的最少顶点数 @@M@@\tau(G)@@，其补集是独立集（independent set）；它以 Node Cover 之名位列 Karp 1972 年的 NP 完全问题表。极大匹配给出因子 @@M@@2@@ 的多项式近似；Karakostas 用半定规划改进到 @@M@@2-\Theta(1/\sqrt{\log n})@@，但该节省随 @@M@@n@@ 增大趋于零。难度一侧：Håstad 证明因子 @@M@@7/6@@ 之下难，Dinur–Safra 于 2005 年提升到 @@M@@10\sqrt5-21\approx 1.36068@@；Khot–Regev 在唯一博弈猜想下证明因子 @@M@@2@@ 之下全难。2017–2018 年的 2-to-2 博弈计划（Khot–Minzer–Safra、Dinur 等、Barak–Kothari–Steurer 及扩张定理）给出无条件的 @@M@@\sqrt2@@ 之下难度，但其完整度密度只到 @@M@@1-1/\sqrt2@@；要得到因子 @@M@@2@@ 阈值，需要完整度密度逼近 @@M@@1/2@@，这正是本文跨越的一步。
定理 1.1（显式覆盖间隙）：对每个固定整数 @@M@@m\ge 4@@，存在从 3SAT 到有限简单无权图的确定性多项式归约：公式可满足时 @@M@@\tau(G)<\left(\frac12+\frac1m\right)|V(G)|@@，不可满足时 @@M@@\tau(G)>\left(1-\frac1m\right)|V(G)|@@，输出显式列出全部顶点与边。两阈值之比为 @@M@@2-\frac{6}{m+2}@@，随 @@M@@m@@ 趋于 @@M@@2@@。推论 1.2：对每个固定 @@M@@1\le\alpha<2@@，Vertex Cover 的 @@M@@\alpha@@-近似 NP 难；除非 @@M@@\mathrm P=\mathrm{NP}@@，不存在 @@M@@2-\varepsilon@@ 因子的确定性多项式算法。
唯一的外部难度输入是 Label Cover（标签覆盖）承诺：由 PCP 定理与 Raz 并行重复定理，可区分”值恰为 @@M@@1@@“与”值至多任意小固定值”的实例；字母表可随该值增大，而本文的解析估计全部与字母表大小无关。构造：设 @@M@@d@@ 个位置，每个无序位置对独立分派一条源约束。一个位置的”查询”由其类型与其余 @@M@@d-1@@ 个位置的端点问题组成，不含约束指标与对端信息。为每个查询—标签对配一个向量坐标；相容标签族按其所选坐标求和，这些和的最大绝对值定义范数 @@M@@\norm{\cdot}@@。图的每个顶点指定全部位置对的约束与网格权重，令 @@M@@S_v@@ 为其位置向量之和；两个不同顶点相邻当且仅当 @@M@@\norm{S_v+S_w}\le 2t@@。完整度：满足的源赋值限制到每个查询给出相容标签，其线性泛函在独立集任两顶点之和上超过 @@M@@2t@@；对对称权重之和做尾估计，可知该独立集占近半图，从而 @@M@@\tau(G)<(\frac12+\frac1m)|V|@@。可靠性：需从大独立集提取短标签表列，且每列只能依赖自己位置的查询与权重——否则固定一对位置后表列会看到对端端点，配对译码论证即失效。分三步：先保方差，剔除至多一个范数 @@M@@\le t@@ 的顶点，距离函数的半差给出一个固定的奇 Lipschitz 函数 @@M@@F@@，把网格权重换成连续均匀权重后，@@M@@F@@ 在新随机和上的方差至少是 @@M@@d@@ 的固定倍数；再限制信息，取 @@M@@h@@ 个位置的小批并冻结外部数据，关键估计是把与某位置相邻的全部种子重采样、同时保持其他位置收到的问题不变——此时只有该位置的查询会变，从而条件”自有问题均值”保留至少 @@M@@h@@ 的固定倍数的总方差（Efron–Stein 式正交分解）；最后从方差到表列，@@M@@F@@ 复合位置和的全梯度落在相容标签选择的带号关联向量的凸包中，但可能依赖全部批输入，而自有问题均值的导数有信息限制却未必在凸包内——立方体上的方差不等式给出自有问题梯度的平方能量，每块 @@M@@\ell^1@@ 范数至多 @@M@@1@@，阈值截断即得不含字母表因子的短表列，再由条件 Jensen 把保留的表列质量传回全梯度，得 @@M@@\E Z\ge 2@@（@@M@@Z@@ 为单个相容选择命中的最多表列数）；而源可靠性下的配对译码给出 @@M@@\E Z<3/2@@，矛盾。整个构造完全确定性：枚举全部有限种子与网格权重，随机变量仅出现在分析中。
论文标注主结果已 Lean 形式化。姊妹篇《The Unique Games Theorem》证明唯一博弈猜想后接入 Khot–Regev 归约，同样给出因子 @@M@@2@@ 阈值；本篇不依赖该猜想，仅用 PCP 与 Label Cover，两条路线互相印证。同族 Max-Cut 直接证明篇结构类似。按 OpenAI 官方声明，未经形式化的结果可能有问题；本篇主结果已形式化，请以社区核验为最终参考。
问 1：证明中最关键、也最脆弱的一步是什么？
答：可靠性分析里的信息限制步。要从大独立集提取短标签表列，且每列只能依赖自己位置的查询与权重；关键估计是把与某位置相邻的全部种子重采样、同时保持其他位置收到的问题不变，用 Efron–Stein 式正交分解保证”自有问题均值”保留至少 h 的固定倍数的总方差。这一步若失效，后续立方体方差不等式给出的表列就不再局部，配对译码随之崩塌。
问 2：为什么表列绝不能看到”对端”的信息？
答：因为配对译码论证需要固定一对位置后，两列表在源约束下于公共测试上一致；若某列表列依赖对端端点问题，它就能”偷看”配对方的答案结构，一致率可以被虚假抬高，E Z<3/2 的源可靠性上界不再适用。这正是查询定义刻意不含约束指标与对端信息的原因。
问 3：与已有工作相比真正的新意是什么？
答：难度侧此前最好是无条件 10√5−21≈1.36（Dinur–Safra）与 2-to-2 计划的 √2；后者卡在完整度密度只到 1−1/√2，而因子 2 阈值需要密度逼近 1/2。Khot–Regev 的因子 2 依赖唯一博弈猜想。本文仅以 PCP 加 Label Cover 为输入无条件越过这一密度门槛，且解析估计全部与字母表大小无关。
问 4：这个结果最可能以什么方式出错？
答：典型风险有二：方差下界的常数（F 在新随机和上的方差至少是 d 的固定倍数）与最后的矛盾收口 E Z≥2 对 E Z<3/2，余量只有 1/2，一处系数含糊即翻盘；其次是所有常数须在请求源字母表之前联合选定（结论一节取 d=2^{38}m^{10} 等），次序错乱会造成循环。主结果已 Lean 形式化，风险已大幅收敛。
问 5：为什么比率写成 2−6/(m+2) 而不直接给 2？
答：归约必须对固定 m 才有多项式规模与固定常数；结论一节明确说明实数 α 只用来选固定整数 m（使 α<2−6/(m+2)），α 本身不是归约的输入，最终比较只涉及整数乘法：基数乘 m 与 (m−1)n 比较。
问 6：结论与 Karakostas 的 2−Θ(1/√log n) 算法矛盾吗？
答：不矛盾。本文难度限于每个固定 α<2；Karakostas 的节省随 n 增大趋于零，不构成任何固定因子的改进，两者恰好把”固定因子难、渐近微改可行”的边界画清。
问 7：谁会用到它？
答：近似算法教材与研究者：极大匹配的因子 2 从此是最优阈值，叙事定稿；与姊妹篇经 Khot–Regev 归约的 UGC 路线互证，结果族 102 的三大阈值（Max-Cut、Vertex Cover、CSP）全部闭合。
总评
把课堂级算法钉死为最终答案的无条件证明，且主结果已形式化；最大残余风险在信息限制与方差估计这些”软分析”环节的形式化覆盖是否完整。