Math Conjectures

APSP Hypothesis

OPENMajorConjectureProposed c. 2010 · Standard version

Canonical statement

For every ε>0\varepsilon>0, there is no O(n3−ε)O(n^{3-\varepsilon})-time word-RAM algorithm which, given an nn-vertex directed graph with O(log⁡n)O(\log n)-bit integer edge weights and no negative directed cycle, outputs the shortest-path distance for every ordered pair of vertices. The distance from uu to vv is the minimum total weight of a directed uu-to-vv path, or +∞+\infty if no such path exists.
View source LaTeX
For every \(\varepsilon>0\), there is no
\(O(n^{3-\varepsilon})\)-time word-RAM algorithm which, given an
\(n\)-vertex directed graph with \(O(\log n)\)-bit integer edge weights
and no negative directed cycle, outputs the shortest-path distance for
every ordered pair of vertices. The distance from \(u\) to \(v\) is the
minimum total weight of a directed \(u\)-to-\(v\) path, or \(+\infty\)
if no such path exists.
TCS-019:[VWilliamsWilliams2010APSP][AbboudVWilliams2014][VWilliams2018FineGrained]
Theoretical computer scienceOperations research

Notes

The APSP hypothesis asserts that all-pairs shortest paths on an nn-vertex directed graph with O(log⁡n)O(\log n)-bit integer weights and no negative cycle admits no O(n3−ε)O(n^{3-\varepsilon})-time word-RAM algorithm for any ε>0\varepsilon>0. Classical dynamic programming solves the problem in cubic time, and the hypothesis, whose modern form emerged around 2010, says this exponent is essentially optimal. Its central role rests on the subcubic equivalences of Vassilevska Williams and Williams, who showed that APSP and a family of related path, matrix, and triangle problems either all admit truly subcubic algorithms or none do [VWilliamsWilliams2010APSP].

Matrix-multiplication and weight-scaling techniques yield improvements in restricted weight regimes, but no truly subcubic algorithm for the general problem is known, nor any matching unconditional lower bound. The hypothesis underlies strong conditional lower bounds, including for dynamic problems [AbboudVWilliams2014], and its place among the core assumptions of fine-grained complexity is surveyed by Vassilevska Williams [VWilliams2018FineGrained].

The hypothesis remains open: refuting it requires an O(n3−ε)O(n^{3-\varepsilon})-time algorithm for general integer weights, while proving it lies beyond current lower-bound techniques.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.