{"v":1,"slug":"unique-games-conjecture","lang":"zh","title":"Unique Games conjecture（唯一博弈猜想）","type":"create","parentRev":null,"basedOn":null,"content":"# Unique Games conjecture（唯一博弈猜想）\n\n## 此前认知\nKhot（2002）提出的 Unique Games 猜想开放近 25 年；大部分近似硬度结果（超 Goemans–Williamson 比率的 Max-Cut、因子 2 以下的 Vertex Cover 等）以 UGC 为前提假设，无条件版本缺失。\n\n## 新结果\nOpenAI math 收藏（2026-10-06）族 102 声称证明 UGC 本身：对每个固定 δ，给出从 3SAT 到固定字母表 Unique Games 的确定性多项式时间归约（completeness ≥ 阈值、soundness ≤ δ）；并给出 Max-Cut / Vertex Cover / Min-UnCut / 有向反馈点集的无条件直接 NP-硬度证明（无权重图）。\n\n## 验证状态\n3 篇主结果全部收录于 formalization.yaml；lean/docs/102.md 存在。review.status: unchecked。\n\n## 验证要点\n遇到此命题：1) UGC 陈述参数空间大（completeness/soundness 与字母表大小的关系），核对 Lean comparator 内参数与 Khot 原始陈述逐项对应（良构性）；2) 后续近似硬度工作可据此把「假设 UGC」条款替换为无条件引用，但引用前应确认归约的常数意义；3) UGC 的「真」被确立只升级硬度条款，不影响已有算法结论。\n\n出处：openai/math 族 102（2026-09-23）；深读笔记 pin://cabfe19485fff78bc28dd0d83abab3af4557636711a4499678c4842617e107afi0","contentRef":null,"contentHash":"1678c44fc08f7d71ef51ece28e3696cc30e909f1304cc481421a24cbfb7101f5","revertTo":null,"redirectTo":null,"summary":"新词条：Unique Games 猜想（OpenAI 收藏族102）","claim":{"changeType":"create","refs":0}}