3SUM hypothesis

Take three lists of integers: 1, 4, 7 in the first; 2, 5, 8 in the second; and 6, 9, 12 in the third. Choosing 4 and 2 gives 6, a match in the third list. The task is to decide whether any such match exists. With three entries in each of the first two lists, there are nine candidate pairs; doubling both list lengths gives four times as many pairs. Can an algorithm without random choices decide this on arbitrary growing lists with a fixed improvement in that growth rate? The integers are machine-sized: their bit counts are at most a fixed multiple of the bits needed to label list positions.[1] [2]

The 3SUM question asks whether one can decide the existence of a matching sum substantially faster than quadratic time on arbitrary input sets. Given $n$-element integer sets $A,B,C$, it asks whether there are $a\in A$, $b\in B$, $c\in C$ with $a+b=c$. In the toy sets $\{1,4,7\}$, $\{2,5,8\}$, $\{6,9,12\}$, the pair $4,2$ certifies yes because $4+2=6$. This page restricts numbers to $O(\log n)$ bits and uses a word RAM with $\Theta(\log n)$-bit words, so arithmetic cannot pack arbitrarily large inputs into one unit-cost word. The target is a deterministic worst-case time bound $O(n^{2-\varepsilon})$ for one fixed $\varepsilon>0$. The saving must apply throughout the eligible input family, not just on easy examples.[1] [2]

Known speedups shave slowly growing factors from the work. They do not supply the stronger, fixed improvement in how the work grows as the lists get longer.[1] [2]

Logarithmic speedups and preprocessed-universe or indexing results do not settle this raw-input model. Unrestricted large machine words are outside the chosen scope.[1] [2]

This is a small arithmetic question that serves as a benchmark for other algorithms. Certain geometric and graph problems can encode 3SUM instances, so sufficiently fast algorithms for those problems would also make 3SUM faster. The hypothesis helps explain why apparently different tasks resist particular speedups, with the connection conditional on the stated model and the kind of reduction used.[1] [2]

The hypothesis supports precise conditional barriers through reductions, including deterministic reductions to offline set intersection and triangle-listing tasks. The computation model matters: a randomized reduction may require a hardness assumption against randomized 3SUM algorithms, stronger than the deterministic target on this page. Separating raw-input time, preprocessing time, word size and randomness keeps the resulting comparisons meaningful rather than treating every problem labelled “3SUM-hard” as having the same guarantee.[1] [2]