结果族 102：The Unique Games Conjecture and optimal approximation thresholds · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
给地图染红蓝两色，规矩是每条边两端必须异色。Min-UnCut 问：一张注定染不”完美”的图，最少会有几条边两端撞色？等价说法：最少删几条边，图才能变成能完美二染色的二部图。这篇论文证明：对”最少删几条”给出任何固定倍数的近似，都是 NP-难的。
关键词卡片
@@M@@K@@ 倍），倍数可事先指定成任意大。看个具体例子
主定理保证存在这样的图族：公式可满足时删 @@M@@\le k@@ 条边就够；不可满足时必须删 @@M@@>Kk@@ 条边。想否决任何固定因子 @@M@@C@@ 的近似算法，取整数 @@M@@K\ge C@@ 即可——常数因子近似全部无望。
为什么值得关心
此前无条件的难度纪录只到约 1.49 因子，本文一步推到全部常数因子，且完全不依赖唯一博弈猜想。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”地图染红蓝”精确化：对象是一张无向图加一个把顶点分成两色的划分；操作是数”两端撞色”的边——它们没被切开，所以叫 uncut 边。要回答的问题是：一张注定染不完美的图，最少会留下几条撞色边，等价于最少删几条边才能把图变成可以完美二染色的二部图。
第二级台阶
组合优化语言：给定划分后 uncut 边的总数的最小值记为 OPT_uncut(G)；C-近似算法指总能返回不超过 C·OPT_uncut(G) 的解的多项式算法。难度由多一归约制造：把 3SAT 公式 φ 在多项式时间内映射为图与整数对 (G,k)，要求公式可满足时 OPT≤k、不可满足时 OPT>Kk——两种情形的最优值相差预设倍数 K，称为乘性鸿沟。
第三级台阶
主定理在此陈述：对每个固定整数 K≥2，存在这样的确定性多项式归约，且 G 是显式列出的有限简单无向无权图。”K 固定”保证归约规模只随输入增长；”无权简单”排除了用权重或重边编码测试概率的作弊空间。于是对任意想要的因子 C>1，取整数 K≥C 即知 C-近似是 NP-难的；再经每条边换成一对 2CNF 子句的局部替换，最小 2CNF 子句删除问题获得同样的常数因子难度。
对任意固定常数 @@M@@C>1@@，在简单无向无权图上把 Min-UnCut 近似到 @@M@@C@@ 因子以内是 NP-hard 的。该结果完全不依赖唯一游戏猜想，把此前无条件硬度只做到约 @@M@@1.49@@ 因子的纪录一举推进到所有常数因子。
Min-UnCut 度量一张图离二部图（bipartite graph）有多远：给定无向图 @@M@@G=(V,E)@@ 和顶点二部划分，两端落在同侧的边称为 uncut 边，目标是最小化其条数，等价于删掉最少的边使图变成二部图。它与 Max-Cut 互为补问题，但当图几乎二部时，Max-Cut 的乘性近似对 Min-UnCut 无从借力，因此其可近似性问题自成一格。算法一侧，Agarwal、Charikar、Makarychev 与 Makarychev 在 2005 年给出随机 @@M@@O(\sqrt{\log |V|})@@ 近似；硬度一侧，KKMO 在唯一游戏猜想（Unique Games Conjecture, UGC）下证明任意常数因子都难，而无条件结果长期停留在 @@M@@1.49@@ 之下：Håstad 等人 2017 年得到加权 Max-Cut 删除问题的 @@M@@11/8@@，Wiman 2018 年改进到 @@M@@1.45685@@，Martinsson 2024 年对两条变量奇偶方程的违约权重问题做到约 @@M@@1.48969@@（可转移到加权 Min-UnCut）。真正的卡点有二：把 UGC 式分析改写成无条件 PCP 归约时，标签解码通常要付出与字母表大小相关的损失；同时还要把连续的概率测试落到无权简单图上而不引入加性误差。
主定理：对每个固定整数 @@M@@K\ge2@@，存在确定性多项式时间多一归约（many-one reduction），把 3SAT 公式 @@M@@\varphi@@ 映为 @@M@@(G,k)@@，其中 @@M@@G@@ 是显式的有限简单无向无权图，@@M@@k\ge1@@ 是正整数，满足：@@M@@\varphi@@ 可满足时 @@M@@\OPT_{\rm uncut}(G)\le k@@，不可满足时 @@M@@\OPT_{\rm uncut}(G)>Kk@@。于是对任意固定 @@M@@C>1@@ 取整数 @@M@@K\ge C@@：确定性多项式时间 @@M@@C@@-近似算法将蕴含 @@M@@\mathsf P=\NP@@，带常数成功概率的随机版本则蕴含 @@M@@\NP\subseteq\RP@@。推论：最小 2CNF 子句删除（minimum 2CNF clause deletion）对每个固定常数因子同样 NP-hard——把每条边换成两个子句 @@M@@(x_u\lor x_v)@@ 与 @@M@@(\neg x_u\lor\neg x_v)@@，即可精确保持最优删除数。
整个证明先构造一个”位比较”鸿沟，再把它逐条实现为图上的 uncut 边。
第一步，起点完全无条件：Håstad 的三变量奇偶方程鸿沟——可满足输入能命中至少 @@M@@1-\zeta@@ 比例的方程，不可满足输入至多 @@M@@3/4@@——再用 Raz 与 Holenstein 的并行重复（parallel repetition）把双人游戏值压到 @@M@@c^r@@。外层游戏中两位玩家的字母表都是 @@M@@\F_2@@ 上的仿射空间（affine space），答案一致性由仿射映射检验。论文为其证明两件事：即使让双方共享固定条数的仿射函数作提示，游戏仍然可靠，因为许多隐藏坐标在这些函数上系数为零；且拉回的均匀仿射函数族联合分布接近独立均匀，允许后继解码依赖这份共享背景。
第二步，内层测试用长码（long code）与折叠（folding）把标签换成函数 @@M@@f@@：对每个布尔查询给出符号，只要求满足 @@M@@f(-P)=-f(P)@@。三个测试分别施加高斯扰动、行重采样与真值表单条目翻转。对任意证明先做高斯平均得到光滑实值函数：第一个测试很少改变答案，故其梯度保有能量（Hermite 展开配合高斯 Poincaré 不等式）；后两个测试控制其 Fourier 度数与低次结构。关键在于这些界只依赖数组位置数目，与字母表大小无关。
第三步，把上述低次相关转换成单个仿射函数条目上的大 Fourier 系数，且该系数是奇的（odd frequency）；奇频率与标签一一对应，这正是”奇频率即标签”引理。提取时先用数组对称性把相等奇频率配对，再限制到随机小盒子分离变量，最后反复使用 Cauchy–Schwarz（Gowers 式超图论证）把项收拢为四角方形上的乘积。选项只依赖数组位置与高斯度数、从不枚举标签频率，因此提取概率与系数大小都与字母表无关——正是这一步绕开了先前方法的字母表损失。
第四步，组合：新增第四个测试，比较双方对同一拉回查询的回答。低代价迫使两个单行光滑函数在 @@M@@L^2@@ 意义下接近；用四阶矩恒等式压制剩余小系数后，双方的大奇系数各给出一个短标签列表，它们以固定正概率含有一对一致标签，从而拼出外层游戏策略，与提示版可靠性矛盾。
最后是有限化：把整个联合高斯符号表用有理分布逼近（截断、网格、以有理多项式逼近 @@M@@e^{-v^2/2}@@），枚举出确定性的有理比较系统，其代价与连续版本相差不足 @@M@@1/2@@；再把每个需求单位实现为长度四（等式）或三（不等式）的路径，路径内部顶点全新，使每件小工具的最小 uncut 代价恰好等于该需求的失败指示子，没有加性基线。取 @@M@@k=5D_0@@：YES 情形 @@M@@\OPT<(9/2)D_0<k@@，NO 情形 @@M@@\OPT>(10K-\tfrac12)D_0>Kk@@，严格乘性鸿沟成立。
本篇属于该结果族的”独立直接归约”支线：只使用既有的 PCP 与 Label Cover 硬度（Håstad 奇偶鸿沟加并行重复），既不假设也不消费本族中心篇所证明的 UGC，却给出其重要推论的无条件版本，与族内中心篇互相印证。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本篇主结果尚无 Lean 形式化证明，请以社区核验为准。
问 1：证明中最关键、也最脆弱的一步是什么？
答：与字母表大小无关的 Fourier 提取（”奇频率即标签”引理）。把低次相关转换成单个仿射函数条目上的大奇 Fourier 系数后，靠数组对称性配对相等奇频率、随机小盒子分离变量、反复用 Cauchy–Schwarz 把项收拢为四角方形上的乘积；选项从不枚举标签频率，提取概率才与字母表无关。此前无条件方法正是在解码处付出字母表损失而止步于 1.49 因子。
问 2：为什么外层游戏要专门证明”带共享提示仍然可靠”？
答：组合阶段双方要比较对同一拉回查询的回答，分析中允许双方共享固定条数的仿射函数作提示；论文证明许多隐藏坐标在这些提示函数上系数为零，游戏值仍被压低。没有这条提示版可靠性，组合出的策略一致率无法与外层矛盾，鸿沟论证断链。
问 3：长码折叠 f(−P)=−f(P) 这个假设为什么不能去掉？
答：折叠强制证明表只使用奇 Fourier 频率，而奇频率与仿射标签一一对应——这正是能把大系数直接读成标签的结构性原因。去掉折叠后偶频率大量出现，大系数可能对应与标签无关的常数项或对称函数，解码失效。
问 4：与已有工作相比真正的新意是什么？
答：KKMO 的常数因子难度以唯一博弈猜想为条件；无条件纪录先后为 Håstad 等的 11/8、Wiman 的 1.45685、Martinsson 的约 1.48969。本文仅用 Håstad 奇偶鸿沟加 Raz–Holenstein 并行重复，通过字母表无关的内层分析一步推到全部常数因子，且不消费本族中心篇的 UGC。
问 5：这个结果最可能以什么方式出错？
答：典型 AI 生成证明的风险在有限化：连续高斯符号表要用截断、网格与 e^{−v²/2} 的有理多项式逼近换成确定性有理比较系统，声称代价差不足 1/2；路径 gadget 必须使每件小工具的最小 uncut 代价恰等于需求失败指示子、零加性基线。取 k=5D₀ 后 YES 侧 (9/2)D₀、NO 侧 (10K−1/2)D₀ 的余量都不宽，一处逼近误差失控即翻盘。论文未形式化。
问 6：Max-Cut 有 0.8786 近似，为什么帮不到 Min-UnCut？
| 答：两者互补但当图几乎二部时 Max-Cut 值接近 | E | ，任何常数因子的 Max-Cut 近似对”差多少才是二部”这一微小差额不敏感；Min-UnCut 的乘性结构必须单独处理，这也是它自成一格的原因。 |
问 7：谁会用到它？
| 答：近似算法与 PCP 社区：Min-UnCut 的可近似性定界为”对数因子以下全难”，与 ACMM 的 O(√log | V | ) 随机算法恰好划定边界；2CNF 子句删除的常数因子难度推论对 SAT 求解器的预处理策略也有参考意义。 |
总评
把一条此前只在 UGC 下成立的著名难度推到无条件的全部常数因子，技术路线清晰独立；最大风险是长链条的连续到有限转换未经形式化，数值余量偏窄。