上周，GPT-5.6 和 Claude Fable 似乎解决了一个无线通信领域的开放性理论问题。这个问题在 2000 年到 2010 年代之间被深入研究过，而我作为一位焦虑的博士一年级学生也曾短暂接触过它。答案终于出现了，也许是因为我是最后几个提出这个问题的人之一，也是第一个促使机器去解决它的人 😊
结果： 你通过一个 N×N 高斯无线信道发送 N 个比特，接收端必须精确恢复所有比特。自 2000 年代以来，人们就知道当信噪比至少为 2 log N 时，这在信息论上是可行的。但唯一已知能达到该阈值的算法是指数搜索算法。而现在的证明表明，一个简单的多项式时间算法可以在完全相同阈值下成功。
让我再多讲一点。
2009 年，我和 Alex Dimakis（@AlexGDimakis）合作了我的第一篇论文，他很快成为了我的博士导师（并不是因为那篇论文）：
那篇论文是众多试图为 MIMO 检测提供多项式时间解决方案的尝试之一。
你可能会问，什么是 MIMO 检测？
发射器通过一个具有 N 个发射天线和 N 个接收天线的无线信道发送一个 N 比特向量。信道将比特全部混合在一起并加入噪声。接收端已知信道矩阵，必须确定发送的是哪些比特。
块错误最优接收机，也就是最大似然（ML）检测器，通过找到在给定接收信号下最有可能被发送的向量来精确解决这个问题。在这种情况下，ML 检测归结为求解这个基本的离散最小二乘问题：
不幸的是，就像生活中所有好问题一样……ML 检测是 NP 困难的。
然而我们并不是 TCS 悲观主义者，无线信道也不是最坏情况的，它们是随机的，而且这个社区从 2000 年代初就开始研究以下问题：
当恢复发送的比特在统计上可能时，我们能否在多项式时间内做到？
我们在上面那篇 2010 年的论文中并没有在这个问题上取得太大进展，尽管该领域有大量工作，但据我所知，这个问题自 2001 年 以来一直是开放的……也就是四分之一个世纪，说得更戏剧化一点。
直到上周。最终答案是
是的！只要完美检测在统计上是可能的，你就可以在多项式时间内做到。
MIMO 解决了；搞定。
但谁在乎呢？我们稍后回到这个问题。
我附上了论文，并且花了 5 天多的时间与模型反复沟通，来简化证明和阐述（原本简直是一场灾难），这个过程比 GPT 最初生成证明（大约花了 30 分钟）要长得多。证明很长，但相对基础。我已经尽我所能核对了所有内容，它是正确的。
现在让我再多谈谈这个问题及其历史，以及为什么我认为即使该领域已经从 MIMO 检测理论的这个特定角落转移了，它仍然值得写下来。
问题设定
所以你发送一个二进制向量 x ∈ {±1}^N，并接收
y=SNRNHx+w
其中 H 是 N×N 的，H 和 w 的所有元素都是独立同分布 N(0,1) 的。接收端知道 H 和噪声统计，但不知道 w，并且想要从 y 中恢复 x。恢复问题的块错误最优解等于
顺便说一句，这个优化问题还有很多不同的名称：MIMO 检测、CDMA 多用户检测、整数最小二乘、格中的最近向量问题，等等等等。
当 SNR = ∞（即有效噪声为 0）时，问题变得平凡：信道矩阵 H 以概率 1 可逆，所以你求逆并 inv(H)*y 就能精确恢复 x。在另一个极端，当 SNR = 0 时，你无法从噪声中检测出任何东西，ML 检测会失败。
但在 0 和无穷大之间的某个位置，ML 检测会成功，精确地说是在 SNR = 2 log N 处。这意味着解决上述优化问题可以让你以趋近于 1 的概率完美恢复发送的 N 比特序列的所有比特，而低于该阈值（直到加性的 loglogN 项），块恢复概率趋近于 0。
所以在 2logN 以上，发送的信号是 ML 优化问题的一个最优解，但解决它似乎需要对所有可能的 N 比特序列进行穷举搜索。所以我们现在关心的问题是：
当 ML 成功时，多项式时间算法能否恢复发送的 x？
**
一段带点戏剧性的简短历史
整数最小二乘问题的可解性问题至少可以追溯到 1989 年，当时 Verdú 证明了 它在一般情况下是 NP 困难的。但 NP 困难是最坏情况的陈述，而我们的实例不是。
Hassibi 和 Vikalo 在 2001 年 是第一个——据我所知——论证平均情况下存在多项式时间解的希望的人。他们分析的算法是当时流行的方法——Sphere Decoder（球面解码器，SD），其历史可以追溯到 Fincke 和 Pohst 1985 年。Sphere Decoder 特别受关注是因为：1) 它是一个精确的 ML 算法，即总是输出最小化器；2) 在实践中它似乎比指数时间快得多。
所以希望在于可以证明 SD 在多项式时间内运行。这就是 H&V 在他们的论文中阐述的内容：他们推导了一个 Sphere Decoder 期望复杂度的公式，对信道和噪声取平均，并表明它看起来是多项式的。如果这是真的，问题就解决了。这似乎是一个令人难以置信的结果。
然后 Jaldén 和 Ottersten 在 2005 年表明这种渐近解释并不完全正确：在任何固定 SNR 下，无论多大，sphere decoding 的期望复杂度实际上关于问题维度是指数的。
所以既然精确且快速的方法行不通，该领域花了大量精力研究 ML 优化问题的近似方法。出现了具有近似保证的半定松弛 和高 SNR 下的紧性条件，但没有尖锐的阈值。比特翻转局部搜索 在模拟中似乎与 ML 匹配，但没有完全证明匹配 ML 恢复阈值。AMP 文献 严格刻画了固定 SNR 下的每比特误差，而在该情况下块恢复是不可能的。统计物理学使用复制级论证产生了预计可以追踪精确 ML 的多项式时间方法，但据我所知，没有证明。而 2010 年与 Babak 和 Alex 合作的论文分析了一种 MCMC 方法，证明了混合后平稳分布在正确解上放置了非消失的质量，但没有证明任何关于混合时间的内容，而这正是困难的部分。
在我看来，在所有这些年里，恰好只有一种多项式时间方法 在任何 SNR 尺度下都有严格的块恢复保证：2020 年的盒子松弛，被证明当 SNR 按 4 log N 缩放时可以恢复块，并且可证明在低于该值时不行。顺便说一句，有点有趣的是，分析这种技术所需的概率工具在 2010 年代末才成熟，而这大部分时间是在该社区已经转移和分散之后。
而从那以后……没有太多活动了。
所以长话短说，ML 能达到的和任何多项式时间方法能可证明达到的之间的差距从未被弥合。
**
GPT 和 Claude 做了什么，以及我们如何得到一个我 Dimitris 能够验证的证明？
受到前沿模型在困难数学任务上最近的不合理的成功 的激励，我决定回到那些在我研究生时期困扰我的问题（我曾经研究信息论和编码理论），并开始把死星对准它们。这就是向 GPT 提出困难的数学问题并获得零样本解答的确切感受：
GIF
但我知道这里有个问题。即使我对我提出的任何问题都得到了完整的答案，如果我想要更广泛地分享它，我就会受制于必须验证它。第一，因为如果结果是错误的，我不想让自己难堪；第二，因为分享本来就是提问和做科学的主要原因。
所以，我决定挑选一个在我博士早期困扰我的、看起来最有雄心的、陈述清晰简洁且仍然开放的问题。于是，我问 GPT-5.6 和 Claude Fable 5：ML MIMO 检测什么时候可以在多项式时间内解决。
两者都为不同的算法给出了证明，并自信地表示：没有差距！存在一个多项式时间算法，在 SNR 高于 2 log N 时成功，精确匹配（直到加性的 loglog 项，但谁在乎呢）ML 恢复阈值。
但有一个小问题 😊 GPT 的算法是 AMP 变体。而我非常讨厌 AMP，因为我无论如何都无法理解它的任何分析。所以我让它尝试证明同样的结果——如果可能的话——用一个更简单的算法。确实，GPT 生成了另一个算法，我也觉得它违反直觉，而且我从未见过有人用过它！
另一方面，Fable 提出了一个我真的很喜欢的东西：
有符号 LMMSE，然后贪心比特翻转。一个在过去被提出并实际使用过的算法。
但还有另一个问题！根据 GPT 的说法，Fable 的证明大部分是错误的……但是可以挽救。所以我决定坚持使用 Fable 提出的算法，并让 GPT 接手 Fable 的证明并修复它。它做到了！
但还有一个问题，这个新证明完全不可读：一堵符号墙，变量指向变量，变量指向变量的比率，而这些比率又定义了其他变量，还有奇特的矩阵分析和概率工具，以及让我浑身起鸡皮疙瘩的 Marchenko–Pastur 相关的东西，以及其他美好的事物。
所以在大约 4-5 天里，我一直在两个模型之间来回穿梭，让它们为证明所需的每个大组件提供最傻瓜化的步骤集。我明确告诉它们，界限和常数变差是可以接受的，只要 2 log N 阈值保留就行，一切都是为了简单。
我想要的只是一个让注意力短暂的老恐龙能够不哭着消化的证明。
我实际上让 GPT 和 Claude 把我抱怨最多的消息分享回来了，哈哈
我最喜欢的：
为什么我坚持要超级简单的步骤？因为我想自己从头到尾验证它。不，我不想用 Lean，它 DOES NOT 解决我的问题。形式化验证只是把抽象级别移到了别处！！你仍然需要验证引理的英文是否能忠实地翻译成 Lean，而这是一种我不理解的语言。
算了吧。我不喜欢 Lean，抱歉。
但我确实理解基本的线性代数和概率，我信任自己验证这种步骤的能力。所以这就是我要求的证明级别。
然后花了多天的提示、提示、再提示，模型们在互相简化对方的论证，而我一直抱怨和拒绝任何我无法理解的内容。
最后它成功了！我们最终得到了一个我完全理解的证明，而且我现在已经逐行检查过了。
证明这个东西花了 30 分钟，而让它变得对我可验证花了大约 5 天。这个比例有点疯狂，但事实就是如此。结果：一个简单的算法在最大似然可行的情况下，在多项式时间内有效。这个问题不存在计算-统计差距。
BOOM！
**
证明的高层思路是什么？
这个算法简单到几乎令人尴尬。但为什么它有效呢？LMMSE 后接取整，在汉明距离上让你到达距发送信号仅一个可忽略比例的位置，即距真实值 o(N)。
然后，贪心比特翻转不会卡住，因为每步下降收益（即代价改善了多少）由高斯量控制，而它们的均匀集中性保证了某个球内的每个非真实值向量都提供一个有保证大小的严格改善的比特翻转。这意味着无论你做什么，你都会得到一个严格大于零的改善量。
然而，在每一步贪心都改善代价，并不意味着每一步与真实值的汉明距离都在改善。事实上，它可能会暂时变得更糟。但不会更糟太多，因为代价函数会随着你增加与真实值的汉明距离而增长。这意味着任何足够远的点的代价都远高于算法开始时的代价，而一条只减少代价的路径永远不会到达那里。贪心可以在汉明距离球内游荡，但它被一个"代价屏障"约束着，使它的路径保持在球内。
所以 1) 每一步都会将代价改善一个远离零的量，2) 起始代价并不比最优值高多少。因此，贪心运行最终必须停止，而将这两个量相除，就得到了它需要的步数，即 NlogN。
此外，贪心不可能在除真实值之外的任何地方结束：在球内的每个其他点，仍然有一些比特翻转可以提供改善，而算法不允许在那里停止。唯一可能停止的地方就是发送的向量。
下面是这个关键论证的一个很好的可视化描述：
这重要吗？
无线社区已经转移了，我也是。但这确实是一个重要的问题。我可以推测这个结果在 2010 年前后意味着什么：一个 ISIT 或 CommSoc/IT Society 最佳论文奖，也许还有 MIT、Berkeley 和 Stanford 的面试。我可以自信地说，作为一个博士生，那将是一个圣杯级的结果，也是我短暂的信息论职业生涯中的高光时刻。
然而……这个领域已经在很大程度上转移了 😊
有大量的类似问题曾经很重要，整个社区花了几十年研究它们。然后随着研究领域的转移慢慢变得不重要了，它们就这样被搁置着，保持开放，无人问津——不是因为它们不可能，而是因为人们慢慢不再关心了。
所以，当人们说"被 AI 解决的 N 年旧问题"时，我会试着解读它真正的含义。
然而，这一切中有一点非常酷：你现在可以回到那些你年轻时关心的问题，把死星对准它们。那些在整个研究社区的全部力量下坚守阵地的问题，现在正安静地、毫无防备地坐在文献宇宙一个被遗弃的角落里，等待着死星向它们开火；而这一切的成本是 200 美元/月。
疯狂的时代……
无论如何，我会把当前草稿 发到 arXiv，但不确定是否会投稿到某个会议或期刊（甚至不确定现在哪个合适）。我也不想浪费任何人的时间。但如果你读了它并发现错误，我很想听听。😊
所以现在我们知道：
MIMO ML 检测在任何可能的时候都是简单的！
万岁……
**
附录
关于上述证明，有一点值得注意：没有发明任何新的数学。
没有 2010 年时不存在的新不等式、新技术或新数学对象。证明很长，但它是基础的，所以它的难点不在于概念性，而在于需要花力气在正确的粒度、正确的时间把二十页标准步骤组合在一起，让它们完美地咬合。
我认为如果我们将这个想法更进一步，它在一定程度上定义了一类问题：解决它们不需要任何新的数学，只需要将已知的想法组装在一起，用比任何人愿意花费的更多的 token 或时间的长字符串串联起来。这些问题很快就会倒在 AI 面前，因为不断尝试大量东西直到某个东西奏效正是 AI 最擅长的。而且，也许"没有人把已知的方法坚持尝试足够久"这句话适用的开放问题比我们想象的还要多。
接着这个想法，这里有一个思想实验：假设你可以把 GPT-5.6 或 Fable 带回 2005 年，相同的 RL 算力，但预训练数据只到当时为止。它们还能解决这个问题吗？
我不知道，反事实很难推演。但即使许多工具在 2005 年可能已经存在，模型"感觉正确"地选择哪种技术的"拉力"可能很大程度上取决于某个方法的流行程度，以及我们的集体直觉——正如一个想法在特定上下文中被使用的频率所记录的那样。2005 年的预训练模型可能会挣扎，不是因为缺乏 RL 算力，而是因为缺乏预训练带来的、朝向正确想法集合的牵引力。这意味着这些模型比数学真理的神谕要有趣得多。我们或许应该把它们看作我们日积月累的直觉的提炼，再经 RL 进一步磨砺。
最后一个想法，我就此结束：
假设我可以穿越回过去，告诉我 2009 年焦虑的自己："兄弟，淡定，你将在 17 年后参与解决 ML MIMO 检测的可解性问题"，仅此而已。过去的我一定会彻底疯掉，试图弄清楚自己是怎么做到的，他会得出当时唯一合理的结论：我一定在信息论领域又待了十五年，很可能在 MIMO 检测上苦干，或者最乐观的情况是整数优化，并且在某个地方、以某种方式、大约在 2026 年，二元最小二乘终于在我巨大智力的重压下崩溃。
该死……那种先验的骄傲感啊。
要是小 Dimitris 知道那个宇宙和我们当前宇宙的比特之间的汉明距离是巨大的，而为此我们要感谢另一个叫 ML 的东西的突破就好了……
