Native linear-programming completion and certificate output
ProvedLax109476Proofs.RamSolverFinish.finish_specalgorithmscomputational-complexitygraph-theory
For a rational linear program , assume the decoded input and reconstruction workspace satisfy the completion precondition, at the prescribed word width and stack depth. The fixed completion command returns a valid certificate and appends its encoding to the previous output within
Signed rational coefficients are handled through exact denominator clearing.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax109476Proofs.RamSolverFinish.finish_spec : ∀ (m n N w : ℕ) (P : Lax109476.LinearProgram.Program ℚ m n),
Lax109476Proofs.RamSolverBranchBounds.wordWidth
(Lax109476Proofs.RamCertificateSetup.parameter
(Lax759944.BinaryWordEncoding.bitSize (Lax109476.RationalEncoding.encodeProgram P))) ≤
w →
Lax109476Proofs.RamRationalReconstruction.depthBound
(Lax109476Proofs.RamRecoverFeasibleSystem.recoveryBits
(Lax109476Proofs.RamCertificateSetup.parameter
(Lax759944.BinaryWordEncoding.bitSize (Lax109476.RationalEncoding.encodeProgram P)))) +
1 ≤
N →
Lax808846Proofs.Reasoning.Spec (2 ^ w) (Lax109476Proofs.RamSolverFinish.Input P N)
(Lax109476Proofs.RamCertificateSetup.save.seq Lax109476Proofs.RamExactSolverProgram.chooseCertificate)
(Lax109476Proofs.RamSolverFinish.Result P)
(Lax109476Proofs.RamSolverFinish.instructionBound
(Lax759944.BinaryWordEncoding.bitSize (Lax109476.RationalEncoding.encodeProgram P))) := by sorrySource