结果族 102：The Unique Games Conjecture and optimal approximation thresholds · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
学校分班：把互相吵架的学生分进两个班，让跨班的”吵架对”尽量多。1995 年的 Goemans–Williamson 算法能保证切到最优值的约 87.86%；这篇论文证明：除非 P=NP，谁也别想明显超过这条线——三十年前的老算法原来已经是天花板。
关键词卡片
@@M@@\alpha_{\mathrm{GW}}\approx 0.8786@@）：用随机超平面舍入所能保证的最优近似比。看个具体例子
小例子：三角形图的最优割是 2 条边（三人分两班，必有一对同班），GW 算法期望至少切到 @@M@@\alpha_{\mathrm{GW}}\cdot2\approx1.757@@ 条。定理说：对任何固定 @@M@@\alpha>\alpha_{\mathrm{GW}}@@，给出 @@M@@\alpha@@-近似的算法都不存在（NP-难）——”保证切到最优的 95%”这类目标绝无可能。
为什么值得关心
为悬置二十余年的中心问题画上句号：GW 的半定规划算法就是 Max-Cut 的最优多项式算法，而且结论不再依赖任何未证猜想。
已 Lean 形式化
第一级台阶
导读把 Max-Cut 说成”把吵架的学生分进两个班”：对象是一个无向图，吵架对是边；操作是把顶点划分成两部分，数有多少条边跨越分割。1995 年的 Goemans–Williamson 半定规划算法保证切到最优值的约 87.86%，本文要精确回答的问题是：这条线是不是算法能力的尽头。
第二级台阶
用组合优化语言：图的最大割值记为 Val；一个 α-近似算法指对每个实例都返回割值不低于 α·Val 的多项式算法；Goemans–Williamson 常数 α_GW 定义为比率 (1+B(t))/(1+t) 在 t∈(0,1) 上的最小值，其中 B(t)=(2/π)arcsin t 是噪声稳定性函数。硬度靠间隙问题表达：区分”割值高”与”割值低”两类实例若 NP-难，则任何跨间隙的近似算法都不存在。
第三级台阶
定理 1.2（间隙定理）陈述：对固定有理数 t∈(0,1) 与 0<ε<(t−B(t))/4，区分 Val≥(1+t)/2−ε 与 Val≤(1+B(t))/2+ε 的实例是 NP-难的；上界 ε<(t−B(t))/4 挡住的是”间隙为正”这一底线，有理性则保证权重可显式编码。两个阈值之比恰好在某个 t 处取到 α_GW，于是定理 1.1 随之成立：对每个固定 α>α_GW，即使简单无权图上的 α-近似也是 NP-难的——GW 算法被确认为最优多项式算法，且结论不依赖任何未证猜想。
本文无条件证明：在简单无权图上，把 Max-Cut 近似到优于 Goemans–Williamson 常数 @@M@@\alpha_{\mathrm{GW}}\approx 0.8786@@ 的任何固定比率都是 NP 难的。1995 年的半定规划算法由此被确认为最优多项式算法，且结论不再需要唯一博弈猜想作前提。
Max-Cut 要把图顶点分成两部分，使跨越分割的边权最大，是 Karp 1972 年列出的最早一批 NP 完全问题之一。Goemans 与 Williamson 在 1995 年用半定规划（semidefinite programming）加随机超平面舍入得到期望比率 @@M@@\alpha_{\mathrm{GW}}=0.878567\ldots@@ 的多项式算法，此后”该比率是否无条件最优”成为近似算法领域的中心问题。难度方面，Håstad 的 Fourier 方法配合 gadget 只能排除 @@M@@16/17\approx 0.941@@ 以上的比率；Khot、Kindler、Mossel、O’Donnell 则证明：若承认唯一博弈猜想，@@M@@\alpha_{\mathrm{GW}}@@ 就是最优的，其解析核心是”多数最稳定”定理（Majority Is Stablest）。Feige–Schechtman 的积分间隙只说明 SDP 松弛本身的局限，不构成对任意算法的难度。这一缺口悬置了二十余年。
定理 1.1：对每个固定 @@M@@\alpha\in(\alpha_{\mathrm{GW}},1]@@，简单无权图上 Max-Cut 的 @@M@@\alpha@@-近似是 NP 难的。证明落在更精确的间隙定理（定理 1.2）：固定有理数 @@M@@t\in(0,1)@@ 与 @@M@@0<\varepsilon<(t-B(t))/4@@，其中 @@M@@B(t)=\frac{2}{\pi}\arcsin t@@，则区分 @@M@@\Val\ge\frac{1+t}{2}-\varepsilon@@ 与 @@M@@\Val\le\frac{1+B(t)}{2}+\varepsilon@@ 的图（边权为有理概率分布，@@M@@\Val@@ 为最大割权重）是 NP 难的。两阈值之比 @@M@@\frac{1+B(t)}{1+t}@@ 的最小值恰为 @@M@@\alpha_{\mathrm{GW}}@@，故任何 @@M@@\alpha>\alpha_{\mathrm{GW}}@@ 的近似算法都能切开这个间隙，与定理 1.1 等价。
起点是已发表的 2-to-1 博弈构造（Dinur–Khot–Kindler–Minzer–Safra 一系，含 Khot–Minzer–Safra 扩张定理），本文取其精确的仿射形式：约束投影是二元线性空间之间维数差一的满射仿射映射，且字母表可在完整度误差任意调小之前、先按所需可靠度固定。这一量词顺序使全篇选参自洽；这是唯一的外部难度输入，唯一博弈猜想仅作历史背景。归约是长码（long code）式的：标签 @@M@@a@@ 由独裁函数 @@M@@w\mapsto w(a)@@ 表示，图为每个源左端点元组配一个字域，任意割即一族布尔函数。查边时经公共右端点抽两条边，把生成的字经仿射投影拉回并将第二个字取负；源约束全满足时独裁标记以约 @@M@@\frac{1+t}{2}@@ 的概率被割开，此为完整度。核心创新是字的生成器：一棵有限根树，每个内部节点带 @@M@@s@@ 对孩子与一张随机表，叶子携带标签空间上的仿射形式；门规则使 Walsh 展开的每个单项式从每对孩子中恰取一项。另做一次成对探索，每层只保留随机一对孩子的双方；两条探索在任何固定深度恰有一个公共节点，在该深度以逐元素相关 @@M@@t@@ 耦合两边的表，使每个单项式恰染一个因子 @@M@@t@@；并对仿射行少量独立重采样以平滑。可靠性：把任意割的奇部沿源边平均，得在所选表项上均衡的函数；割值超过 NO 阈值意味着期望噪声稳定性超过 @@M@@B(t)@@，由”多数最稳定”检出一个高影响表项——但它由门的输入索引，并非源标签。随后三步弥合裂缝：其一，利用门对称性局部简化 Fourier 支撑，使仿射平移成为该门表格的平移；其二，向量值仿射散列引理：独立仿射平移下，弥散的 Fourier 质量平均造不出大表项影响，界还与行空间维数无关；其三，隐藏坐标译码：质量集中须固定许多行坐标，而左端点不知投影就无法拉回这些上下文——在乘积博弈的一个随机因子植入零系数，遗忘后分布几乎不变，该因子处无需投影即可拉回，只需跨因子比较所选门的 @@M@@2s@@ 条自由行，代价 @@M@@2^{2s}@@ 质量。译码损失与源字母表大小无关，否则字母表维数依赖所求可靠度，选参将循环。最终按”先译码损失与源可靠度，再字母表与因子数，最后源完整度误差”的顺序定参；附录给出向简单无权图的确定性转换。
论文标注主结果已 Lean 形式化。姊妹篇《The Unique Games Theorem》证明唯一博弈猜想后，接入 KKMO 归约同样给出 Max-Cut 的最优阈值；本篇不依赖该猜想、从 2-to-1 博弈直接出发，两条独立路线互相印证。同族 Vertex Cover 篇则确立因子 @@M@@2@@ 阈值。按 OpenAI 官方声明，未经形式化的结果可能有问题；本篇主结果已形式化，请以社区核验为最终参考。
问 1：证明中最关键、也最脆弱的一步是什么？
答：可靠性分析中”弥合裂缝”的三步。割值超阈值经多数最稳定定理检出的高影响表项，是由门的输入索引的，并非源标签；必须依次用门对称性简化 Fourier 支撑、向量值仿射散列引理压制弥散质量、隐藏坐标译码把影响送回源博弈。任何一步失守，”高割值 ⇒ 源博弈有解”的桥梁就断了。
问 2：为什么从 2-to-1 博弈出发，而不走唯一博弈或 Label Cover？
答：本文唯一的外部难度输入是 Dinur–Khot–Kindler–Minzer–Safra 一系（含 KMS 扩张定理）2-to-1 构造的精确仿射形式：其字母表可在完整度误差任意调小之前先按可靠度固定。这一量词顺序使全篇选参自洽；不依赖刚证完的唯一博弈定理，也使本篇与 UGC 路线构成互证的独立证据。
问 3：ε<(t−B(t))/4 与 t 取有理数这两个假设为什么不能去掉？
答：ε<(t−B(t))/4 保证 YES 与 NO 阈值之间隙严格为正，否则间隙问题无从区分；t 与各参数取有理数则保证枚举测试结果得到的边权重具多项式比特复杂度——第 10 节的确定性多项式时间构造明确用到这一点。
问 4：与已有工作相比真正的新意是什么？
答：Håstad 的 Fourier 方法只能排除 16/17 以上比率；KKMO 证明 α_GW 最优但以唯一博弈猜想为条件；Feige–Schechtman 只是 SDP 积分间隙。本文首次无条件达到 α_GW，核心创新是树的字生成器：成对探索在公共深度以逐元素相关 t 耦合两边，使每个 Walsh 单项式恰染一个因子 t，直接制造出 B(t) 形状的稳定性门槛。
问 5：这个结果最可能以什么方式出错？
答：典型风险是参数循环依赖：全文按 (t,ε,μ)→(s,m,p*,θ)→b→n→T→a 的次序定参，任何一处把后面才定的量用到前面，选参即崩；其次是指示”译码损失与源字母表大小无关”的隐藏坐标论证中遗忘后分布几乎不变的估计。主结果已 Lean 形式化，此类风险已大幅收敛，但附录向简单无权图的转换细节仍值得人工复核。
问 6：构造的图有多大？还算是多项式时间吗？
| 答：顶点数为 | X | ^T·2^{2^{(n+1)T}}，含双指数；但固定 t,ε 后 s、n、T 全是常数，故相对 3SAT 输入规模仍是多项式。第 10 节枚举每个测试结果并把概率加到对应边权上，是确定性多项式时间计算。 |
问 7：谁会用到它？
答：近似算法领域自此把 Max-Cut 从”条件最优”改写为”无条件最优”，教科书叙事就此定稿；SDP 舍入的工程侧也获得了理论上的不可改进性保单；与姊妹篇 Unique Games 定理的两条路线互证，加固了整个结果族 102。
总评
为悬置三十年的中心问题画上句号，且主结果已形式化、证明路线独立于 UGC，分量与可信度双高；残余风险集中在附录无权化转换与超长参数链的边角细节。