APSP and 3SUM hypotheses: no n^(3−ε) APSP or n^(2−ε) 3SUM on polynomially bounded integers
Difficulty 32: before October 2026 refuting either hypothesis would have sat near 78 (decades of only subpolynomial savings, much like SETH at 88 but with no P ≠ NP barrier); a refutation by the leading experts in the area, with a mechanism in established algebraic techniques, is now under review, so the remaining distance is mainly verification. This is a larger discount than UGC (70) received, because the claim is human-written by specialists rather than an unreviewed AI manuscript. If the preprint is confirmed the difficulty drops to about 5; if it fails it returns to the 75–80 band. Application value 24: the savings are tiny and the algorithms galactic, so the value is in redirecting algorithm design. Leverage 66: hundreds of conditional lower bounds depend on these hypotheses, below SETH (81) and ω (72).
The problem
Two beliefs, that shortest routes between all pairs need n³ steps and 3SUM needs n², behind hundreds of speed limits.
- 1Shortest paths need n³ steps for decades
- 23SUM needs n² steps for decades
- 3Hundreds of problems tied to them
- 4Hypothesis: no polynomial speed-up
- 52026 preprint claims one; unconfirmed
Statements. APSP hypothesis: for every , all-pairs shortest paths on -vertex directed graphs with integer edge weights in (no negative cycles) cannot be solved in time on a word RAM with -bit words. for every , deciding whether integers in contain three that sum to zero cannot be done in time, even with randomisation. The question: are they true?
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Cap sets in 𝔽₃ⁿ: the growth constant, between 2.2202 and 2.7552Combinatorics · D58
- Step 2
- Matrix multiplication exponent: is ω = 2, i.e. n^(2+o(1)) operations for n×n products?Complexity Theory · D82
- Then
- APSP and 3SUM hypotheses: no n^(3−ε) APSP or n^(2−ε) 3SUM on polynomially bounded integersThis problem
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm
- Step 4
- Then
- APSP and 3SUM hypotheses: no n^(3−ε) APSP or n^(2−ε) 3SUM on polynomially bounded integersThe problem
State of the art
Status before the claim. The best APSP algorithm for polynomially bounded integers before 2026 ran in time (Williams, STOC 2014 for real weights, with refinements by Chan and Williams, SODA 2016 via derandomisation), and for 3SUM the best was (Chan, 2018 and follow-ups). Neither was truly subpolynomially faster than the textbook bound, and Abboud, Vassilevska Williams and others had built an extensive web of equivalences (APSP is subcubic-equivalent to min-plus product, negative-triangle and replacement paths; Vassilevska Williams and Williams, FOCS 2010). Carmosino et al. (2016) showed that nondeterministic SETH rules out deterministic fine-grained reductions from SAT to 3SUM or APSP.
Realistic applications
If correct, conditional lower bounds based on these hypotheses are void and algorithm designers should look for truly subcubic and subquadratic algorithms for many problems (replacement paths, negative-triangle, nearest-point problems, 3SUM-hard geometric problems). The exponents are tiny (), and the algorithms are galactic because they rest on rectangular fast matrix multiplication, so no immediate practical speed-up is implied.
What counts as solved
Resolved negatively (hypotheses false) when a truly subcubic APSP or truly subquadratic 3SUM algorithm for polynomially bounded integers is accepted by experts, for example the Alman–Vassilevska Williams algorithms after refereed publication or independent verification. Resolved positively only by an unconditional proof of the stated lower bounds. If a flaw is found in the 2026 preprint, both hypotheses revert to open with no credible claim.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
Refuting the hypotheses needs a truly subcubic APSP or truly subquadratic 3SUM algorithm, which is an algorithm with a proof; proving them needs unconditional lower bounds beyond current techniques. No formal running-time framework exists in Mathlib, so experts verify the manuscript. If the 2026 preprint has a flaw, both hypotheses revert to open.
Claims under verification
+ add a claimWhere the work is
Verification is mathematical (checking a long proof), with some computation to test exponents numerically.
Bottlenecks
ranked by votes- #1TheoryExpert verification of a long, technical proof
The argument modifies rectangular matrix multiplication machinery and sparse-graph triangle detection; verification capacity is limited to a small group of fine-grained and algebraic-algorithms experts.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Oct 5, 2026Claimed refutation of the 3SUM and APSP hypothesessource
Alman and Vassilevska Williams posted deterministic O(n^1.9992) 3SUM and O(n^2.9995) APSP algorithms for polynomially bounded integers, refuting both hypotheses if correct; unrefereed.
- May 31, 2014Faster APSP via circuit complexitysource
Williams gave an n^3/2^(Ω(√log n))-type algorithm, the best truly sub-polynomial speedup known for decades.
- Oct 1, 2010APSP subcubic equivalencessource
Vassilevska Williams and Williams proved APSP is equivalent to several problems under subcubic reductions (FOCS 2010).
- Oct 1, 19953SUM-hardness in geometrysource
Gajentaan and Overmars introduced 3SUM-hardness for computational-geometry problems (Comput. Geom., October 1995; day approximate).