整数乘法首破 n log n 下界,AI 主导引热议
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 的讨论帖)。
2026-10-07 ~ 2026-10-09 · 11 条相关
- 第 1 集:3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现(2026-10-06,13 条)
- 第 2 集:整数乘法首破 n log n 下界,AI 主导引热议(2026-10-07,11 条)
- 第 3 集:OpenAI 数学成果被指玩弄复杂度表述话术(2026-10-07,2 条)
- 第 4 集:AI 社区整活直播:Agent 军团冲击整数乘法复杂度纪录(2026-10-08,4 条)
一手来源
- 整数乘法再快于 N log N?算法圈惊呼「太邪门」 — QuintinPope5 ·
- 2026 年还在发现乘法新算法,Dean Ball 感叹:提速小数点后 37 位 — deanwball ·
- AI 加形式化工具把数年研究压缩到数小时,社区直播攻整数乘法难题 — aran_nayebi ·
- 【源头】整数乘法再快于 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