三個數加起來等於 0，指數 2 終於掉了 0.0008：預印本宣稱推翻 3SUM 與 APSP 假說，從 1962 年的一頁論文到 Claude｜AI 寫的數學

3SUM：給 n 個數，有沒有三個加起來等於 0。APSP：所有點對最短路徑。教科書分別是 n² 與 n³，幾十年只省過比多項式小的因子。細粒度複雜度假設這兩個指數不能往下掉一個固定常數。2026 年 10 月 5 日 Josh Alman 與 Virginia Vassilevska Williams 的預印本在多項式大小的整數上給出確定性演算法：3SUM O(n^1.9992)、APSP O(n^2.9995)，論文寫明這推翻了兩個假說；實數版 3SUM／APSP 是 Las Vegas 演算法，期望時間分別為 O(n^1.998)、O(n^2.998)。這集只講題目、影響與故事，不講證明。 論文自述：演算法由 Anthropic 的內部研究模型（Claude）找到，「no human input」是作者與 Anthropic 的說法，無法從外部查證，模型版本未公開；Anthropic 向兩位作者提供報酬。目前狀態：預印本，沒有期刊審查；Gasarch 11 月 1 日寫「being looked at by experts」。Lean 形式化由 Anthropic 內部模型完成，涵蓋 Exact Triangle、3SUM、(min,+)-product、APSP、Zero-Weight k-Clique，實數輸入的執行時間不在其中，README 沒有記錄 Comparator 的執行；本頻道沒有自己建置。範圍：CNF-SAT、Orthogonal Vectors、k≥4 的 k-SUM 這個演算法碰不到。論文自己寫演算法 potentially impractical、常數 enormous。這集的研究與旁白也用 Claude 製作。 一手來源： ・Alman, Vassilevska Williams, Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs：https://arxiv.org/abs/2610.06783 ・Lean 形式化：https://github.com/anthropics/formal-math/tree/main/3sum-apsp ・Aaronson, The Mathocalypse：https://scottaaronson.blog/?p=10169 ・Gasarch, 3SUM and APSP and ETH, Oh My!：https://blog.computationalcomplexity.org/2026/11/3sum-and-apsp-and-eth-oh-my.html ・Majdoddin 後續（3SUM n^(1.9945+o(1))）：https://arxiv.org/abs/2610.17420 ・Gajentaan, Overmars, On a class of O(n²) problems in computational geometry (1995)：https://doi.org/10.1016/0925-7721(95)00022-0 ・Pătraşcu, Towards Polynomial Lower Bounds for Dynamic Problems (STOC 2010)：https://people.csail.mit.edu/mip/papers/mp-3sum/paper.pdf ・Vassilevska Williams, Williams, Subcubic equivalences between path, matrix and triangle problems (FOCS 2010)：論文參考文獻 [VW10] ・R. Williams, Faster all-pairs shortest paths via circuit complexity：https://arxiv.org/abs/1312.6680 ・Grønlund, Pettie, Threesomes, Degenerates, and Love Triangles：https://arxiv.org/abs/1404.0799 ・Floyd, Algorithm 97: Shortest path (1962)：https://doi.org/10.1145/367766.368168 ・Schrijver, On the History of the Shortest Path Problem (2012)：https://ems.press/books/dms/251/4930 ・Strassen, Gaussian elimination is not optimal (1969)：https://link.springer.com/article/10.1007/BF02165411 ・Pătraşcu 訃聞（Fortnow）：https://blog.computationalcomplexity.org/2012/06/mihai-patrascu-1982-2012.html ；（Thorup）https://eatcs.org/index.php/home/1-news/1282-obituary-for-mihai-patrascu 章節 00:00 開場 02:07 1962 年的一頁 03:03 兩個指標 04:02 上界與下界 04:34 綁在一起 05:46 Pătraşcu 06:46 同進同退 07:52 Claude 08:22 只算要的格子 10:23 0.0008 算什麼 11:20 能用嗎 11:35 別人怎麼說 12:40 還沒解決的 照片出處 ・Mihai Pătraşcu：Dr. Virgil Pătrașcu（CC0，https://commons.wikimedia.org/wiki/File:Mihai_Patrascu.jpg） ・Ryan Williams：Thore Husfeldt, CC BY-SA 3.0（https://commons.wikimedia.org/wiki/File:Ryan_Williams_at_Dagstuhl_10441.jpg） ・Virginia Vassilevska Williams：Katrin Schmid, CC BY-SA 2.0 de（https://commons.wikimedia.org/wiki/File:Virginia_Vassilevska_Williams_Oberwolfach_2012.jpg） ・Scott Aaronson：Easy n（Public domain，https://commons.wikimedia.org/wiki/File:Scott_Aaronson_retouched.jpg） ・William Gasarch：SebastosOctavian, CC BY-SA 4.0（https://commons.wikimedia.org/wiki/File:BillGasarch.jpg） ・Volker Strassen：David Eppstein, CC BY-SA 3.0（https://commons.wikimedia.org/wiki/File:Strassen_Knuth_Prize_lecture.jpg） ・Josh Alman：本人網頁（https://joshalman.com/） 配樂（依出場順序）： ・Erik Satie〈Gymnopédie No. 1〉，Robin Alciatore 演奏（Musopen，公有領域；https://commons.wikimedia.org/wiki/File:Erik_Satie_-_gymnopedies_-_la_1_ere._lent_et_douloureux.ogg） #數學 #理論計算機 #演算法 #3SUM #細粒度複雜度 #AI寫的數學