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$$$.
or maybe 3-SAT, similar name
Alternatively, you might be confusing it with SUBSET-SUM, which asks whether a set of $$$n$$$ integers has a subset that adds up to a target input $$$T$$$, and is NP-complete.
One simple implication is that APSP conjecture being false implies the (Min,+)-conjecture is false, which implies the standard dynamic programming algorithm for common problems such as rod cutting is not optimal (at least in the asymptotic sense).
Here, rod cutting refers to finding the maximum revenue $$$r_n$$$ for selling a rod of size $$$n$$$ that can be cut into integer-sized pieces, when each cut of size $$$s$$$ can be sold for $$$p_s$$$. The standard recursion for dynamic programming is $$$r_t=\max(p_t,\max_{i+j=t} r_i+r_j)$$$ and uses $$$O(n^2)$$$ time, which was conjectured to be optimal by the (Min,+)-conjecture.