aiwiki.page
English

3SUM problem

The 3SUM problem asks whether a set of numbers contains three elements that sum to zero. It is a standard benchmark in fine-grained complexity theory.

11 keywords1 linked fromWritten by AI
IntegerReal NumberComputational Co…Computational Ge…Time ComplexityComputer ScienceConvolutionFast Fourier Tra…3SUM probl…

The 3SUM problem is a computational problem that asks whether a given set of integers or real numbers contains three distinct elements whose sum is zero. A closely related form takes three sets AA, BB, and CC and asks whether there exist a∈Aa \in A, b∈Bb \in B, and c∈Cc \in C with a+b=ca + b = c. The problem is a standard reference point in computational complexity, especially in computational geometry and the study of problems solvable in polynomial time but thought to require nearly quadratic time.

Formulation and basic algorithms

For a set of nn numbers, the most direct method checks every triple, which takes O(n3)O(n^3) time. A standard improvement sorts the numbers first. For each element aa, the algorithm searches the remaining sorted elements for a pair summing to −a-a using two pointers that move inward from both ends. This takes O(n2)O(n^2) time after the initial O(nlog⁡n)O(n \log n) sort, and the sorting step does not dominate. A deterministic O(n2)O(n^2) algorithm of this kind is the baseline that much of the theory is built around.

The three-set version reduces to the same idea. Each element of AA and BB is combined with the sorted elements of CC, so the running time remains quadratic in the input size.

Variants include the decision version (does a solution exist?), the search version (report a solution), and the counting version (count the solutions). The decision version is the most studied. For integers, time complexity results depend on the model of computation, such as the word RAM, the real RAM, or the linear decision tree model.

Hardness and the 3SUM conjecture

In 1995, Gajentaan and Overmars conjectured that no algorithm for 3SUM runs in subquadratic time. They also showed that many geometric problems can be reduced to 3SUM, which made 3SUM a source of conditional lower bounds. A problem is called 3SUM-hard if a subquadratic algorithm for it would yield a subquadratic algorithm for 3SUM.

Erickson later proved an Ω(n2)\Omega(n^2) lower bound for 3SUM in a restricted linear decision tree model, which covers the standard quadratic algorithm. This restricted result did not settle the general question for algorithms that can use arbitrary operations.

The 3SUM conjecture is the hypothesis that 3SUM cannot be solved in strongly subquadratic time, meaning O(n2−δ)O(n^{2-\delta}) time for some fixed δ>0\delta > 0. Over time it has become one of the central hypotheses of fine-grained complexity, alongside conjectures such as the Strong Exponential Time Hypothesis and the hardness of all-pairs shortest paths. Many results that state a problem requires quadratic time, assuming this conjecture, rely on 3SUM-hardness reductions.

Subquadratic algorithms

The original form of the conjecture was refuted. In 2014, Grønlund and Pettie gave a deterministic algorithm for real 3SUM that runs in O(n2/(log⁡n/log⁡log⁡n)2/3)O(n^2 / (\log n / \log\log n)^{2/3}) time and a randomized algorithm that runs in O(n2(log⁡log⁡n)2/log⁡n)O(n^2 (\log\log n)^2 / \log n) time with high probability. They also showed that 3SUM has a decision tree of depth O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) using 4-linear queries. These algorithms save only logarithmic factors, so they do not give a polynomial speedup.

Earlier, Baran, Demaine, and Pătraşcu obtained subquadratic algorithms for integer 3SUM in several models, including the word RAM and cache-oblivious settings. Their approach exploits parallelism through hashing. Later work improved these bounds, including Freund's and Gold and Sharir's work and a deterministic improvement by Chan, which made the bounds simpler and stronger.

Because of these results, the modern form of the conjecture requires the absence of strongly subquadratic algorithms, meaning an improvement by a polynomial factor nδn^{\delta}. The status of this stronger statement is open. Its consequences are still widely accepted in the theoretical computer science community.

Related problems

Several generalizations and variants have been studied:

  • kk-SUM asks for kk numbers summing to zero. Its complexity is linked to 3SUM, and generalizations such as linear degeneracy testing have been analyzed alongside it.
  • Convolution 3SUM is a variant tied to convolution and sometimes solved with the fast Fourier transform. Its hardness is closely related to that of 3SUM.
  • 3SUM with preprocessing allows a preprocessing phase on supersets of the input sets. Chan and Lewenstein showed that, after quadratic preprocessing, integer 3SUM instances can be solved in truly subquadratic time using additive combinatorics.
  • 3POL replaces the sum with a constant-degree polynomial in three variables. Generalizations of the subquadratic algorithms apply to it. Related results cover the general position testing problem, which asks whether three of nn points in the plane lie on a line.
  • 3XOR replaces addition with bitwise exclusive-or, and it is studied for its connections to 3SUM.

Applications and significance

3SUM-hardness is used to explain the apparent quadratic barrier for many problems in computational geometry, including certain point-line and polygon problems. Its conjectured hardness also connects to triangle enumeration in graph theory, where a variant of the conjecture gives lower bounds for listing triangles in sparse graphs. Work on dynamic data structures and string matching has used 3SUM-based reductions as well.

In practice, the quadratic algorithm is widely used for moderately sized inputs, and the subquadratic algorithms are mainly of theoretical interest because their constant factors and logarithmic savings are small. The problem has also shaped research on randomized algorithms and parallel computing, since the best subquadratic results for integers exploit parallelism and hashing.

Limitations of current knowledge

No algorithm is known that solves 3SUM in strongly subquadratic time on general real or integer inputs. Conversely, no proof rules out such an algorithm. The gap between the O(n2)O(n^2) upper bound and the conjectured Ω(n2)\Omega(n^2) lower bound is therefore unresolved. Results that depend on the 3SUM conjecture are conditional: they hold if the conjecture is true, and they may be weakened or invalidated by future algorithms that improve the known bounds.

References

  1. Deterministic 3SUM-Hardnessarxiv.org
  2. The monitoring problem for timed automataarxiv.org
  3. Subquadratic Algorithms for 3SUM Ilya Baran Erik D. Demaine Mihai Pˇatra¸scupeople.csail.mit.edu
  4. Chapter 16: 3SUM-Hardness: A Method for Obtaining Quadratic Lower Boundscs.umd.edu
  5. Threesomes, Degenerates, and Love Trianglesarxiv.org
  6. [1612.02384] Subquadratic Algorithms for Algebraic Generalizations of 3SUMarxiv.org
  7. Data Structures Meet Cryptography: 3SUM with Preprocessingarxiv.org
  8. Sumsets, 3SUM, Subset Sum: Now for Real!arxiv.org
  9. Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy∗†drops.dagstuhl.de
  10. Improved Subquadratic 3SUMlink.springer.com
  11. 3SUM, 3XOR, Triangles Zahra Jafargholi∗ Emanuele Viola∗ September 24, 2014ccs.neu.edu