文章摘要
微软首席研究员 Dimitris Papailiopoulos 携手大语言模型 GPT-5.6 与 Claude Fable 5，耗时七天攻克了困扰学界 25 年的无线通信难题。该研究仅用两步简单算法，首次在信噪比为 $2\log N$ 时精准匹配最大似然阈值，且复杂度降至 $O(N^3)$，填平了信号恢复与快速算法间的理论鸿沟。

微软研究院首席研究员Dimitris Papailiopoulos与大语言模型GPT-5.6、Claude Fable 5合作，耗时七天解决了困扰学界二十五年的无线通信经典数学难题，首次实现了在信噪比达到2logN时精准还原原始信号，完美命中最大似然阈值，且算法复杂度仅为O(N³)。

在现代无线通信系统中，发送端会通过N×N的信道同时传输N路比特信号，但信道会将各路信号相互混叠，同时引入随机噪声，接收端最终拿到的是一份被干扰后的混合信号，需要从中完整还原出发送端最初发出的每一位原始比特。理论上存在一种万无一失的方法，也就是最大似然检测，通过枚举所有2^N种可能的比特组合，找到与接收信号匹配度最高的结果，但这种方法的计算量会随着N的增大呈指数级增长，一旦N稍大，计算就会变得几乎不可能完成。

1989年，Sergio Verdú证明了这类问题在最坏情况下属于NP-hard问题，也就是说存在某些刻意构造的信道矩阵，会让任何算法的计算量都呈指数级爆炸。不过现实中的无线信道都是随机产生的，并不会专门为难接收端，因此学界从2000年代初开始提出一个更具体的问题：如果信道是随机的，只要统计上存在还原原始信号的可能，是否一定能找到不需要穷举的快速算法？

后续研究找到了一条精确的分界线——当信噪比达到2logN时，发送的比特能够被完全恢复的概率趋近于1，低于这个阈值时，哪怕是最大似然检测本身也会开始出错，这条分界线因此被称为最大似然阈值。学界的目标就是设计出能够精确命中这个阈值的多项式时间算法。

2001年，Babak Hassibi和Haris Vikalo提出了球形译码算法，通过划定搜索球来压缩候选范围，当时他们推导出的结论显示该算法的期望复杂度是多项式级的，看起来解决了问题，但2005年Joakim Jaldén和Björn Ottersten推翻了这一结论：为了以足够高的概率将发送信号包含在球内，球的半径需要随着问题规模N的增大而变大，这导致球内需要搜索的候选数量依然呈指数级增长，球形译码的实际复杂度依旧是指数级的。

此后学界尝试了半正定松弛、比特翻转局部搜索、AMP、统计物理方法等多种近似方案，每一种都能给出不错的分析结果，但没有一种被证明能够精确匹配2logN的最大似然阈值。直到2020年，一种名为box relaxation的方法将离散问题放宽为连续优化问题，拿到了当时最好的严格证明结果，能够在信噪比达到4logN时实现精确恢复，但这依然比理论门槛高出一倍。二十五年间，一波又一波的学者轮番上阵，始终没能填平“统计上可恢复”与“快速算法可恢复”之间的鸿沟。

本次突破的核心算法

上周，这条长达二十五年的鸿沟终于被填平。Dimitris Papailiopoulos与GPT-5.6、Claude Fable 5合作证明，一个仅包含两个核心步骤的简单算法，就能在信噪比等于2logN时精准恢复全部比特，且算法复杂度仅为O(N³)。这项研究还给出了双向的严谨证明：一方面证明了该算法能够在信噪比达到2logN时实现信号的精确恢复，另一方面进一步证明，只要信噪比略低于这个最大似然阈值，哪怕是传统的最大似然检测方法也会开始失效，这也验证了该阈值的精确性。

拆开来看，这个算法只有两个核心步骤。第一步是LMMSE取整，也就是线性最小均方误差估计，先通过标准的信号处理方法得到一个连续取值的粗略猜测，再将每个坐标按照正负号取整为+1或-1。论文证明，取整后的结果与真实发送的比特之间的汉明距离仅为o(N)，也就是说随着N的增大，猜错的比特数占总比特数的比例会趋近于零。

第二步是贪心逐位翻转，从第一步得到的猜测结果出发，每一轮检查所有N个比特，找到翻转哪一位能够让衡量匹配程度的代价函数下降最多，就执行该翻转，随后重复这一过程。

很多人会好奇，这样的贪心搜索会不会中途卡在某个错误的局部最优解中无法前进？为了回答这个问题，论文证明了两个关键结论。第一，在猜测起点周围的一个范围内，每一个还没有完全猜对的点，都至少存在一位翻转能够让代价函数严格下降，且下降的幅度有一个不会随着N变大而消失的下限，这意味着贪心搜索永远能找到继续优化的步骤，不会陷入停滞。第二，代价函数本身会随着汉明距离，也就是猜错的比特数的增大而增大，这形成了一道天然的“护栏”：哪怕搜索过程中某一步猜错的比特数量暂时变多，代价函数也无法回到起点，更不会翻越护栏跑到猜测范围之外。

将这两个结论结合起来，通过计算每一步代价下降的幅度和总代价差，就能得到贪心搜索的复杂度为O(NlogN)步，加上前期的LMMSE取整步骤，整体算法复杂度为O(N³)。贪心搜索的停止规则是找不到任何能让代价下降的翻转，而根据前面的证明，只要还没有猜对正确的比特串，就一定能找到可以优化的翻转步骤，只有当算法完全还原了真实的比特串时，任何翻转都会让代价函数变差，此时算法才会停止，也就是说，这个贪心搜索唯一能停下的地方就是真实发送的比特串，整个证明过程也因此严谨闭环。

合作与验证过程

Dimitris表示，整个合作过程耗时整整七天。最初他邀请GPT-5.6和Claude Fable 5尝试解决这道难题，两个模型很快分别给出了各自的证明思路。GPT-5.6采用了AMP算法的路径，这是Dimitris一直没能完全吃透分析方法的一类工具；而Claude Fable 5给出的路径则是业内实际已经在使用、但从未被严格证明过的“符号LMMSE加贪心逐位翻转”方案。

两条路径都各自给出了完整的证明，声称能够在信噪比2logN时实现精确恢复。Dimitris最终选择了Claude Fable 5的方案，并让GPT接手修补证明中的漏洞。GPT修复了漏洞，但修复后的证明充满了复杂的符号和矩阵分析工具，形成了一堵“符号墙”，Dimitris完全无法理解。接下来的几天里，他反复让两个模型互相简化对方的论证，唯一的底线是无论如何简化，都必须保住2logN这个核心阈值，除此之外，只要最终的证明能够被他亲手逐行验证，怎么修改都可以。

他还拒绝了使用Lean进行形式化验证，原因很简单：他不懂Lean。Lean是一种能够让计算机自动检查数学证明是否成立的工具，但使用它需要先将证明翻译成Lean能够识别的形式语言，而这道翻译工作本身也可能出错，由于Dimitris不懂Lean，他无法验证翻译的正确性。最终，经过一周的折腾，他终于拿到了一份可以逐行手算核对的严谨证明。

研究者背景

Dimitris Papailiopoulos目前是微软研究院的首席研究员，同时兼任威斯康星大学麦迪逊分校电子与计算机工程系的副教授。他早年的研究方向是信息论和编码理论，2009年还在读博士一年级时，他就写下了第一篇论文，尝试用马尔可夫链蒙特卡洛（MCMC）方法解决MIMO检测问题，但最终没能成功。十七年前那道让他卡住的难题，如今终于被他自己解开，而这次的突破，离不开大语言模型的助力。

参考链接：
https://x.com/DimitrisPapail/status/2086159964234482144

以上内容不代表本平台立场，仅供读者参考