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 is the decision problem of whether a finite numeric input contains three distinct elements whose sum is exactly zero. Its elementary witness contrasts with near-quadratic known algorithms and model-sensitive bounds. The old literal quadratic conjecture was refuted by logarithmic improvements; current fine-grained uses typically assume no strongly subquadratic algorithm under a specified model. Sorting plus a two-pointer scan gives a familiar quadratic approach.

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.

Scope of Application¶

3SUM applies in algorithm design and related work only when its carrier, rules, and evidence boundary are explicit. Use it in algorithms, computational geometry, decision trees, integer computation, and fine-grained complexity with set/list convention, numeric domain, encoding, distinctness, target, decision versus enumeration, computation model, randomization, runtime, space, and conjectural status 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. The central simple predicate–algorithmic difficulty tradeoff is this: Three-term equality is easy to state but expensive to search at scale.

Abstract Reasoning¶

Use three linked moves: formalize the exact witness and input conventions; choose a computation model and cost measure; establish an upper bound with algorithm and invariants. As a collapse test, the identity is lost when the witness uses a different arity, values outside the input, an approximate predicate without declaration, or an unstated cost model for a complexity claim.

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. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG.

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