3SUM Hardness

Imagine you have a list of n integers and you want to know: do any three of them add up to exactly zero?

This is the 3SUM problem, and at first glance it looks trivially easy. You can check every triple in $O(n^{3})$ steps by brute force. With a sort-and-scan trick you can do it in $O(n^{2})$ — sort the list, then for each element a, walk two pointers inward from both ends looking for b and c such that a + b + c = 0.

Can you do better? Nobody knows. For over 30 years, every attempt to break the $n^{2}$ barrier has failed. No sub-quadratic algorithm has been found, and computer scientists conjecture that none exists.

That conjecture — the 3SUM Conjecture — would be just a curious open question, except for one thing: researchers found they could reduce dozens of computational geometry problems to 3SUM. Proving any of those problems is sub-quadratic would automatically disprove the 3SUM Conjecture, and vice versa. The conjecture became the bedrock of an entire web of conditional lower bounds, a way to say "this problem is at least as hard as 3SUM" without solving P vs NP first.

Below is a sorted list of integers. The classic two-pointer algorithm fixes each element a and scans the rest with two pointers — one from the left, one from the right — looking for b and c such that a + b + c = 0. Click Step to advance one outer iteration, or Run to finish instantly.

<p class="hint">{{hint}}</p>
<div id="array-row" class="array-row"></div>
<div class="info-row">
  <span id="info-a" class="badge badge-a">{{badge_a_init}}</span>
  <span id="info-b" class="badge badge-b">{{badge_b_init}}</span>
  <span id="info-c" class="badge badge-c">{{badge_c_init}}</span>
  <span id="info-cmp" class="badge badge-cmp">{{comparisons_init}}</span>
</div>
<div id="status" class="status">{{status_init}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run"  type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.array-row { display: flex; gap: 5px; flex-wrap: wrap; margin: .5rem 0 .6rem; }
.cell {
  width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
  font: 700 14px ui-monospace, monospace; border-radius: 8px;
  border: 2px solid #c5cdd6; background: #edf1f5; color: #2b3a4a;
  transition: background .15s, border-color .15s;
}
.cell.fixed  { background: #dbe4ff; border-color: #7091e6; color: #1d3557; }
.cell.left   { background: #fff3cd; border-color: #f0a500; color: #5a3e00; }
.cell.right  { background: #fde8c8; border-color: #e07b39; color: #5a2500; }
.cell.found  { background: #c3f0ca; border-color: #2e9e51; color: #0a4020; }
.info-row { display: flex; gap: .4rem; flex-wrap: wrap; margin: .3rem 0; }
.badge { font: 600 12px ui-monospace, monospace; padding: .2rem .55rem; border-radius: 6px; }
.badge-a   { background: #dbe4ff; color: #1d3557; }
.badge-b   { background: #fff3cd; color: #5a3e00; }
.badge-c   { background: #fde8c8; color: #5a2500; }
.badge-cmp { background: #f0f0f0; color: #333; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .95rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Count the comparisons. For n numbers the algorithm makes at most n × n pointer steps — hence $O(n^{2})$. Each time you add one more number, the worst-case work grows by an entire extra row. The open question is whether a fundamentally smarter strategy could trim that to, say, $O(n^{1.9})$ — and so far, nobody has found one.

How hard is 3SUM, really?

• Status: open conjecture. The 3SUM Conjecture — that no algorithm solves 3SUM in $O(n^{2-\varepsilon})$ time for any $\varepsilon > 0$ — has never been proven. It is a widely believed assumption, not a theorem.
• Quadratic is the best known. The two-pointer algorithm (Gajentaan & Sharir, 1995) achieves $O(n^{2})$ after sorting in $O(n \log n)$. Subsequent work shaved off logarithmic factors; a 2014 result by Grønlund & Pettie reached $O(n^{2} / (\log n / \log \log n)^2)$, but still quadratic in the big-O sense.
• 3SUM-hard problems. Via reductions, at least dozens of problems in computational geometry are 3SUM-hard: deciding whether any three points among n are collinear, whether a set of n triangles cover a polygon, whether a query point is in the union of n triangles, and many more. A sub-quadratic algorithm for any of them would shatter the conjecture for all.
• Fine-grained complexity. This is the broader program: assume a hard problem (3SUM, APSP, SETH) and derive conditional lower bounds for other problems. It gives us a precise complexity landscape without needing to resolve P vs NP.
• Sub-quadratic for special inputs. For integer inputs in [−u, u], a randomized FFT-based algorithm runs in $\tilde{O}(n + u)$ time, which beats $O(n^{2})$ when u is small. Real-number 3SUM over arbitrary inputs remains open.

The 3SUM Conjecture sits in the same philosophical territory as P vs NP: almost certainly true, enormously useful as an assumption, and frustratingly unproven.

The 3SUM Conjecture is not just theoretical tidiness — it directly explains why practitioners hit quadratic walls in real systems:

• Computational geometry: collinearity testing (are any 3 of n points on a line?), triangle containment queries, polygon union tests, and motion planning obstacles are all 3SUM-hard. The $O(n^{2})$ algorithms you find in textbooks may genuinely be optimal.
• Geographic information systems: spatial overlay operations — intersecting two layers of n polygons — reduce to 3SUM-style checks. A sub-quadratic breakthrough would transform GIS software.
• Collision detection in games and robotics: detecting whether any three swept shapes intersect touches 3SUM-hard subproblems. The quadratic cost is a known engineering constraint.
• Fine-grained algorithm design: the conjecture teaches algorithm designers why they can't seem to break a barrier, not just that they can't. It is a map of what is fundamentally hard versus what is merely hard to engineer.
• Cryptographic hash functions: some constructions rely on sum-zero problems being hard in structured domains — a connection to the broader theory of subset sum and lattice problems.

Understand 3SUM-hardness and you understand why many of the fastest practical geometry algorithms stop improving — not for lack of effort, but because the conjecture says the floor may already be underfoot.

The 3SUM Conjecture is one of the most productive open questions in algorithm theory. Nobody has proven it, nobody has refuted it — but its shadow falls across dozens of computational geometry problems, each of them unable to escape the quadratic bound unless 3SUM itself does.

That is the power of fine-grained complexity: even without resolving P vs NP, we can map which problems are linked, which hardness is shared, and where the quadratic floor is most likely to hold. The next time a geometry algorithm refuses to go below $O(n^{2})$, you may be hitting the 3SUM Conjecture in disguise — and no amount of clever engineering will help if the conjecture is true.