Math Conjectures

Modern 3SUM Conjecture

OPENMajorConjectureProposed c. 1995 · Standard version

Canonical statement

For every ε>0\varepsilon>0, there is no randomized bounded-error O(n2−ε)O(n^{2-\varepsilon})-time word-RAM algorithm that, given nn distinct O(log⁡n)O(\log n)-bit integers, decides whether three distinct input integers a,b,ca,b,c satisfy
a+b+c=0. a+b+c=0.
View source LaTeX
For every \(\varepsilon>0\), there is no randomized
bounded-error \(O(n^{2-\varepsilon})\)-time word-RAM algorithm that,
given \(n\) distinct \(O(\log n)\)-bit integers, decides whether three
distinct input integers \(a,b,c\) satisfy
\[
  a+b+c=0.
\]
TCS-020:[GajentaanOvermars1995][GronlundPettie2014ThreeSUM][KopelowitzPettiePorat2016]
Theoretical computer scienceOperations research

Notes

The 3SUM problem asks, given nn distinct integers, whether three of them satisfy a+b+c=0a+b+c=0; the straightforward algorithm runs in quadratic time. The modern conjecture asserts that no randomized bounded-error algorithm solves the problem in time O(n2−ε)O(n^{2-\varepsilon}) for any ε>0\varepsilon>0 on a word RAM with O(log⁡n)O(\log n)-bit inputs. The hypothesis descends from the work of Gajentaan and Overmars, who in 1995 identified a large class of computational-geometry problems that are 3SUM-hard and all seemingly stuck at quadratic time [GajentaanOvermars1995].

The older, literal expectation that no o(n2)o(n^2)-time algorithm exists was refuted: Grønlund and Pettie gave algorithms beating n2n^2 by logarithmic factors [GronlundPettie2014ThreeSUM], which is why the modern formulation excludes only polynomial improvements of the form n2−εn^{2-\varepsilon}. On the hardness side, the conjecture supports conditional lower bounds well beyond geometry, including higher polynomial lower bounds obtained by Kopelowitz, Pettie and Porat [KopelowitzPettiePorat2016].

The conjecture remains open: no fixed-polynomial speedup over quadratic time is known, and no unconditional quadratic lower bound either; settling it requires one or the other.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.