AI 协助破解无线通信领域 25 年悬而未决的理论难题

近日，一位研究者在 Hacker News 的 AI 版块发文，称借助两款 AI 模型（其称之为 GPT-5.6 与 Claude「Fable」）成功证明了一个在无线通信领域悬而未决 25 年的理论问题：只要完美检测在统计意义上可行，就一定存在多项式时间算法可以完成 MIMO 检测。这是自 2001 年 Hassibi 与 Vikalo 提出猜想以来，该问题首次得到完整解答。

问题背景：MIMO 检测的 NP 难题

MIMO（多输入多输出）是现代无线通信的核心技术之一。其基本设定是：发射端通过 N 根天线同时发送 N 个比特向量 x，信号经过 N×N 信道矩阵 H 混合并叠加高斯噪声后，被接收端的 N 根天线接收得到信号 y。接收方已知 H 和噪声统计特性，但不知道具体的噪声 w，需要从 y 中还原出原始比特 x。

理论上，最大似然（ML）检测器能给出最优解，其本质是求解一个离散最小二乘问题。然而 ML 检测在最坏情况下是 NP 难的——若要在全部 2^N 种可能的比特序列中穷举搜索，计算复杂度随 N 指数增长。

学界真正关心的问题是：当信道具有随机性而非最坏情况时，是否存在更高效的算法？

25 年的研究脉络

• 2001 年：Hassibi 与 Vikalo 首次论证「平均情况下存在多项式时间解」的希望。他们分析的对象是 1985 年由 Fincke 和 Pohst 提出的「球形译码」（Sphere Decoder）算法，并推导出其期望复杂度的表达式，看起来像多项式。
• 2005 年：Jaldén 与 Ottersten 推翻了这一乐观结论，证明在任意固定 SNR 下，球形译码的期望复杂度实际随问题维度指数增长。

此后，研究方向转向 ML 检测的近似算法（如半正定松弛等），但精确且高效的多项式时间算法始终未能出现。该问题在不同数学语境下也有等价表述，包括 CDMA 多用户检测、整数最小二乘、格中最近向量等。

这次的新结果

关键阈值是 SNR = 2 log N。早在 2000 年代学界就已知道：当信噪比不低于 2 log N 时，完美检测在信息论意义上是可能的（成功概率趋于 1）；低于此阈值（差一个 loglog N 项）则成功概率趋于 0。

但此前唯一能触达该阈值的算法是穷举搜索，复杂度为指数级。

此次的新证明表明：当 SNR 达到 2 log N 时，存在简单的多项式时间算法可以成功还原全部 N 个比特。 也就是说，只要统计意义上可解，就能高效地解。

研究者表示，GPT 用了约 30 分钟生成初始证明，但他又花了 5 天以上时间反复与模型交互，逐步简化和润色证明过程，使其从「绝对混乱」的初稿变成「相对初等」的成稿。他声称已对证明进行了完整核查，并认为其正确。

意义与局限

该结论对 MIMO 检测及相关数学问题具有理论参考价值。不过作者也承认，通信领域对这一具体子问题的研究热度已不如从前，产业实践中也早已通过近似算法与新编码方案绕过了这一瓶颈。

更具普遍意义的或许是这次协作过程本身所展示的能力：AI 不仅能在半小时内给出潜在证明框架，还能与研究者经过多轮迭代，将冗长晦涩的数学推导打磨为清晰可读的形式。这也是 AI 在长期悬而未决的理论问题上发挥实质作用的又一个案例。