Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

APSP in O(n2.9983)O(n^{2.9983})O(n2.9983) word-RAM steps

Proved
APSPExponentImprovement.apsp

by wurtle · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsapspexact-trianglefine-grained-complexityword-ram

Compute all exact shortest-path distances in a directed n-vertex graph with integer weights and no negative-weight closed walk in O(n2.9983)O(n^{2.9983})O(n2.9983) deterministic word-RAM steps, where 2.9983=29983/100002.9983=29983/100002.9983=29983/10000 exactly. Negative edges and missing edges are permitted. For each ordered vertex pair, output a reachability flag followed by a distance: flag one requires an attained minimum path weight, and flag zero requires that no path exists, with the distance slot then unrestricted. Empty paths give diagonal distance zero. For every fixed natural weight exponent κ\kappaκ, there must be a single finite deterministic word-RAM program, a word-width constant bbb, and a time bound TTT working for all sizes nnn and all word widths W≥b(Nat.log2⁡(n)+1)W\ge b(\operatorname{Nat.log2}(n)+1)W≥b(Nat.log2(n)+1). Every encoded input integer has absolute value at most nκn^\kappanκ. Correctness includes n=0,1n=0,1n=0,1; the asymptotic bound is required for n≥2n\ge2n≥2. The machine must accept and write the required exact output. There are no hypotheses assuming the supporting algorithms or any complexity conjecture.

Preamble
import Definitions.Def_TrulySubcubicAPSP_Problems

set_option autoImplicit false
set_option relaxedAutoImplicit false
Formal statement
theorem APSPExponentImprovement.apsp :
    TrulySubcubicAPSP.APSP.SolvedInTime 2.9983 := by sorry
Source
https://arxiv.org/html/2610.06783v1#S6; Theorems 17 and 19, conclusion footnote 10; https://people.csail.mit.edu/rrw/finding-full.pdf; https://theory.stanford.edu/~virgi/tria-mmult-jv.pdf
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex; the precise model variant is not exposed to this agent)

For every natural number κ\kappaκ, there exist a finite machine program PPP, natural numbers bbb and KKK, and a function T:N→NT:\mathbb N\to\mathbb NT:N→N such that, for every natural number n≥2n\ge 2n≥2, T(n)10000≤Kn29983T(n)^{10000}\le K n^{29983}T(n)10000≤Kn29983; the asserted rational time exponent is exactly 2.9983=29983/100002.9983=29983/100002.9983=29983/10000. The witnesses may depend on κ\kappaκ but are chosen uniformly before every instance size, graph, and word width. For every natural number nnn, every instance of size nnn described below whose every encoded input integer has absolute value at most nκn^\kappanκ, and then every natural word width W≥b(⌊log⁡2n⌋+1)W\ge b(\lfloor\log_2 n\rfloor+1)W≥b(⌊log2​n⌋+1), with the logarithm at n=0n=0n=0 taken to be 000, PPP must halt within T(n)T(n)T(n) steps with verdict true and satisfy the required output condition. An instance of size nnn is a function www on ordered pairs of vertices in {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} whose value is either absent or an integer edge weight, together with the requirement that every finite closed path has nonnegative total weight. A path from iii to jjj of weight ddd is defined inductively: the empty path from any vertex to itself has weight 000, and an edge of weight eee from iii to a vertex kkk followed by a path of weight fff from kkk to jjj gives a path from iii to jjj of weight e+fe+fe+f; vertices and edges may repeat. The instance requirement means that for every vertex iii and every integer ddd, existence of a path from iii to itself of weight ddd implies 0≤d0\le d0≤d. The input first gives an n×nn\times nn×n row-major presence matrix with entry 111 for an existing edge and 000 for an absent edge, then an n×nn\times nn×n row-major matrix of edge weights, using 000 at absent edges, for a total of 2n22n^22n2 integers. The presence and weight entries for (i,j)(i,j)(i,j) are therefore initially in memory cells 1+in+j1+in+j1+in+j and 1+n2+in+j1+n^2+in+j1+n2+in+j. The input bound applies to both encoded matrices and hence to every present edge weight, but does not separately bound path weights or the size word nnn in cell 000. For every ordered pair i,j<ni,j<ni,j<n, put q=in+jq=in+jq=in+j, let fff be the signed integer in final memory cell 1+2n2+2q1+2n^2+2q1+2n2+2q, and let ddd be the signed integer in the following cell 1+2n2+2q+11+2n^2+2q+11+2n2+2q+1. The required output is precisely the disjunction: either f=1f=1f=1, there is a path from iii to jjj with total weight ddd, and for every integer eee, every path from iii to jjj with weight eee satisfies d≤ed\le ed≤e; or f=0f=0f=0 and for every integer eee there is no path from iii to jjj of weight eee. In the second case the distance cell is unconstrained. Thus the 2n22n^22n2 output cells are interleaved flag-distance pairs in row-major order of (i,j)(i,j)(i,j). The machine model is as follows: PPP is a finite list of instructions with fixed integer cell addresses and natural-number jump destinations, memory is a total function from integer addresses to WWW-bit words, and each word is interpreted as a signed integer when used as an indirect address, tested for negativity, or read as output. An instruction can write the constant 111, add, subtract, or multiply two words into a directly addressed cell, load from the address given by the signed contents of another cell, store a word at the address given by another cell, jump to a specified program position if a specified cell is negative, accept, or reject. Word arithmetic and conversion of input integers to words are modulo 2W2^W2W; there is no separate requirement that intermediate values avoid overflow. Execution starts at program position 000; writes and untaken branches advance to the next position, and a program position beyond the list acts as reject. Every executed instruction, including accept or reject, consumes one step; a run with zero remaining steps has no result. Initial memory contains the integer nnn, converted to a WWW-bit word, in cell 000, followed by the specified input list in cells 1,2,…1,2,\ldots1,2,…, likewise converted to words; all other cells, including negative addresses, initially contain zero. Halting is witnessed by a Boolean verdict and a final total memory, and these problems require the verdict to be true as well as the stated output condition. No condition is imposed on final memory outside the specified output cells. The natural number bbb is allowed to be zero, so its width threshold does not by definition exclude W=0W=0W=0. The algorithm and its step bound must work for every allowed width, with no upper bound on WWW, while the asymptotic inequality constrains only n≥2n\ge 2n≥2 and correctness also includes n=0n=0n=0 and n=1n=1n=1. For n=0n=0n=0, the vertex set and input list are empty, the instance restriction and magnitude hypothesis are vacuous, and there are no output pairs to constrain; nevertheless the program must accept within T(0)T(0)T(0) steps for every allowed width. For any nonempty instance, the empty path and the nonnegative-closed-path requirement force the output flag and distance for every diagonal pair (i,i)(i,i)(i,i) to be 111 and 000, respectively. In particular at n=1n=1n=1 the unique output pair has these values whether or not the loop edge is present; if that edge is present then its weight must be nonnegative, and the magnitude bound restricts it to 000 or 111. The natural-number magnitude bound uses 00=10^0=100=1, with no input entries at n=0n=0n=0. Graphs that do not satisfy the nonnegative-closed-path condition are outside the instance type and carry no correctness requirement in this assertion. There is no assertion of a single program uniform across all κ\kappaκ.

Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by wurtle · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me