Native exact LP execution for a canonical rational program
ProvedLax109476Proofs.RamSolverCanonicalExecution.solve_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a rational LP and the size of its canonical encoding. With and the published initialized source and workspace predicates, the actual solver command produces its complete certificate result within instructions:
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamSolverCanonicalExecution end Lax109476Proofs.RamSolverCanonicalExecution
Formal statement
theorem Lax109476Proofs.RamSolverCanonicalExecution.solve_spec_native : ∀ (m n w : Nat) (P : Lax109476.LinearProgram.Program Rat m n),
@LE.le Nat instLENat
(Lax109476Proofs.RamUniformSolverBounds.wordWidth
(Lax759944.BinaryWordEncoding.bitSize (@Lax109476.RationalEncoding.encodeProgram m n P)))
w →
Lax808846Proofs.Reasoning.Spec
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w)
(@Lax109476Proofs.RamSolverCanonicalExecution.Input m n
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w)
P)
Lax109476Proofs.RamExactSolverProgram.solve (@Lax109476Proofs.RamSolverFinish.Result m n P)
(Lax109476Proofs.RamUniformSolverBounds.instructionBound
(Lax759944.BinaryWordEncoding.bitSize (@Lax109476.RationalEncoding.encodeProgram m n P))) := by sorrySource