结果族 105：Perfect completeness for 2-to-1 games · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
想象一场巨型配对考试：左边一排答题人、右边一排审题人，每张考卷规定”审题人 a 的答案只能配答题人 1 或 2，审题人 b 只能配 3 或 4”——每个右侧答案恰好有两个候选。问：全对到什么程度？论文证明，判断”能否人人配对成功”还是”怎么做都至少九成配错”，与最难的 NP 问题一样难。
关键词卡片
看个具体例子
定理的数字版：取 @@M@@\delta=1\%@@——存在多项式时间变换，把可满足的 3-SAT 变成值为 @@M@@1@@（全部约束满足）的 2-to-1 博弈，把不可满足的变成值至多 @@M@@0.01@@ 的博弈，且区分二者是 NP-难的。注意”每个右答案恰有两个候选”的刚性：多一个少一个都会破坏证明结构，这正是它名字里”2-to-1”的含义。
为什么值得关心
这是 Khot 2002 年提出的 2-to-1 猜想的完美完备性版本，长期缺口被补上，而它正是图着色等一大片”近似也难”结论的钥匙。
已 Lean 形式化
第一级台阶
导读里那场”巨型配对考试”，对象是一个二部图式的约束系统：左边答题人、右边审题人，每张考卷是一张投影表——它规定左边的哪个答案算对。操作是给每个顶点各贴一个标签；一条边被满足，当且仅当右侧标签恰好等于左侧标签经该边投影表映出的像。整场考试的”值”是任何贴法能同时满足的边所占比例的上确界。
第二级台阶
用本科术语说，这是投影博弈（projection game）：有限二部多重图，每条边带映射 π_e，值定义为满足边比例的最大值。2-to-1 博弈要求左右字母表分别为 [2q] 与 [q]，且每条边的投影表中每个右答案恰好有两个原像。完美完备性指 YES 情形必须值为 1——存在一种贴法让每张考卷都判对；NP 难指区分”值为 1”与”值至多 δ”与 3-SAT 同级。
第三级台阶
定理的语境是逼近难度：对每个事先固定的有理数 δ，要造出多项式时间归约，把可满足的 3-SAT 变成值为 1 的博弈、不可满足的变成值至多 δ 的博弈。这里”恰好两个原像”是不可动摇的假设——普通并行重复会把二元素纤维膨胀成 2^k 个，破坏 2-to-1 结构，这正是此前二十年卡在近完美完备性端点的根源。结论是该归约存在且输出是显式无权边多重集与显式投影表，为下游一大片图着色与 PCP 不可逼近性结论补上缺失的前提。
证明了 Khot 的 2-to-1 博弈猜想（2-to-1 Games Conjecture）的完美完备性（perfect completeness）版本：对任意固定有理数 @@M@@\delta\in(0,1)@@，区分”完全可满足”与”值至多 @@M@@\delta@@“的 2-to-1 博弈是 NP 难的。这是逼近难度理论的基石结果。
2-to-1 博弈是一类投影博弈（projection game）：二部图每条边带约束映射 @@M@@\pi_e@@，左、右字母表为 @@M@@[2q]@@ 和 @@M@@[q]@@，每个右答案恰有两个原像。Khot 于 2002 年研究逼近难度（hardness of approximation）时提出该猜想，它蕴含大量图着色与约束满足问题的最优不可逼近性。Grassmann 纲领（Khot–Minzer–Safra 等）此前已证完备性 @@M@@1-\eps@@、可靠性任意小的近完美版本，但”完美完备性”端点——YES 实例须被全部满足——悬而未决：对恰二投影做普通并行重复会把二元素纤维膨胀成 @@M@@2^k@@ 个，破坏 2-to-1 结构。Austrin–O’Donnell–Tan–Wright 的完美完备性结果可靠性停在 @@M@@23/24+\eps@@；Fei–Minzer–Wang 只解决了 4-to-1 情形。
主定理：对每个固定有理数 @@M@@\delta\in(0,1)@@，存在只依赖 @@M@@\delta@@ 的整数 @@M@@q\ge2@@ 与确定性多项式时间归约，把 3-SAT 映到字母表为 @@M@@[2q]@@、@@M@@[q]@@ 的 2-to-1 博弈，使可满足公式产生值为 @@M@@1@@ 的博弈，不可满足公式产生的博弈值至多 @@M@@\delta@@；输出是显式列出的无权边多重集和显式投影表，每张表的每个右答案恰有两个原像。推论：最大 @@M@@k@@-可着色子图（maximum @@M@@k@@-colorable subgraph）在 @@M@@1-1/k+C\log k/k^2@@ 处 NP 难；并恢复 Håstad 关于可满足 Not-Two 谓词与三查询 PCP（可靠性 @@M@@5/8+\eps@@）的定理。
先用 Dinur 的完美完备性 PCP 与 Dinur–Steurer 并行重复，得到完备性为 @@M@@1@@、值任意小的子句—变量源博弈。再把其独立副本放到一棵有限树的叶上：叶上是答案域上全部 @@M@@\mathbb F_2@@ 值函数，内部节点取各子空间两两乘积张成的空间并展示数组（若干行函数）；全体数组的联合取值把定义域剖分成块，合法答案即一块，也就是能同时实现全部还原输出的赋值。测试时随机选一层与非零方向 @@M@@a@@ 取商：商核恰为 @@M@@\{0,a\}@@，每个右标签至多合并两块，天然得到”至多二”纤维；满足的源赋值满足全部约束，此即完美完备性。
若标记以 @@M@@\eps@@ 比例接受，配对计数给出同时成功的两层 @@M@@i<j@@。上层用逆 shortcode 定理（源于 Grassmann 图扩张），从秩一步游走下的表值相等中提取仿射切片（affine slice）上稠密的响应，联合折叠恒等式把它化为线性泛函 @@M@@z@@（@@M@@z(1)=1@@），其乘积型 @@M@@F(x,y)=z(xy)@@ 在展示行上的 Gram 矩阵秩至多 @@M@@1@@；右侧解码器靠 Fourier 重字符列表解码，两侧以正概率相等。难点是左形式的秩只在其依赖的被测行上检验：在纤维内重采样并借稀疏投影后验估计，把限制相等提升为完整相等，再用逆定理取出固定形式；固定的高秩形式在仿射切片上几乎不可能通过秩 @@M@@1@@ 检验，故正份额协议只能来自秩至多 @@M@@s@@ 的形式。最后”干净重复”论证让低秩形式在源叶诱导短奇列表、重建输入，与源博弈值 @@M@@<1/(2s^2)@@ 矛盾。组装时按依赖顺序选参数，把”至多二”补成”恰为二”，再把有理权重舍入为显式无权多重集，总可靠性不超过 @@M@@\delta@@。
主结果已由 OpenAI 完成 Lean 形式化证明（结果族 105 配套文档 lean/docs/105.md）。三个外部输入（Dinur PCP、Dinur–Steurer 重复、KMS Grassmann 扩张）均为社区已证定理；论文自证的采样比较、逆定理推广与干净重复引理是核验重点。本定理恰好补上 Guruswami–Sinop 与 O’Donnell–Wu 归约所需的”恰二纤维加完美完备性”前提，使上述推论无条件成立；同纲领姊妹篇另证得三着色图独立集的更强可靠性。按 OpenAI 官方声明，未经形式化的结果可能有问题，而本文主结果已形式化，可信度较高。
问 1：证明里最关键也最脆弱的一步是什么？
（答：左形式的秩只在其自身依赖的被测行上检验（引言 Proof overview 明言”The remaining difficulty”）。通过秩 1 检验不能立刻约束整体的秩；论文靠在低层省略方向纤维内重采样得到限制相等，再用稀疏投影后验估计把它提升为完整形式相等，第二次逆 shortcode 应用才把协议归到有界秩形式。这一”由局部秩推断整体秩”的提升链条是全文最细的地方。）
问 2：”恰好两个原像”这条刚性为什么去不掉？
（答：一是结构性障碍：对恰二投影做 k 次普通并行重复，每个右答案的原像变成 2^k 个，2-to-1 结构当场瓦解，所以可靠性放大必须靠树状构造与 {0,a} 商核实现；二是下游需求：Guruswami–Sinop 的归约正需要”恰二纤维+完美完备性”这个前提，”至多二”不够用，论文最后组装时还要专门把至多二补成恰为二。）
问 3：与已有工作相比真正的新意是什么？
（答：Austrin–O’Donnell–Tan–Wright 的完美完备性版本可靠性卡在 23/24+ε；Khot–Minzer–Safra 的 Grassmann 纲领只给出完备性 1−ε 的近完美版本；Fei–Minzer–Wang 只做了 4-to-1。本文首次同时做到：完美完备性、恰二纤维、可靠性任意小，且不带 Braverman–Khot–Minzer “Rich 2-to-1”那类额外条件。）
问 4：AI 生成证明最可能在哪里出错？
（答：三处高危。一是采样比较的全变差界：树外数组均匀、树内递归采样器每调用换新随机性、增加孩子数掩盖特殊路径孩子——任何一个分布近似失真，可靠性论证就漏气；二是参数须”按依赖顺序”选取，ε、q、层数互相嵌套，顺序一乱常数就矛盾；三是干净重复引理中”零事件与指定源对恰独立”（Lemmas clean-law 与 reconstruction）。主结果已 Lean 形式化，是主要减震器。）
问 5：外部输入可靠吗？
（答：三个外部定理——Dinur 完美完备性 PCP、Dinur–Steurer 并行重复、KMS Grassmann 扩张——均为社区已发表结果；论文自证的采样比较、逆 shortcode 估计与干净重复引理才是核验重点，其中逆定理还要求常数不依赖表格值域并能用于小商空间。）
问 6：谁会用到这个定理？
（答：立竿见影的推论有三条：最大 k-可着色子图在 1−1/k+C·log k/k² 处 NP 难（Guruswami–Sinop 前提补齐）；恢复 Håstad 关于可满足 Not-Two 谓词与三查询 PCP（可靠性 5/8+ε）的定理；经 Guruswami–Sandeep 找回”三着色 vs 非 c-着色”的硬度。姊妹篇再用它推进三着色图独立集硬度。）
总评
补上了 2-to-1 猜想悬置二十余年的完美完备性端点，且主结果已形式化，是逼近难度纲领的一块基石；最大风险藏在自证的采样与提升引理里——形式化覆盖的是主定理陈述，外围推论的常数组装仍需社区复核。