3SUM与APSP计算复杂度壁垒被突破

Subquadratic 3SUM and Subcubic APSP

算法领域迎来重大突破，研究人员首次实现了3SUM和全源最短路径（APSP）问题的多项式级加速。新算法将3SUM的确定性求解时间优化至O(n^1.9992)，APSP优化至O(n^2.9995)，直接推翻了长期存在的3SUM和APSP假设。这一成果源于一种针对稀疏偏斜图中三角形问题的全新矩阵乘法算法，不仅解决了Exact Triangle问题，还通过已知归约关系，推翻了Exact Triangle假设、Zero-Weight k-Clique假设等多个计算复杂性猜想，为一系列相关算法问题带来了实质性的速度提升。