Proof of `Deterministic polynomial-time product flow–cut algorithm`
groundedproofs/Lax455465Proofs/RamProductAlgorithm.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.
Description
One fixed RAM program constructs the joint flow–cut certificate in both edge models, with universal approximation constant 512.
Proof strategy
Compile the complete valid-input pipeline: the registered exact LP solver, rational directed distances, deterministic metric rounding, and certificate output. A bounded interpreter computes the source word width and clock from the actual binary input size. Its execution and polynomial resource proofs apply to every input word. On valid networks its clock contains the complete source execution, so it emits exactly the certified output. Compiler transfer establishes the existing uniform word-RAM predicate at every sufficient host word width.