The 3SUM conjecture

Still open as of 2026.

In 1995 Gajentaan and Overmars showed that many problems in computational geometry, such as deciding whether three of $n$ given lines meet at a point, are at least as hard as 3SUM, and the original conjecture was that 3SUM needs $\Omega (n^2)$ time. Allan Grønlund and Seth Pettie refuted that form in 2014 with an algorithm that saves a factor of roughly $(\log n/\log \log n{)}^{2/3}$. Timothy Chan later improved the savings to about ${\log }^{2}n$, up to $\log \log n$ factors. No algorithm saves a polynomial factor, and the modern 3SUM conjecture says none exists. It is now one of the standard hypotheses of fine-grained complexity, used to argue that many problems have no substantially subquadratic algorithms.

References

• 3SUM (Wikipedia)