Columbia 與 MIT 論文展示 Claude 找到更快的 3SUM 與 APSP 演算法
Columbia 與 MIT 論文展示 Claude 發現的演算法突破 3SUM 與 APSP 長期速度上限
3SUM 和全對最短路徑都是長期難以加快的問題,研究者過去認為它們的運算時間很難再改善。
- Columbia 與 MIT 的論文指出,Claude 找到一種更快計算長而窄矩陣中特定元素的方法,再透過已知的轉換,讓 3SUM 的時間降到 O(n^1.9992),全對最短路徑降到 O(n^2.9995)。這些改善幅度不大,卻足以推翻相關的難度猜想。
- 研究也用 Lean 4 形式化驗證證明。
AI 伴隨問答
針對這篇報導有疑問?可直接點選快捷問題或向 AI 追問背景脈絡與技術細節:
這項研究展示 Claude 如何從矩陣乘法問題找到更快演算法,再透過已知轉換改善 3SUM 與 APSP 的運算時間。
Rohan Paul· @rohanpaul_ai · X·2026-11-22 02:47· 4 分鐘前精選AI 評分77
AI 導讀
Columbia 和 MIT 的論文展示 Claude 發現的演算法在 3SUM 和全對最短路徑(APSP)上取得多項式改進,3SUM 達到 O(n^1.9992)、APSP 達到 O(n^2.9995),推翻了 3SUM 和 APSP 假設。
推薦理由
論文顯示 Claude 發現的演算法改進了 3SUM 和 APSP 的長期複雜度上限,並用 Lean 4 形式化驗證,讀者可以瞭解 AI 搜尋演算法的可行路徑。
哥倫比亞大學和麻省理工學院的新論文表明,Claude 發現的一種演算法打破了 3SUM 和全對最短路徑長期以來的速度極限。
3SUM 問的是列表中是否有 3 個數之和為 0,全對最短路徑則要求出圖中每一對節點之間的距離。幾十年來,沒有人能把教科書式的二次和三次時間複雜度改進超過極小的常數因子,許多人認為不可能做到。
Claude 找到了一種更快的方法來計算兩個長而窄的矩陣乘積中的選定元素,跳過了經典方法所做的一些工作。已知的歸約隨後將其轉化為 3SUM、最短路徑以及許多相關問題的加速。
3SUM 現在的執行時間為 O(n^1.9992),最短路徑為 O(n^2.9995),這些微小的改進仍然否定了 3SUM 和 APSP 猜想。Claude 在一次會話中找到了該方法,使用了 1600 萬輸出 token,沒有人類輸入。
把“已知困難”的演算法極限視為 AI 搜尋的開放目標,並像這篇論文用 Lean 4 所做的那樣,對 AI 發現的證明進行形式化驗證。
來源:Rohan Paul · x.com