GPT-5.6与Fable联手攻克25年数学难题
微软研究员与AI模型合作解决了长期悬而未决的MIMO检测复杂度问题，将可达信噪比推进到理论极限。
MIMO检测（多天线无线通信中从噪声信号恢复原始比特的问题）的最大似然阈值，理论上是2log N，但此前所有算法只能达到4log N。微软研究院Dimitris Papailiopoulos与GPT-5.6和Fable合作，证明了一个简单的两步算法能在2log N下精确恢复，填补了25年空白。
正文摘录
微软研究院首席研究员 Dimitris Papailiopoulos，证明了一个多项式时间算法，能 让 MIMO 检测精确命中最大似然阈值 。 MIMO 检测是无线通信领域的一个经典问题，需要 接收端从被噪声搅乱的信号中，把发送端原本发出的信息完整还原 。 2001年，Hassibi 和 Vikalo 以为找到了突破口，但 2005 年这条路又被 Jaldén 和 Ottersten 证明走不通。 此后学界又先后试过半正定松弛、比特翻转局部搜索、AMP、统计物理方法，最接近的结果也只能停在比理论门槛高一倍的地方。 发送端把 N 个比特通过一个 N×N 的信道发出去，信道会把这些比特混在一起，还会叠加噪声； 接收端手里只有一份被搅乱过的信号，要把发送端最初发出的 N 个比特，一位不差地找回来。 理论上有一个万无一失的办法，叫 最大似然检测 ，也就是把所有可能的比特组合都算一遍，找出跟接收到的信号最匹配的那一个。 这种方法一定能找到正确答案，前提是你愿意等——N 个比特意味着 2 的 N 次方种组合，N 稍微大一点，穷举就要算到天荒地老。 1989年，Sergio Verdú 证明了 这类问题在最坏情况下是 NP-hard 的 ，也就是不管用什么算法，都存在某些输入让计算量指数级爆炸。 现实里的无线信道不是谁刻意构造的，它的每一次衰减、每一次噪声都是随机产生的，不会挑那些最难算的情况来为难接收端。 如果信道是随机产生的，只要统计上存在恢复原始比特的可能，是不是就一定能找到一个不需要穷举的算法？ 后来的研究给出了一条精确的分界线， 当信噪比达到 2logN，发送的比特能够被完全恢复的概率趋近于 1 。 低于这条线，连最大似然检测本身都会开始出错，这条分界线因此被称为 最大似然阈值 。