AI 把两个几十年的算法指数挪动了

3SUM 达到亚二次、APSP 达到亚三次,两个老猜想被推翻。

白板上的推导

一句话:这不是跑分,是动了教科书

一句话:这篇论文证明,两个被老算法界当成铁律的猜想是假的。据转述该论文的报道,Claude 参与了发现的算法,在 3SUM 上给出 O(n^1.9992),在 APSP 上给出 O(n^2.9995),都是真正意义上的、面向指数的多项式改进。

划重点,这里不是把常数抠快几个百分点。3SUM 和 APSP 是复杂度理论里两个被默认了几十年的下界猜想,无数算法都踩着它们做归约。如今这两块招牌,被这次的结果直接摘了下来。

我的判断是,这类进展真正的分量不在那几个数字,而在它动摇了复杂度理论里两块被踩了几十年的地基——指数一旦动了,教科书上的划线就得跟着改。

说白了,跑分拼的是几个百分点的常数,这次改的是指数本身。前者是调参,后者才算真正动了教科书。

算法与图

3SUM 和 APSP 是什么

3SUM 是最经典的三数之和问题:给你一堆数,问有没有三个数加起来恰好等于零。朴素做法要三层循环,复杂度是 O(n^3),数据量一上来就彻底吃不消,只能换思路。

几十年前有人把它压到接近 O(n^2),于是立起 3SUM 猜想:理论上不存在真正亚二次的算法,那笔平方账拨不下去。这些年无数归约都默认这条成立,始终没人能推翻它,它就这样稳稳躺了二十年。

APSP 是同一套逻辑:给一张图,算出任意两点之间的最短路径。经典做法 O(n^3),沿类似思路一路压到贴近三次方,于是又立起一个对应的亚三次下界猜想,同样是行业公认的经验线。

这两个猜想常被拿来做归约的地基:想证明另一个问题有多难,先把它归约到 3SUM 或 APSP 头上,难度就跟着转移过去。地基一旦松动,上面砌的所有东西都得回头重新检查一遍,工作量不小。

下降的曲线

那两个指数是怎么被压下去的

这篇论文据称靠的是更精细的中间结果组合加上新的归约路径,把平方和三次的位置一点点挪动,最后落在 1.9992 与 2.9995。具体的每一步怎么拼,报道只给了相当大的轮廓。

据转述该论文的报道,关键在把已知子过程的开销重新计价、重排先后顺序,让整体指数往下沉一小节。数学上每一步都不算大,可一旦把几百处这样的改动叠起来,就成了那根刺破边界的线,方向感比单步更关键。

这里我较个真:0.0008 和 0.0005 的差距听起来很细,可在复杂度图上,它代表一个此前被「不可能」牢牢挡住的区间,第一次被人真正踏了进去。这跟工程上把常数压一压,性质完全不同。

我的判断是,方法层面最大的意义是演示了这样一条路:不必发明全新的数学,只要把现有工具重排得当,就可能撬动被公认多年的边界——这个信号,比两个数字本身更值钱。

人与机器对坐

人和机器各自干了什么

据转述该论文的报道,Claude 参与了这次发现的中间环节——由模型补上人一时没想到的拼接思路,再由人来验证、核对、收尾。这份分工,报道里拆得相当清楚,没有含糊的余地。

人的活是把模型丢出来的点子接住,跟已有的证明逐条核对,辨别哪些方向站得住,再把它改写成严谨、可独立检查的完整结果,而不是直接把机器的输出当成答案,这份把关最费人。

我的判断是,这次的分工最能说明当下这类工具的位置:它不负责包办结论,而是把搜索空间撞开一角,让研究者看到原先被注意习惯屏蔽掉的岔路。

说白了,人负责判断哪条路能走通、值不值得走到黑,机器负责把路边的可能性翻出来铺在台面上。两边都不闲,谁也别想顶替谁。

谨慎的庆祝

但这里有个前提

但这里有个前提:报道给的是结果和思路的轮廓,完整证明的细节、可复现的代码,目前还没有被逐字确认过。同行验证没走完,任何结论都该先打个折再看。

更关键的是,亚二次、亚三次在这两个具体问题上成立,不等于这类工具对每一个难题都管用。这次的位置很特殊,任何想把它顺手推广到别处的说法都要小心。

我的判断是,把它读成「这台机器开始理解算法结构」,还为时过早。更稳的说法是,它偶尔探到了人没挖过的点;至于挖得对不对,得等人把证明补齐、逐字验证完。

还有一个常被略过的点:这次能成,前提是问题足够干净、步骤可以形式上核对。真到了要图纸直觉、要工程判断的场合,这套「撞方向」的办法未必同样好使,别顺势吹过了头。

所以不用急着庆祝,回头盯紧后续的同行评审就好——只要证明站得住,这页教科书才算真正翻了过去。

AI 写一段 JS,十步工具调用一次交完
下一篇
AI 写一段 JS,十步工具调用一次交完
Code Mode 让 Claude 写一段 JS,一次就把多步工具调用跑完。
继续下滑 或 点击阅读下一篇
下一篇 AI 写一段 JS,十步工具调用一次交完 →
站长照片
“

1

”
联系二维码
微信:扫码加企业微信
邮箱:15611497360@aqq.com
手机:15611497360

私信站长

申请退款