Proof of `Polynomial-time RAM construction of a uniform short-path flow`

groundedproofs/Lax455465Proofs/RamUniformShortPathFlow.lean · lax-455465

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

One fixed polynomial-time RAM program constructs the rational short-path flow of Theorem 18, with universal constants 32768 and 8192.

Proof strategy

The program reads the source graph, computes the maximum incident capacity, and invokes the registered exact LP solver on successive layered networks. It implements the stopping test and extracts the selected primal solution by deterministic positive-path traversal, bottleneck subtraction, and online cycle erasure. Conservation and capacity invariants certify the actual emitted records. A common denominator lattice bounds every residual word independently of the number of updates. The complete execution has polynomial word and instruction bounds; compiler simulation and a bounded interpreter establish the registered uniform RAM predicate on every input.