跳到正文
𝕏 Rohan Paul(x.com)·· 1 天前品質評分58
重點導讀

3SUM 和計算圖中所有點之間的最短距離,長期被認為很難比教科書方法快多少。

  • 這篇 Columbia 與 MIT 論文說,Claude 找到一種計算兩個長而窄的矩陣部分乘積的方法,省下傳統做法中的一些計算,再把它用到這兩類問題。論文列出的速度提升幅度不大,但足以推翻相關的 3SUM 與 APSP 假設。
  • 研究團隊也用 Lean 4 檢查了證明。作者表示,Claude 在一次工作階段中找到這個方法,使用 16M 輸出 tokens,沒有人工介入。

AI 伴隨問答

自備 Key 深度分析

針對這篇報導有疑問?可直接點選快捷問題或向 AI 追問背景脈絡與技術細節:

Rohan Paul
Rohan Paul@rohanpaul_ai
·1 天前
𝕏

New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits for 3SUM and all-pairs shortest paths.

3SUM asks whether 3 numbers in a list sum to 0, and all-pairs shortest paths asks for every distance in a graph. For decades, nobody beat textbook quadratic and cubic time by more than tiny factors, and many assumed nobody could.

Claude found a faster way to compute selected entries of a product of 2 long, thin matrices, skipping work a classic method does. Known reductions then turn this into speedups for 3SUM, shortest paths, and many related problems.

3SUM now runs in O(n^1.9992) time and shortest paths in O(n^2.9995), tiny gains that still refute the 3SUM and APSP hypotheses. Claude found the method in 1 session using 16M output tokens with no human input.

Treat "known hard" algorithm limits as open targets for AI search, and check AI-found proofs formally, as this paper did with Lean 4.

推文來源 · X (Twitter)在 X 參與討論

讀者討論

理性交流 · 即時討論