OP-0032OpenAlgorithms and data structures

The 3SUM conjecture

Is there any truly subquadratic algorithm for finding three numbers summing to zero?

MSC 68W · Algorithms in computer science

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Given $n$ integers, decide whether some three of them sum to zero. Conjecture: no algorithm solves 3SUM in time $O(n^{2-\varepsilon})$ for any $\varepsilon > 0$ on a word RAM with $O(\log n)$ -bit words.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

3SUM is the anchor of fine-grained complexity: dozens of problems in computational geometry and string algorithms have been shown to require quadratic time unless 3SUM does not. The conjecture plays the role $\mathrm{P}\ne\mathrm{NP}$ plays for NP-hardness, but at the level of polynomial exponents.

Known partial results

Grønlund and Pettie (2014) gave an $O(n^2/(\log n / \log\log n)^{2/3})$ algorithm, showing the exact quadratic bound is false, though the improvement is subpolynomial.
Chan improved the polylogarithmic savings further.
In the decision-tree model, $O(n^{3/2})$ comparisons suffice (Kane, Lovett, Moran), which shows any proof of the conjecture must use more than an information-theoretic argument.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.