Claude发现突破3SUM和最短路径算法速度限制的算法
热点事件持续更新
Claude发现突破3SUM和最短路径算法速度限制的算法
1 篇报道1 个报道来源1 小时前更新
先了解这件事
AI 综述
哥伦比亚大学与麻省理工学院的新论文显示,Anthropic旗下AI模型Claude发现的算法在3SUM和全对最短路径问题上突破了长期存在的速度限制。具体而言,3SUM问题的运行时间优化至O(n^1.9992),全对最短路径问题优化至O(n^2.9995)。这些微小的常数级改进在理论计算机科学中具有重大意义,因为它们直接否定了广泛使用的3SUM假设和APSP(全对最短路径)假设。 3SUM假设和APSP假设是算法复杂性研究中的基石,许多经典算法的时间复杂度下限都建立在这两个假设之上。此次突破意味着基于这些假设推导出的效率上限可能不再成立,为相关领域的算法设计打开了新的可能性空间。
AI 根据报道生成 · 58 分钟前更新
最新进展11月22日 02:47
Columbia 与 MIT 论文:Claude 发现的算法突破 3SUM 和全对最短路径的长期速度限制报道时间线
沿着报道,了解事件的不同侧面。
11月22日
- Rohan Paul (X)精选Columbia 与 MIT 论文:Claude 发现的算法突破 3SUM 和全对最短路径的长期速度限制
Columbia 与 MIT 的新论文显示,Claude 发现的算法在 3SUM 和全对最短路径问题上突破了长期存在的速度限制。3SUM 现在可在 O(n^1.9992) 时间内运行,最短路径为 O(n^2.9995),这些微小改进仍否定了 3SUM 和 APSP 假设。
本事件热度走势
还没有足够的连续观测数据,暂不绘制趋势。