Analytic feasibility certificate for the APSP exponent 2.9929479187094
ProvedApspBound.apsp_feasibilityConsider the aligned-cache reduction for All-Pairs Shortest Paths (APSP), whose cost accounting is organized into 47 inequalities spanning the geometric regimes of the reduction and the four cost phases (scalar stages and cyclic stages ). Each inequality has the form , where is affine in the entropic cost parameters (box/cache formation), (box gain) and (residual query exponent), and the target is either (a positivity or geometry condition) or the stage saving . This theorem is the closed analytic feasibility certificate: at the true real-logarithm parameters , , —obtained from the binary-entropy analysis and pinned inside their certified rational enclosures by proved logarithm bounds—every one of the 47 cost inequalities holds with a common strictly positive slack ; in particular the check family has exactly 47 members. Equivalently, each of the six cost categories of the written reduction saves strictly more than below cubic time, uniformly over every stage, certifying that the exponent (i.e. ) is analytically feasible for the reduction's cost model. The theorem is a certificate of these 47 cost inequalities at exact real-logarithm parameters; it does not by itself constitute a complete word-RAM algorithm for APSP.
import Definitions.Def_ApspBound_Model
import Definitions.Def_ApspBound_Model
theorem ApspBound.apsp_feasibility :
ApspBound.Numerical.checks.length = 47 ∧
∀ check ∈ ApspBound.Numerical.checks,
(check.target : ℝ) + ApspBound.Analytic.uniformSlack <
ApspBound.Analytic.evalReal check.expression := by sorry