3SUM¶

The computational decision problem of determining whether a set or list of numbers contains three distinct input elements whose sum is zero, with complexity stated relative to the numeric domain and computation model.

Version: v1 · 2026-09-28 · History
Domain-specific #: 7812
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Fine Grained Complexity, Computational Complexity → Computer Science & Software Engineering

Core Idea¶

3SUM asks whether three distinct input elements sum to zero. The predicate is simple; the abstraction's importance comes from the gap between simple statement, near-quadratic algorithms, model-specific bounds, and its use in conditional reductions.

Sorting plus a two-pointer scan gives a familiar quadratic approach. Faster-than-quadratic logarithmic improvements refute the old literal Ω(n²) conjecture, while the modern conjectural barrier is usually no O(n^(2−ε)) expected-time algorithm under specified models.

Integer ranges can enable convolution or word-level methods unavailable for arbitrary reals. Therefore every runtime or lower-bound claim must state domain, model, randomization, and task variant.

How would you explain it like I'm…

Three Numbers Make Zero

Here's a puzzle: you have a list of numbers, some below zero. Can you find three different ones that add up to exactly zero? That's 3SUM. It's easy to say, but surprisingly hard for computers to solve really fast when the list is huge.

The Zero-Sum Triple Puzzle

3SUM is a computer science puzzle: given a list of numbers, are there three different ones that add up to zero, like 5, −2 and −3? A simple method sorts the list and then slides two pointers in from the ends to look for a match for each number, which takes roughly 'number of items times number of items' steps. Computer scientists have found only small speed-ups over that, and many believe you can't do dramatically better. Because of that, 3SUM is used as a yardstick: if another problem could be solved fast, 3SUM could be too.

3SUM Hardness Benchmark

3SUM: given n numbers, decide whether three distinct elements sum to zero. Sorting followed by a two-pointer scan solves it in roughly n² steps (quadratic time). For a long time people conjectured that you could not beat n² at all, but algorithms faster by logarithmic factors disproved that exact claim. Today the usual conjecture is that no algorithm runs in time n^(2−ε) for any fixed ε > 0, in specified models of computation. Researchers use it for 'conditional' results: if another problem could be solved fast, then 3SUM could be too, so that problem is probably hard. Details matter: whether inputs are integers or real numbers and which computational model is assumed change which techniques are allowed.

3SUM decides whether n input elements contain three distinct ones summing to zero. Its significance comes from the gap between a trivial predicate and the difficulty of beating quadratic time. Sorting plus a two-pointer scan gives an O(n²) algorithm; subsequent algorithms achieving logarithmic-factor improvements refuted the old literal Ω(n²) conjecture. The modern conjectural barrier is that no algorithm solves 3SUM in O(n^(2−ε)) expected time for any ε > 0, stated relative to a specified model of computation. The problem is used as a source of conditional lower bounds via reductions ('3SUM-hardness'). Because integer inputs from bounded ranges admit convolution-based or word-level methods unavailable for arbitrary reals, every runtime or lower-bound claim must specify the input domain, computational model, whether randomization is allowed, and which task variant is meant.

Structural Signature¶

Sig role-phrases:

finite numeric input. Supplies n values over a declared domain. Constitutive carrier. If altered: Continuous distribution claims are not problem instances.
distinct index triple. Chooses three input occurrences rather than one value reused illicitly. Constitutive witness. If altered: Multiplicity conventions change feasibility.
zero-sum predicate. Requires x+y+z=0 exactly or under a declared variant. Constitutive relation. If altered: Changing target changes the problem instance/variant.
decision output. Returns existence or nonexistence rather than necessarily enumerating all triples. Problem type. If altered: Reporting one heuristic candidate does not solve the decision problem.
computation model. Defines admissible operations and cost. Complexity boundary. If altered: Real RAM, word RAM, decision tree, and bounded integers support different claims.
reduction role. Transfers conditional hardness to other problems. Research consequence. If altered: A reduction requires explicit size and model preservation.

What It Is Not¶

Not 2SUM. Witness arity is three.
Not k-SUM in general. k=3 fixes a distinct complexity regime.
Not closest-to-zero. The decision predicate is exact unless a variant is stated.
Not one universal quadratic lower bound. Known and conjectured bounds are model-specific.

Scope of Application¶

3SUM applies in algorithm design and related work only when its carrier, rules, and evidence boundary are explicit.

Algorithm design. Compares sorting, hashing, and specialized methods.
Computational geometry. Supports conditional lower-bound reductions.
Fine-grained complexity. Uses the no-strongly-subquadratic conjecture.
Decision trees. Studies query/linear-comparison complexity.
Integer algorithms. Exploits bounded range and convolution.

Clarity¶

State input as set or multiset/list, numeric domain and encoding, distinct-index rule, exact target, decision/enumeration variant, n and value range, deterministic/randomized model, expected/worst-case time, space, and reduction assumptions.

Manages Complexity¶

3SUM isolates how representation and computation model shape difficulty. For sorted real inputs, a fixed first element and inward-moving pair pointers exploit order to inspect O(n²) combinations without enumerating all O(n³) triples. Hashing changes expected-time and space assumptions. Bounded integers allow bit-vector or convolution methods whose cost depends on numeric range N, making O(n+N log N) incomparable with a pure n-bound when N is huge. Linear decision-tree results count a restricted kind of query rather than ordinary machine instructions. Fine-grained reductions use 3SUM as a conditional hardness source, but their conclusion inherits the exact conjecture, model, dimension, precision, and blow-up of the reduction. The 2014 subquadratic logarithmic improvement is a reminder to distinguish Ω(n²) from n^(2−o(1)). Precise asymptotic language is part of the concept's responsible use, not editorial decoration.

Abstract Reasoning¶

Formalize the exact witness and input conventions.
Choose a computation model and cost measure.
Establish an upper bound with algorithm and invariants.
State lower bounds or conjectures with their restrictions.
Audit reductions for size, precision, and model preservation.

Knowledge Transfer¶

The witness-search structure transfers literally to 3SUM variants and reduction targets only through explicit mappings that preserve yes/no instances and complexity scale. Informal claims that a task 'looks quadratic like 3SUM' do not inherit conditional hardness.

Examples¶

Canonical¶

For sorted values [-7,-1,2,5,8], a two-pointer scan with first value -7 finds -7+-1+8=0, certifying YES with three distinct indices.

Mapped back: finite numeric input → five declared integers; distinct index triple → positions of -7,-1,8; zero-sum predicate → exact equality; decision output → YES; computation model → comparison/RAM scan; reduction role → not invoked.

Applied / In Practice¶

A fine-grained lower-bound proof maps each 3SUM instance to a geometric instance of near-linear size and shows YES iff the geometric structure exists, then states that a strongly subquadratic target algorithm would refute the named 3SUM conjecture.

Mapped back: finite numeric input → source instance; distinct index triple → preserved witness; zero-sum predicate → iff reduction; decision output → target decision; computation model → declared RAM/model; reduction role → conditional hardness transfer.

Structural Tensions¶

T1: simple predicate vs. algorithmic difficulty. Three-term equality is easy to state but expensive to search at scale. Diagnostic: Which input structure is the algorithm exploiting?

T2: model generality vs. specialized speed. Bounded integers or decision trees enable results that may not transfer. Diagnostic: Which operations and encodings does the bound assume?

T3: exact lower bound vs. conjectural barrier. Known logarithmic improvements coexist with no strongly subquadratic conjecture. Diagnostic: Is the claim theorem, restricted-model bound, or conjecture?

Structural–Framed Character¶

3SUM is structural-formal and minimally framed. Its vocabulary is mathematical; evaluation is neutral; agency and institutional origin are absent; temporality is algorithmic; robustness depends on exact model. Its finite witness-decision structure is supplied by Computational problem. Its character: a three-element zero-sum existence problem anchoring model-sensitive complexity reasoning.

Structural Core vs. Domain Accent¶

Skeletal core. A finite input admits a yes/no answer exactly when a bounded-size witness satisfies a relation.

Domain-bound accent. Three numeric elements, zero sum, distinct indices, machine models, asymptotic time, and fine-grained reductions specify 3SUM.

Why not prime. Computational Problem supplies the broader genus; 3SUM adds one arity and algebraic predicate.

This entry is a kind of Computational problem.

Strict parent — Computational problem. 3SUM is a decision problem with finite input, witness predicate, and model-dependent resource complexity; the zero-sum triple is the differentia.
Related — k-SUM. It generalizes witness arity and changes bounds.

Relationships to Other Abstractions¶

Current abstraction 3SUM Domain-specific

Parents (1) — more general patterns this builds on

3SUM is a kind of Computational problem Domain-specific

3SUM is a strict kind of Computational Problem: each finite input asks whether a three-element zero-sum witness exists.

Hierarchy path (1) — routes to 1 parentless root

3SUM → Computational problem → Function (Mapping)

Neighborhood in Abstraction Space¶

3SUM sits in a crowded region of the domain-specific corpus (32^nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

2SUM. Tell: Two or three chosen elements?
Subset sum. Tell: Fixed triple or arbitrary subset?
Convolution 3SUM. Tell: Equivalent/reduced variant under what encoding?
3SUM conjecture. Tell: Problem definition or unproved complexity claim?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/3SUM (revision 1321403038).
Preserved source candidate: http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf
Preserved source candidate: https://cs.stackexchange.com/q/37888
Preserved source candidate: http://cs.smith.edu/~orourke/TOPP/P41.html
Preserved source candidate: http://erikdemaine.org/papers/3SUM_Algorithmica/
Preserved source candidate: http://maven.smith.edu/~orourke/TOPP/Welcome.html
Preserved source candidate: http://cs.smith.edu/~orourke/TOPP/P11.html
Preserved source candidate: https://archive.today/20121215035647/http://maven.smith.edu/~orourke/TOPP/Welcome.html
Preserved source candidate: http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.