GPT-5.6 与 Fable 5 联手协助微软研究院首席研究员 Dimitris Papailiopoulos，成功攻克了一道悬置 25 年的无线通信数学难题。研究团队证明了一种多项式时间算法，能够在 MIMO 检测中精确命中最大似然阈值，将原本需要指数级时间的穷举搜索优化为高效计算。
作者透露，这一突破性的证明过程耗时整整七天。
MIMO（多输入多输出）检测是无线通信领域的核心问题，其目标是从被噪声干扰的信号中，完整还原发送端的原始信息。虽然统计上已知在特定信噪比下可恢复信号，但传统方法依赖穷举搜索，计算复杂度随比特数呈指数级增长。因此，学界长期致力于寻找一种无需穷举、能在多项式时间内实现精确还原的快速算法。
早在 2001 年，Hassibi 和 Vikalo 曾认为通过球形译码找到了突破口，但该结论于 2005 年被 Jaldén和 Ottersten 证伪。此后二十余年，学界尝试过半正定松弛、比特翻转局部搜索、AMP 及统计物理等多种方法，最佳结果仍停留在理论门槛的两倍之处，始终未能跨越这道鸿沟。
25 年困局：从 NP-hard 到理论阈值
MIMO 检测的本质是在接收端从混合了噪声的信号中，准确还原发送端发出的 N 个比特。理论上，“最大似然检测”能通过遍历所有 2 的 N 次方种组合找到唯一正确答案，但其计算量随 N 增大而指数爆炸，实际应用中不可行。
1989 年，Sergio Verdú证明了该类问题在最坏情况下属于 NP-hard。然而，现实无线信道具有随机性，并非刻意构造的“最坏情况”。因此，学界转向研究更具体的问题：在随机信道且统计上可恢复的前提下，是否存在非穷举的多项式时间算法？
研究确立了一条关键分界线：当信噪比达到 2logN 时，发送比特被完全恢复的概率趋近于 1，此即“最大似然阈值”。低于该阈值，即便是最大似然检测也会失效。核心挑战在于设计一种快速算法，使其性能精确匹配这一理论阈值。
2001 年提出的“球形译码”算法曾被视为希望，它通过限制搜索范围来压缩计算量。初看其期望复杂度为多项式时间，但 2005 年的研究证实，为保证捕获信号，搜索球半径需随规模扩大，导致内部候选数量仍呈指数级增长，该路径宣告失败。
随后出现的半正定松弛、AMP 等近似方法，虽各有建树，但均无法在严格证明下达到 2logN 的理论阈值。2020 年的"box relaxation"方法将门槛降至 4logN，但仍距理论极限有一倍之遥。二十五年来，“统计可恢复”与“算法可恢复”之间始终存在难以逾越的鸿沟。
如今，Dimitris Papailiopoulos 借助 GPT-5.6 和 Fable 5，证明了一个仅需两步的简单算法，能在信噪比等于 2logN 时实现精确恢复，且复杂度仅为 O(N³)。该研究同时证明了双向结果：算法在阈值处有效，而略低于阈值时，任何方法（包括最大似然检测）都将失效。
AI 辅助证明：两步算法的诞生
Dimitris 邀请 GPT-5.6 和 Fable 5 共同攻关。GPT-5.6 提出了基于 AMP 算法的路径，而 Fable 5 则建议使用“符号 LMMSE 加贪心逐位翻转”这一业界常用但未获严格证明的老算法。
最终，Dimitris 选择了 Fable 5 的路径，并由 GPT-5.6 负责修补证明中的漏洞。经过多轮迭代简化，去除了复杂的矩阵分析工具，形成了一份可逐行手算核对的证明。作者未采用 Lean 形式化验证，而是坚持人工验证以确保逻辑的可理解性与正确性。
该算法包含两个核心步骤：
第一步：LMMSE 取整
利用线性最小均方误差估计（LMMSE）生成连续的粗略猜测，并按正负号取整为+1 或 -1。证明显示，取整后的结果与真实比特的汉明距离仅为 o(N)，即随着 N 增大，错误比例趋近于零。
第二步：贪心逐位翻转
从第一步的结果出发，每轮检查所有比特，翻转能使代价函数下降最多的一位，直至无法改进。论文证明了两点关键性质：一是在误差范围内，总存在至少一位翻转能显著降低代价，确保算法不会陷入局部最优；二是代价函数随汉明距离增大而单调递增，形成天然护栏，防止搜索路径偏离。
综合推导表明，该贪心搜索的复杂度为 O(NlogN) 步。算法仅在完全匹配真实比特串时才会停止，从而完成了从统计可能性到算法确定性的闭环证明。
研究者背景
Dimitris Papailiopoulos 现任微软研究院首席研究员及威斯康星大学麦迪逊分校副教授，深耕信息论与编码理论领域。早在 2009 年攻读博士期间，他便尝试用 MCMC 方法解决 MIMO 检测问题但未果。十七年后，借助 AI 大模型的辅助，他终于解开了这道曾经困扰自己的难题。
