克雷西 发自 凹非寺
量子位 | 公众号 QbitAI
本文经 AI 新媒体量子位（公众号 ID: QbitAI）授权转载，转载请联系出处
GPT-5.6 与 Fable 5 联手，协助微软研究院首席研究员 Dimitris Papailiopoulos 解决了一道悬置 25 年的数学难题。他证明了一个多项式时间算法，能让 MIMO 检测精确命中最大似然阈值。
作者表示，这一证明过程耗时整整七天。
MIMO 检测是无线通信领域的经典问题，核心在于接收端需从被噪声干扰的信号中，完整还原发送端原本发出的信息。
统计上该操作虽可实现，但传统方法依赖穷举搜索，时间复杂度呈指数级。因此，学界长期致力于探索能否利用快速算法，在不通过穷举的情况下实现信号还原。
2001 年，Hassibi 和 Vikalo 曾以为找到突破口，但 2005 年被 Jaldén和 Ottersten 证伪。此后，半正定松弛、比特翻转局部搜索、AMP 及统计物理等方法相继尝试，最佳结果仍停留在理论门槛的两倍之处。25 年来，众多学者轮番攻关，均未成功。
25 年来，只能靠穷举
MIMO 检测是无线通信的基础问题：发送端将 N 个比特通过 N×N 信道发出，信道会将比特混合并叠加噪声；接收端仅持有被搅乱的信号，需无损还原最初的 N 个比特。
理论上存在万无一失的“最大似然检测”法，即遍历所有可能的比特组合，找出与接收信号最匹配的一项。该方法虽能确保正确，但计算量随 N 呈 2 的 N 次方增长，稍大规模便无法在有限时间内完成。
1989 年，Sergio Verdú证明此类问题在最坏情况下属 NP-hard，即存在特定输入导致计算量指数级爆炸。然而，“最坏情况”通常指数学构造的极端信道矩阵，现实无线信道的衰减与噪声多为随机产生，并非刻意刁难。
因此，学界自 2000 年代初转向更具体的问题：若信道随机生成且统计上存在恢复可能，是否必能找到无需穷举的多项式时间算法？
研究确立了一条精确分界线：当信噪比达到 2logN 时，比特完全恢复的概率趋近于 1。低于此线，连最大似然检测也会失效，该分界线被称为“最大似然阈值”。核心问题随之明确：能否设计快速算法，精确命中该阈值？
2001 年，Babak Hassibi 和 Haris Vikalo 提出“球形译码”（sphere decoder）算法，试图通过在接收信号周围划定搜索范围来压缩计算量，并推导出其期望复杂度为多项式时间。若结论成立，难题即解。
然而 2005 年，Joakim Jaldén和 Björn Ottersten 推翻该结论，证明在任意固定信噪比下，为确保以非零概率覆盖信号，搜索球半径需随规模扩大，导致候选数量呈指数级增长，期望复杂度实为指数级。
此后，学界转向半正定松弛、比特翻转、AMP 等近似方法，虽各有分析成果，但均未被证明能精确匹配 2logN 阈值。2020 年提出的"box relaxation"方法虽将严格证明结果推进至 4logN，但仍为理论门槛的两倍。
25 年来，统计上的“可恢复”与快速算法的“可恢复”之间始终存在鸿沟。上周，Dimitris Papailiopoulos 联合 GPT-5.6 和 Claude Fable 5 填平了这一差距。他们证明，一个仅需两步的简单算法，能在信噪比等于 2logN 时精确恢复全部比特，且复杂度仅为 O(N³)。
该论文证明了双向结果：一方面，该算法在信噪比等于 2logN 时可精确恢复信号；另一方面，若信噪比略低于此阈值，即便是最大似然检测也会失效。
GPT-5.6 和 Fable 5 联手证明
Dimitris 邀请 GPT-5.6 和 Fable 5 尝试解题，两模型迅速给出不同思路。GPT-5.6 采用了 Dimitris 尚未完全掌握的 AMP 算法路径；而 Fable 5 则提出了“符号 LMMSE 加贪心逐位翻转”方案，这是一个业内常用但从未被严格证明的老算法。
两条路径均声称能在 2logN 信噪比下实现精确恢复。Dimitris 最终选择 Fable 5 的路径，并让 GPT-5.6 协助检查修补漏洞。修复后的证明虽逻辑严密，但充满了复杂的矩阵分析工具，难以直观理解。
随后几天，Dimitris 反复要求两模型互相简化论证，唯一底线是必须保住 2logN 这一门槛，且最终形式需让他能够看懂。他未采用 Lean 进行形式化验证，因不熟悉该工具且担心翻译过程引入新错误。
历经一周打磨，他最终获得了一份可逐行手算核对的证明。该算法核心仅含两步：
第一步：LMMSE 取整
LMMSE（线性最小均方误差估计）是信号处理中的标准方法，先给出连续取值的粗略猜测，再按正负号取整为 +1 或 -1。论文证明，取整结果与真实比特的汉明距离仅为 o(N)，即随着 N 增大，错误比特占比趋近于零。
第二步：贪心逐位翻转
基于第一步的猜测，每轮检查所有 N 个比特，翻转能使代价函数（衡量匹配度）下降最多的一位，并重复此过程。
为确保贪心搜索不陷入局部最优，论文证明了两点：第一，在猜测起点附近，每个未猜对的点至少存在一位翻转能使代价函数严格下降，且下降幅度有非零下界，保证搜索不会卡死；第二，代价函数随汉明距离增大而增大，形成天然护栏，防止搜索路径偏离过远。
综合上述两点，算法复杂度被计算为 O(NlogN) 步。由于护栏内任何未猜对的状态都能找到改进步骤，算法唯一能停下的时刻即是找到真实比特串之时。至此，证明完成。Dimitris 确认已全程验证该论证过程。
作者简介
Dimitris Papailiopoulos，现任微软研究院首席研究员及威斯康星大学麦迪逊分校电子与计算机工程系副教授，早年主攻信息论与编码理论。
2009 年，尚在博士一年级的他与导师 Alex Dimakis 合作发表首篇论文，尝试用 MCMC 方法解决 MIMO 检测问题但未获成功。17 年后，借助 AI 大模型之力，他终于解开了这道曾让自己受阻的难题。
参考链接：
https://x.com/DimitrisPapail/status/2086159964234482144