Theorem 22 — APSP in steps
ProvedTrulySubcubicAPSP.apspFor every fixed , there exist one finite deterministic word-RAM program , one natural constant , and one step-bound function that work for every input size , including , and for every word width . All encoded input numbers have absolute value at most . The run must halt with the specified verdict and output within steps.
For a directed -vertex graph with integer weights and no negative-weight closed walk, accept and compute every exact shortest-path distance in
Each ordered vertex pair receives a flag and a distance. Reachable pairs have flag one and an attained minimum path weight; unreachable pairs have flag zero and an unconstrained distance slot. Negative edge weights and missing edges are permitted. Empty paths give diagonal distance zero. No assumptions about other algorithms appear in the theorem.
This is the corresponding known result extracted from the source formalization, presented here as an open proof obligation.
/- Copyright (c) 2026 Anthropic, PBC. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. SPDX-License-Identifier: Apache-2.0 -/ import Definitions.Def_TrulySubcubicAPSP_Problems set_option autoImplicit false set_option relaxedAutoImplicit false
theorem TrulySubcubicAPSP.apsp :
TrulySubcubicAPSP.APSP.SolvedInTime 2.99942 := by sorryRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex independent sub-agent)
For every natural number , including zero, there exist a finite program , natural numbers , and a function such that for every natural number , with the following uniform correctness property. For every natural number , including zero, consider any directed graph specified by assigning to each ordered pair of vertices in either no edge or an integer edge weight. A path is a finite sequence of composable directed edges, vertices may repeat, its weight is the sum of its edge weights, and each vertex also has an empty path to itself of weight zero. Assume that every path from any vertex to itself has nonnegative weight. Encode the graph as a list of its edge-presence indicators, each for an edge and otherwise, followed by its edge weights, with zero substituted for an absent edge, using increasing row order and within each row increasing column order for both matrices. If every integer in this list satisfies , then for every natural word width , with the logarithm term interpreted as zero at , halts and accepts within steps. In its final memory, let and be the signed values at addresses and , respectively. For every , either , there exists a path from to of weight , and for every integer that is the weight of a path from to ; or and no path from to of any integer weight exists. In the second case the distance cell is unrestricted, and other final memory cells are unrestricted. Here the machine has a total memory indexed by all integers, storing -bit words; loading an integer and performing addition, subtraction, or multiplication reduces modulo , and signed readings use the two's-complement integer represented by the word (zero when ). The finite program may use instructions that write the constant , add, subtract, or multiply two directly addressed words into a directly addressed cell, load indirectly into a directly addressed cell, store indirectly from a directly addressed cell, branch to a fixed natural-number program position when a directly addressed word has negative signed value, accept, or reject. Direct cell addresses are arbitrary integer constants; indirect addresses are signed readings of address words. Execution begins at program position zero; each instruction costs one step, including acceptance and rejection, nonhalting instructions proceed to the next position except for a taken branch, and a position outside the program rejects in one step. Initially cell zero contains , the following cells contain the input list in order, and every other cell contains zero, all encoded as -bit words. The same work for all these , graphs, and widths, but may depend on ; the specified exponent is the exact rational number . There is no requirement that or be positive; if , the width requirement includes . The time inequality imposes no bound at or , although correctness and termination within steps are still required there. The empty path and the nonnegativity assumption entail and for every vertex. At the graph and its input list are empty, the assumptions about closed paths and input magnitudes and all output conditions are vacuous, and the machine must still accept. Exponentiation uses natural-number powers, in particular even at .
Confirmed by the mission captain (proposal self-audit).