The modern integer 3SUM conjecture
For an integer $n \ge 3$, the input is an explicitly listed set $S \subseteq \{-n^3, \dots, n^3\}$ of $n$ integers, written in binary, and the task is to decide whether $S$ contains pairwise distinct $a, b, c$ with $a + b = c$. The model is the word RAM with words of $\Theta(\log n)$ bits, long enough to hold an input integer and an address, in which arithmetic and bit operations on words, comparisons and indexed memory accesses cost one step. An algorithm is a single uniform program for all $n$; it may use randomness, but must answer correctly with probability at least $2/3$ on every input. All its computation, including any preprocessing of the input, is counted, and it receives no advice. Let $$T_A(n) = \max_{S} \mathbb{E}\bigl[\text{number of steps of } A \text{ on } S\bigr],$$ the maximum over all such $S$ with $|S| = n$ and the expectation over the random choices of $A$. Checking all pairs takes $O(n^2)$ steps; Baran, Demaine and Pătraşcu gave a randomized algorithm with expected time $O\bigl(n^2 (\log\log n)^2/(\log n)^2\bigr)$ in this model.
Problem. Is it true that there are no fixed $\varepsilon > 0$ and no such algorithm $A$ with $T_A(n) = O(n^{2-\varepsilon})$ as $n \to \infty$? Savings by logarithmic factors are allowed.
Source: Pătraşcu (2010), Conjecture 6 of the author's manuscript, for zero-error algorithms in expected time n^{2−o(1)}; quadratic 3SUM-hardness goes back to Gajentaan and Overmars (1995). Stated with bounded error, after Ball, Rosen, Sabin and Vasudevan (2017), by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- 3SUM, AIM Open Applied Problems, fine-grained complexity, word RAM algorithms
References
@inproceedings{patrascu2010,
author = {P{\u{a}}tra{\c{s}}cu, Mihai},
title = {Towards polynomial lower bounds for dynamic problems},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing ({STOC} 2010)},
publisher = {ACM},
address = {New York},
year = {2010},
pages = {603--610},
doi = {10.1145/1806689.1806772},
}
@article{gajentaan1995,
author = {Gajentaan, Anka and Overmars, Mark H.},
title = {On a class of {$O(n^2)$} problems in computational geometry},
journal = {Comput. Geom.},
volume = {5},
number = {3},
year = {1995},
pages = {165--185},
doi = {10.1016/0925-7721(95)00022-2},
}
@inproceedings{ball2017,
author = {Ball, Marshall and Rosen, Alon and Sabin, Manuel and Vasudevan, Prashant Nalini},
title = {Average-case fine-grained hardness},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing ({STOC} 2017)},
publisher = {ACM},
address = {New York},
year = {2017},
pages = {483--496},
doi = {10.1145/3055399.3055466},
}
@article{baran2008,
author = {Baran, Ilya and Demaine, Erik D. and P{\u{a}}tra{\c{s}}cu, Mihai},
title = {Subquadratic algorithms for {3SUM}},
journal = {Algorithmica},
volume = {50},
number = {4},
year = {2008},
pages = {584--596},
doi = {10.1007/s00453-007-9036-3},
}
@misc{aim-integer-three-sum-hardness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The modern integer 3SUM conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/340-integer-three-sum-hardness.md},
note = {Entry 340 at commit a153f46, 2026-10-13},
}
Resolution claims
We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-15 | Needs verification → Solution claimed | — | Recorded here: arXiv:2610.06783v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00319, "The modern integer 3SUM conjecture", clopen.solutions.