结果族 102：The Unique Games Conjecture and optimal approximation thresholds · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
一片单行道路网里藏着能绕圈的路线；想打断所有绕圈，最少要关闭几个路口？这就是有向反馈顶点集问题。已知算法只能保证对数级别的近似；这篇论文证明：任何固定常数倍的近似（哪怕 100 倍）都是 NP-难的，而且这次不再需要借助任何未证猜想。
关键词卡片
看个具体例子
小例子：三个路口组成的单行三角环，关闭任意一个，圈就全断，答案为 1。主定理：对任意固定 @@M@@A\ge1@@（如 @@M@@A=100@@），区分”删 @@M@@\le k@@ 个就够”与”删 @@M@@>Ak@@ 个才够”是 NP-难的；因此常数因子近似算法存在当且仅当 P=NP。同样的难度对”删边版”（最小反馈弧集）也成立。
为什么值得关心
“任意常数因子都难”此前只在唯一博弈猜想下成立，本文把它变成无条件的普通 NP-难，追平了猜想所许诺的全部结论。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”单行道路网”精确化：对象是一张有向图，箭头都是单行道；麻烦在于存在沿箭头方向绕回起点的路线。要做的事是关闭尽量少的路口（删顶点），使剩下的路网里一条绕圈路线都不剩——求这个最小数目。
第二级台阶
图论语言：沿箭头回到起点的路线叫有向圈；反馈顶点集指删去后余图无圈的顶点集，其最小大小记为 DFVS(G)；无圈性可用拓扑序（把顶点排成一行、所有箭头指向同侧）在多项式时间内验证。A-近似算法指总能返回大小不超过 A·DFVS(G) 的解的多项式算法，A 是任意固定常数。
第三级台阶
定理 1.1 在此陈述：对每个固定实数 A≥1，存在从 NP-难承诺问题出发的确定性多项式时间归约，产出实例 (G,k)，使 YES 情形 DFVS(G)≤k、NO 情形 DFVS(G)>Ak，且 G 是无权有向图。”固定 A”挡住了归约常数随输入增长的漏洞；无权图排除了用代价作弊的空间。结论是：多项式时间常数近似算法存在当且仅当 P=NP——此前这需要唯一博弈猜想背书，如今成为普通 NP-难；同样的难度连带传给反馈弧集（删弧版）问题。
对任意固定常数 @@M@@A\ge1@@，在无权有向图上把最小反馈顶点集近似到 @@M@@A@@ 因子是 NP-hard 的。此前这一结论依赖唯一游戏猜想，本文把它变成不附带复杂性假设的普通 NP-hardness。
有向图的最小反馈顶点集（directed feedback vertex set, DFVS）是删去后使余图无环的最小顶点集，等价于命中每条有向圈，可用拓扑序（topological order）在多项式时间内验证。算法方面，Seymour 1995 年关于有向圈分数装填（fractional packing）的工作给出一般的 @@M@@O(\log n\log\log n)@@ 近似，Even–Naor–Schieber–Sudan 1998 年给出覆盖加权情形的构造性算法，至今没有实质改进。硬度方面，把无向图每条边换成一对反向弧，顶点覆盖（Vertex Cover）的任何硬度都直接迁移到 DFVS：Dinur–Safra 的 @@M@@10\sqrt5-21@@、以及 two-to-one 游戏路线完成的 @@M@@\sqrt2@@ 以下因子相继传入。但”每个常数因子都难”这一更强命题，此前只在 UGC 之下成立：Guruswami–Manokaran–Raghavendra（2008 年，后与 Håstad、Charikar 出期刊版）经最大无环子图与反馈弧集建立，Svensson 2013 年与 Guruswami–Lee 2016 年又给出 YES 结构更强的构造。换言之，常数因子门槛之上始终横亘着一道复杂性假设，本文将其移除。
主定理：对每个固定实数 @@M@@A\ge1@@，存在从 NP-hard 承诺问题（promise problem）出发的确定性多项式时间归约，产出实例 @@M@@(G,k)@@ 满足 YES: @@M@@\DFVS(G)\le k@@、NO: @@M@@\DFVS(G)>Ak@@。因此，多项式时间常数近似算法存在当且仅当 @@M@@\mathrm P=\mathrm{NP}@@。两个附带结论：同样的常数因子硬度对最小反馈弧集（directed feedback arc set）在无权、无重弧、无双向弧的有向图上成立；DFVS 版本也可要求图中不出现反向弧。
出发点是”不完美完备性”的 2-to-1 游戏定理（由 Dinur–Khot–Kindler–Minzer–Safra、Khot–Minzer–Safra、Barak–Kothari–Steurer 等人的工作合成）：区分游戏值至少 @@M@@1-\theta@@ 与至多 @@M@@\theta@@ 的 2-to-1 游戏是 NP-hard 的，且投影纤维恰好两个——论证完全不消费唯一游戏硬度定理。构造沿用 Svensson 独裁测试（dictatorship test）中受保护顶点与可删测试顶点的分工：受保护的是”秩顶点”，可删的是”测试顶点”。
先建加权图。对每个短的游戏顶点元组 @@M@@\mathbf d@@ 与取值于 @@M@@[N]@@ 的秩函数 @@M@@x@@，建一个代价 @@M@@D+1=10A+1@@ 的顶点；当 @@M@@x@@ 逐点小于 @@M@@y@@ 时加弧，并按前缀投影把相应顶点等同起来。核心不变量：任何全局标号 @@M@@\ell@@ 通过 @@M@@x(\ell(\mathbf d))@@ 给出评估值，使每条秩弧严格递增，故秩图本身无环。测试顶点分三族：全前缀测试（总质量 @@M@@H@@）、大侧与小侧各一族的单标签测试（质量 @@M@@|X|@@ 与 @@M@@|Y|@@）、比较测试（质量 @@M@@K@@），每族都按”逐结果建点、概率计入代价”确定性枚举。YES 情形删去评估元组落入星集的通配测试与所涉边不被满足的比较测试，指数型 Markov 界逐族付账，总代价至多 @@M@@4@@；幸存弧按评估值严格递增，因此无环。
NO 情形反设存在代价至多 @@M@@D@@ 的反馈顶点集：秩顶点全部幸存，其拓扑序在秩顶点间诱导出一致的比较位，论文分四步读出矛盾。其一，秩比较：用有限 Ramsey 定理加有限 minimax 造出秩嵌入的分布，使任意三个位置的像分布几乎相同，于是有序比较以高概率一致，得到关于标号元组子集的单调布尔函数。其二，共享前缀的条件化：随机子集把元组按词典序分成胞腔，单调性选出唯一转移胞，全前缀测试保证它在每个二进偏差（bias）下的一步不至于太少，从而条件化后大侧函数的接受概率在每个尺度都不低于偏差的固定常数倍。其三，与字母表无关的关键性（pivotality）预算：单标签测试对”星标在随机排列某个前缀处成为关键”收费，所得量 @@M@@B(f)@@ 同时控制总影响力与接受概率除以偏差，其期望不超过 @@M@@D+1@@；于是 Friedgut 的 junta 定理（固定二进偏差版本）给出有界坐标列表，其大小在游戏字母表确定之前就已固定。其四，跨尺度的公共尾变量：用保持投影的耦合比较大侧偏差 @@M@@p_i@@ 与小侧偏差 @@M@@2p_i@@，游戏 soundness 使两侧 junta 列表典型地落在不相交的投影纤维里，从而耦合下输出独立；于是每个二进偏差都被迫给小侧预算的尾和贡献一个固定正常数。所有估计针对同一分布下的同一随机变量，把全部 @@M@@M@@ 个尺度的贡献相加即超出预算，得出矛盾。
最后去权：把每个顶点代价上取整为 @@M@@\lceil Sw_v\rceil@@ 并克隆成相应大小的独立集，弧改为全连接。舍入使任何删除集至多多付一个单位，于是 YES: @@M@@\DFVS\le5S@@、NO: @@M@@\DFVS>DS=10AS@@，取 @@M@@k=5S@@ 即得 @@M@@A@@ 倍鸿沟。若要禁止反向弧，先把每条弧用私有顶点细分；反馈弧集版本则把每个顶点拆成 @@M@@v^-,v^+@@ 并配 @@M@@n+1@@ 条私有二长路，最优值与近似解同时保持。
本篇同属该结果族的直接归约支线：硬性起点是已发表的 2-to-1 游戏定理，既不假设 UGC，也与族内中心篇对 UGC 本身的证明相互独立，却共同刻画出同一批问题的最优近似阈值图景，与 Max-Cut、Vertex Cover、Min-UnCut 等姊妹篇互相支撑。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本篇主结果尚无 Lean 形式化证明，请以社区核验为准。
问 1：证明中最关键、也最脆弱的一步是什么？
答：第四步”跨尺度的公共尾变量”。矛盾要求把所有二进偏差（dyadic bias）上的贡献加进同一个关键性预算的尾和并超出其期望，这只有在每个估计都针对同一分布下的同一随机变量时才合法。引言明言：若在每个尺度单独给出影响力界，将无权把贡献相加；论文专门构造了与偏差无关的 pivotality 量 B(f) 来支撑这一相加——它是全文的承重梁。
问 2：为什么”共享前缀必须在抽约束之前固定所有顶点函数”这一假设不能松动？
答：因为 junta 坐标列表要拼成一个博弈标号（每个游戏顶点一个函数），必须让两侧函数在被测约束抽出之前就已确定；若函数随测试改变，坐标列表不再定义标号，解码无从谈起。同样，秩顶点代价 D+1=10A+1 大于 NO 侧预算 D，保证它们全部幸存，拓扑序才提供一致的比较位。
问 3：与已有工作相比真正的新意是什么？
答：”每个常数因子都难”此前只在 UGC 下成立（Guruswami–Manokaran–Raghavendra 一系、Svensson、Guruswami–Lee）；无条件纪录只有 Vertex Cover 迁移来的 10√5−21 与 two-to-1 线的 √2。本文以不完美完备性 2-to-1 博弈定理（DKKMS/KMS/BKS）为唯一硬度输入，用 Friedgut junta 定理替代 Svensson 的 IAOTIO 与 G–L 的不变性原理，无条件追平了 UGC 所许诺的结论。
问 4：这个结果最可能以什么方式出错？
答：典型风险有四处：Ramsey 加 minimax 的秩铺开要求任意三个位置的像分布几乎相同，”几乎”的容差直接决定比较一致的概率；耦合下两侧 junta 列表落在不相交投影纤维、输出独立，这一步把比较界搬到乘积测度；YES 侧指数 Markov 界逐族付账凑出总代价至多 4；去权时克隆独立集使任何删除集至多多付一个单位。论文未形式化，这些估计均未经机器核验。
问 5：起点为什么选不完美完备性的 2-to-1 定理而不是更新的完美完备性版本？
答：论文用的是其精确形式（定理 games）：对任意小常数 θ，区分值 ≥1−θ 与 ≤θ 是 NP-难的，且字母表固定、投影纤维恰好两个；引言明确说完美完备性 2-to-1 猜想不是论证前提。该形式已发表且无需附加假设，是能直接消费的最强无条件起点。
问 6：结论对算法研究意味着什么？
答：引言如实界定了边界：定理说明所需近似因子随输入规模无界增长（除非 P=NP），但不识别增长速率、也不改进 Seymour 的 O(log n log log n) 一般算法——对数因子与常数因子之间的精确差距仍是开放地带。
问 7：谁会用到它？
答：DFVS 与反馈弧集的近似算法研究者（Ghorbani–Mnich 2026 记录的缺口就此部分闭合）；排序与约束删除问题社区；以及把 UGC 条件结论逐个”无条件化”这一计划的整体图景。
总评
把一条 UGC 级结论无条件化，方法上以单一关键性预算跨尺度记账颇具巧思；最大风险是四步可靠性分析的长链条估计未经形式化，容差叠加处最易失守。