One formulation of the 3-SUM problem is determining whether a set of $$$n$$$ integers has a subset of $$$3$$$ integers that add up to zero. With hashing, this takes $$$O(n^2)$$$ time and was conjectured to be optimal.
The all-pairs shortest paths problem (APSP) is determining the shortest path between all pairs of vertices in a graph with $$$n$$$ vertices. Floyd-Warshall uses $$$O(n^3)$$$ time and was conjectured to be optimal.
It seems possible that neither of these conjectures is true, declared by the paper https://arxiv.org/pdf/2610.06783 using an internal model of Claude and verified using Lean.
damn does this mean $$$P=NP$$$ since $$$3$$$-sum is $$$NP$$$-complete? I feel like this should be bigger news
$$$3$$$-sum was never NP-complete.. it had $$$O(n^2)$$$ solution which was conjectured to be optimal
You are probably confusing $$$3SUM$$$ with $$$OV$$$ (orthogonal vectors problem) and $$$P = NP$$$ with a much stronger conjecture (strong exponential time hypothesis, $$$SETH$$$ for short). A strongly subquadratic ($$$O(n^{2-\varepsilon})$$$ for some $$$\varepsilon \gt 0$$$) algorithm for $$$OV$$$ would imply a state-of-the-art algorithm for $$$SAT$$$ and refute $$$SETH$$$. Still, even a linear algorithm for $$$OV$$$ is not known to imply $$$P = NP$$$.