一道困扰无线通信领域 25 年的理论难题，最近被一位教授和两款大模型联手攻克。威斯康星大学麦迪逊分校教授、目前休学术假在微软研究院担任首席研究员的迪米特里奥斯·帕派利奥普洛斯（Dimitris Papailiopoulos），给出了一个多项式时间算法，让多输入多输出（MIMO）检测能够精确命中「最大似然阈值」。整个过程，他花了整整七天。

MIMO 是自 4G 以来几乎所有现代蜂窝通信标准的基础技术。发送端把 N 个比特通过一个 N×N 的信道发出，信道会把它们搅混并叠加噪声；接收端手里只有一份被污染过的信号，却要把原始的 N 个比特一位不差地还原出来。

一个卡了 25 年的理论目标

理论上存在一个万无一失的办法，叫最大似然（ML）检测：把所有 2 的 N 次方种比特组合都算一遍，找出与接收信号最匹配的那个。这种方法在数学上一定正确，但代价是指数级——N 稍微大一点，穷举就要算到天荒地老。

早在 1989 年，塞尔吉奥·贝尔杜（Sergio Verdú）就证明，这类问题在最坏情形下是 NP-hard 的，也就是说，无论用什么算法，都存在某些刻意构造的输入让计算量爆炸式增长。但「最坏情形」指的是数学上专门为难算法的信道矩阵；现实中的无线信道是随机产生的，不会挑最难的来考接收端。

于是从 2000 年代初开始，学界换了一个更贴合实际的问题：如果信道是随机生成的，只要统计上还存在恢复原始比特的可能，是不是就一定能找到不需要穷举的快速算法？后续研究给出了一条精确的分界线——当信噪比达到 2logN 时，原始比特能被完全恢复的概率趋近于 1；低于这条线，连最大似然检测本身都会开始出错。这条线因此被称为「最大似然阈值」。问题于是变得具体：能不能设计一个跑得快的算法，精确命中 2logN？

从穷举到 2logN 这道墙

过去 25 年里，一波又一波学者轮番上阵，却没人能真正翻过这道墙。

2001 年，哈西比（Hassibi）与维卡洛（Vikalo）认为球形译码能在期望意义下以多项式时间运行；但 2005 年，亚尔登（Jaldén）与奥特斯滕（Ottersten）证明，在任意固定信噪比下它依然是穷举级别的。此后学界又试过半正定松弛、比特翻转局部搜索、近似消息传递（AMP）、统计物理方法，每一种都能写出漂亮的分析，却没有一种被严格证明能精确匹配 2logN。2020 年，一种把离散问题放宽成连续优化来解的「盒式松弛」（box relaxation）拿到了当时最好的严格结果——能在信噪比达到 4logN 时做到精确恢复，正好是理论门槛的两倍。

两步算法，复杂度 O(N³)

帕派利奥普洛斯的新算法出奇简单，只有两步。第一步叫 LMMSE 取整：先用线性最小均方误差估计给出一个连续值的粗略猜测，再把每个坐标按正负号取整成 +1 或 -1。论文证明，取整结果与真实比特之间的汉明距离只有 o(N)——也就是说，随着 N 增大，猜错的比特占比趋近于零。第二步叫贪心逐位翻转：从第一步的猜测出发，每一轮找出翻转哪一位能让「代价函数」下降得最多，就翻转那一位并重复。

为了让贪心搜索不会中途卡死，论文证明了两件事：在正确解附近的一个范围内，每个还没猜对的点都至少存在一位翻转能让代价严格下降，且下降幅度有一个不趋于零的下限；同时，代价函数本身随汉明距离增大而增大，形成一道天然护栏，搜索无法翻越逃逸。两者合起来证明，贪心搜索只会在真实比特串处停下，总复杂度为 O(N³)。

这个结果还是双向的：一头证明算法能在 2logN 精确恢复，另一头进一步确认，信噪比只要略低于 2logN，连最大似然检测都会开始失败——阈值不是被「逼近」，而是被确认就是那堵墙。

30 分钟思路，7 天证明

大模型扮演了关键但不替代的角色。帕派利奥普洛斯让 OpenAI 的 GPT-5.6 和 Anthropic 的 Claude Fable 5 来试这道题，两个模型很快分别给出了证明思路：GPT-5.6 走的是近似消息传递（AMP）路线，Fable 5 走的是「符号 LMMSE 加贪心逐位翻转」这条业内实际在用、却从未被严格证明过的老算法。他最终选择了 Fable 的路线，再让 GPT-5.6 接手检查并修补论证中的漏洞，期间反复让两个模型互相简化彼此的证明，唯一底线是无论如何都要保住 2logN 这个门槛。

据他描述，核心的理论突破由 AI 在大约 30 分钟内给出，而完整的验证与证明撰写则耗费了整整七天，期间大量工作是为 AI 的思路补缺、纠错、把「符号墙」化简到能逐行手算核对。这项成果由一个攻读博士期间就盯上该题、十七年后才最终收尾的研究者完成，也折射出顶尖实验室里数学与工程研究正在发生的人机协作转向。

来源：Moneycontrol