专题 · FULL STORY

AI 撼动算法复杂度:从突破传闻到社区验证

十月初,研究者接连爆料 AI 参与的整数乘法与 3SUM 等经典问题复杂度突破,随后社区质疑 OpenAI 成果的复杂度表述,更有 Agent 军团直播冲击整数乘法纪录,事件线从传闻、争议走向验证与整活。

2026-10-06 ~ 2026-10-09 · 4 集 · 30 条

第 1 集 · 3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现(2026-10-06,13 条)

Josh Alman 与 Virginia Vassilevska Williams 发布 arXiv 预印本《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》,对两个教科书级经典问题给出历史首次的多项式级改进:对 n 个多项式大小整数,3SUM 可在确定性 O(n^1.9992) 时间内求解;整数权重的全源最短路径(APSP)可在 O(n^2.9995) 时间内求解。这突破了长期被视为下界的 n² 与 n³ 界,实质推翻 3SUM 假设与 APSP 假设,重塑细粒度复杂度理论格局。社交媒体同时流传 Anthropic 的 Claude 参与发现核心算法的消息,目前尚无论文正文或 Anthropic 官方的直接说明。

已确认

  • 论文给出确定性算法,是首个对 3SUM 与 APSP 的真正次平方/次立方结果,适用于多项式大小的整数输入,带多项式相关条件
  • 论文随附 Lean 形式化,其中声称推翻了随机整数 Word-RAM 3SUM 猜想——据 @basedjensen 转述,该猜想位列作者自排的「数学最重要未解问题榜单」第 159 位,且论文称 Claude 参与发现了针对 3SUM、APSP 及 ExaTime 相关问题的反驳算法
  • 据 @thegautamkamath 转述 Ilya Razenshteyn 的说法,Claude 为 3SUM 问题(判断 n 个整数中是否存在三数之和为零)给出 O(n^1.9992) 算法,并附带 Lean 形式化证明
  • @AMBNNJ 称 Anthropic 内部模型独立发现了突破平方/立方下界的算法;@robleclerc 补充转述称,该内部模型在探索开放问题时自行发现核心算法,研究人员随后将其简化并为两个问题证明了多项式加速
  • 据 @arannayebi 转述,同日理论计算机科学接连出现多项突破:亚 n·log n 的 FFT(整数乘法新上界)、次立方 APSP、次二次 3SUM,以及 KLS 猜想被证明;他半开玩笑称这一天动摇了自己对人类算法能力的信心
  • 据 @HankYeomans 转述,Przemek Chojecki 评价称 Claude 参与改进了 3SUM-Hard 一族问题的多项式界,有人认为这是朝 P=NP 方向的重要进展
  • 据 @arannayebi 转引 NoahCitron 的调侃:数学家认为数学是美的,而机器眼里数学不讲优雅——人类只是恰好先找到了那些优雅的解,机器得出的 3SUM 次二次算法即是例证

尚未确认

  • Claude 参与发现的说法目前仅来自社交媒体流传(@AMBNNJ、@thegautamkamath 转述、@robleclerc 转述、@basedjensen 等),尚无论文正文细节或 Anthropic 层面的直接说明

为什么重要

  • 3SUM 与 APSP 假设是细粒度复杂度理论的支柱,大量条件性下界建立在它们之上;被推翻意味着该领域格局需要重绘
  • @thegautamkamath 转述评论称这是真正非凡的结果,但同时带走了该领域大部分乐趣——许多经典难度假设随之动摇
  • 若 Claude 参与发现属实,将是 AI 在开放性理论研究中取得实质突破的标志性案例,也暗示自动化搜索可能找到人类因偏好「优雅解」而长期错过的算法

第 2 集 · 整数乘法首破 n log n 下界,AI 主导引热议(2026-10-07,11 条)

10 月 7 日起,多位研究者在社交平台爆料:整数乘法算法的速度首次突破长期被视为下界的 O(n log n) 复杂度,即比 Schönhage–Strassen 类算法更快,且主要贡献来自 AI。这一结果连同 3-sum 被压到 n^1.999 等近期进展,在算法与复杂性理论圈引发广泛讨论与争论,热度之高甚至让部分博主感叹时间线被刷屏。

已确认

  • 新工作表明整数乘法可以快于 n log n,被引用者形容为「cursed(邪门)」(@mgostIH 的消息,由 @QuintinPope5 转述)。
  • @IgorCarron 转引评论称,AI(AlphaEvolve 类工作)找到了比 n log n 更快的整数乘法方法,但 AES 加密未受影响,评论者戏谑「就因为还没宣布?」;该说法仍属评论性讨论,算法细节未公布。
  • 技术路线(据 @deanwball 引用的推文):把两数相乘转化为卷积网络,再走 FFT 并利用蝶形网络的对称性;理论复杂度更低,但 Dean Ball 提到提速幅度仅体现在小数点后第 37 位左右。
  • 研究进程本身也在被 AI 改写:@arannayebi 转述 Christian Szegedy 的感叹——去年之前这类成果还是分散在数年间、经月度同行评审才能发表的论文,如今借助 AI 与形式化工具,整个过程可被压缩到几小时;背景是 Aurelien Prot 建了一个实时追踪器,公开直播社区用 AI 攻坚这一整数乘法难题。
  • 主要贡献来自 AI,与五年前 LLM 还会算错乘法形成戏剧性对比(@CatAstroPiyush 转发的讨论)。
  • @bzogrammer(由 @snikolov 转发)给出通俗解释:这类结果并非离奇,是典型的分形式复杂度界;朴素乘法 O(n²) 曾长期被认为最优,直到 Karatsuba 提出指数为 log2(3)≈1.58 的算法才被打破,历史在此重演。
  • 同期 3-sum 降到 n^1.999、乘法降到 n(log n)^0.999,均属「擦线改进」类结果。
  • @chrisalbon 反映讨论已刷屏,人人都在聊「sub n log n」和「kappa 常数」,并自嘲式建议不如买台德州仪器计算器解决问题。

尚未确认

  • 上述内容多来自转发与二手转述,原始论文尚未正式发布,算法细节与 AI 参与的具体方式未在帖子材料中给出。

为什么重要

  • 如果下界真的被打破,说明长期坚信的复杂度下界可能只是人类认知局限导致的「弱近似」(多位发帖者的感叹)。
  • 研究范式的变化同样值得注意:若如 Szegedy 所言,AI 加形式化工具能把数年的同行评审周期压缩到数小时,并配合公开实时追踪器进行社区协作,这预示着数学研究流程本身可能被重塑。
  • 审美之争:@thomasahle 指出这类结果起初让人担心数学深挖下去变「丑陋」(square packing 式的 ugly bound),但换个视角也能看到美;@deanwball 则感叹 2026 年了人类(和 AI)还能在「乘法」上发现新东西。
  • 实用性之争:@srchvrs 质疑在已知指数上磨掉小常数是否算根本性突破,还是只是 hack——历史上不少渐近改进带有「银河级」常数,实际毫无影响,且大概率不会有;对此的回应也存在(@thomasahle 的讨论帖)。

第 3 集 · OpenAI 数学成果被指玩弄复杂度表述话术(2026-10-07,2 条)

近日流传的推文列举 OpenAI 内部前沿模型产出的多项理论计算机科学成果,包括将 3SUM 问题改进到 O(n^1.9992)、把整数乘法改进到约 O(n log n^(1e-55)) 等。但有网友戳穿其中复杂度「低于 n log n」的宣传话术:实际结果是 n(log n)^0.5499…9,只是在小数点后贴满一串 9,技术上确实低于上界,实质上是文字游戏,引发社区调侃。

第 4 集 · AI 社区整活直播:Agent 军团冲击整数乘法复杂度纪录(2026-10-08,4 条)

AI Agent 社区发起一场整活直播,追踪 @0xdoug 使用 Agent 军团冲击 O(n·log n) 整数乘法纪录的进展。最新消息是其达成 2^(-15)(此前曾达 2^(-34)),但错过了凌晨 12:44 的目标时刻。julianschiavo 等人煞有介事地持续播报进度,社区纷纷接梗,eigenhector 称「次线性时间整数乘法才是正道」,还有人按「严谨数据分析」调侃大数乘法将迎来「foom」式加速,感叹这条时间线太野了。