专题 · 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 在开放性理论研究中取得实质突破的标志性案例,也暗示自动化搜索可能找到人类因偏好「优雅解」而长期错过的算法
- APSP 次立方与 3SUM 次平方算法问世,细粒度复杂度格局生变 — thegautamkamath · 2026-10-06
- Claude 突破 3SUM 复杂度下界,给出 O(n^1.9992) 算法附 Lean 证明 — thegautamkamath · 2026-10-06
- Alman 与 Williams 突破数十年瓶颈:3SUM 首次达到亚二次复杂度 — auto_grad_ · 2026-10-06
- Anthropic 内部模型独立发现算法,首次突破 3SUM 与 APSP 平方/立方下界 — AMBNNJ · 2026-10-06
- 新论文推翻 3SUM 与 APSP 猜想,传 Claude 参与发现次二次算法 — burny_tech · 2026-10-06
- 3SUM 与 APSP 猜想被推翻:首次真次二次算法问世 — ctjlewis · 2026-10-06
- Claude 助力论文宣称推翻 3SUM 猜想,附 Lean 形式化验证 — basedjensen · 2026-10-06
- AI 发现新算法,首次突破 3SUM 与 APSP 复杂度下界 — FrnkNlsn · 2026-10-06
- 3SUM 与 APSP 猜想被推翻,KLS 猜想同日被证明 — aran_nayebi · 2026-10-06
- Anthropic 内部模型自主破解 3SUM 与 APSP 难题 — robleclerc · 2026-10-07
- Anthropic 用 Claude 破解 3SUM 多项式界,附 Lean 形式化证明 — HankYeomans · 2026-10-07
- 算法理论一日连破三关,MIT 学者调侃:也许 P=NP 真有戏 — burny_tech · 2026-10-07
- AI 找到 3SUM 的 O(n^1.9992) 算法:机器眼里数学不讲优雅 — aran_nayebi · 2026-10-08
第 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 的讨论帖)。
- 整数乘法再快于 N log N?算法圈惊呼「太邪门」 — QuintinPope5 · 2026-10-07
- LLM 五年内从算错乘法到改进乘法算法本身,突破 n log n 下界 — CatAstro_Piyush · 2026-10-07
- 3-sum 降到 n^1.999 让人担心数学「丑陋」?换个视角又美了 — thomasahle · 2026-10-07
- 整数乘法可快于 n log n,数学「下界」再被动摇引发热议 — deanwball · 2026-10-07
- 2026 年还在发现乘法新算法,Dean Ball 感叹:提速小数点后 37 位 — deanwball · 2026-10-07
- 把已知指数磨掉小常数算突破吗?算法界的实用主义之争 — srchvrs · 2026-10-07
- shaving 常数算突破吗?学者激辩超 n log n 乘法算法 — thomasahle · 2026-10-07
- 从 O(n²) 到 Karatsuba:大整数乘法的分形复杂度解释 — snikolov · 2026-10-08
- 整数乘法突破 n log n 下界?圈内质疑传闻未经正式发布 — IgorCarron · 2026-10-08
- 整數乘法複雜度刷屏?网友:买台德州仪器计算器吧 — chrisalbon · 2026-10-09
- AI 加形式化工具把数年研究压缩到数小时,社区直播攻整数乘法难题 — aran_nayebi · 2026-10-09
第 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,技术上确实低于上界,实质上是文字游戏,引发社区调侃。
- 「低于 n log n」翻车现场:细看是 n(log n)^0.54999 — BLUECOW009 · 2026-10-07
- 网友调侃 OpenAI 数学成果:号称低于 n log n,实为 n(log n)^0.54…9 — burny_tech · 2026-10-07
第 4 集 · AI 社区整活直播:Agent 军团冲击整数乘法复杂度纪录(2026-10-08,4 条)
AI Agent 社区发起一场整活直播,追踪 @0xdoug 使用 Agent 军团冲击 O(n·log n) 整数乘法纪录的进展。最新消息是其达成 2^(-15)(此前曾达 2^(-34)),但错过了凌晨 12:44 的目标时刻。julianschiavo 等人煞有介事地持续播报进度,社区纷纷接梗,eigenhector 称「次线性时间整数乘法才是正道」,还有人按「严谨数据分析」调侃大数乘法将迎来「foom」式加速,感叹这条时间线太野了。
- AI 圈梗:按当前趋势大数乘法将迎来「foom」式加速 — rickasaurus · 2026-10-08
- 预言线性时间整数乘法达成时刻,AI 圈整活直播又更新进度 — rickasaurus · 2026-10-09
- 整数乘法进度条又更新,AI 圈感叹这个时间线太野了 — eigenhector · 2026-10-09
- Agent 军团冲击 O(n·log n) 乘法纪录:2^-15 达成,直播预测时刻 — eigenrobot · 2026-10-09