APSP in word-RAM steps
ProvedAPSPExponentImprovement.apspCompute all exact shortest-path distances in a directed n-vertex graph with integer weights and no negative-weight closed walk in deterministic word-RAM steps, where 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 , there must be a single finite deterministic word-RAM program, a word-width constant , and a time bound working for all sizes and all word widths . Every encoded input integer has absolute value at most . Correctness includes ; the asymptotic bound is required for . The machine must accept and write the required exact output. There are no hypotheses assuming the supporting algorithms or any complexity conjecture.
import Definitions.Def_TrulySubcubicAPSP_Problems set_option autoImplicit false set_option relaxedAutoImplicit false
theorem APSPExponentImprovement.apsp :
TrulySubcubicAPSP.APSP.SolvedInTime 2.9983 := by sorryRead-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 , there exist a finite machine program , natural numbers and , and a function such that, for every natural number , ; the asserted rational time exponent is exactly . The witnesses may depend on but are chosen uniformly before every instance size, graph, and word width. For every natural number , every instance of size described below whose every encoded input integer has absolute value at most , and then every natural word width , with the logarithm at taken to be , must halt within steps with verdict true and satisfy the required output condition. An instance of size is a function on ordered pairs of vertices in 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 to of weight is defined inductively: the empty path from any vertex to itself has weight , and an edge of weight from to a vertex followed by a path of weight from to gives a path from to of weight ; vertices and edges may repeat. The instance requirement means that for every vertex and every integer , existence of a path from to itself of weight implies . The input first gives an row-major presence matrix with entry for an existing edge and for an absent edge, then an row-major matrix of edge weights, using at absent edges, for a total of integers. The presence and weight entries for are therefore initially in memory cells and . 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 in cell . For every ordered pair , put , let be the signed integer in final memory cell , and let be the signed integer in the following cell . The required output is precisely the disjunction: either , there is a path from to with total weight , and for every integer , every path from to with weight satisfies ; or and for every integer there is no path from to of weight . In the second case the distance cell is unconstrained. Thus the output cells are interleaved flag-distance pairs in row-major order of . The machine model is as follows: 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 -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 , 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 ; there is no separate requirement that intermediate values avoid overflow. Execution starts at program position ; 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 , converted to a -bit word, in cell , followed by the specified input list in cells , 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 is allowed to be zero, so its width threshold does not by definition exclude . The algorithm and its step bound must work for every allowed width, with no upper bound on , while the asymptotic inequality constrains only and correctness also includes and . For , 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 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 to be and , respectively. In particular at 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 or . The natural-number magnitude bound uses , with no input entries at . 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 .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.