Total native LP-solver execution on arbitrary word input
ProvedLax109476Proofs.RamSolverTotalExecution.solve_spec_nativealgorithmscomputational-complexitygraph-theory
Let be any finite natural-word list, including malformed encodings, and let be its binary size. Assume and the complete initialized frontend and solver workspace. The fixed command has at most instructions and returns its full outcome: invalid input has validity flag zero and unchanged output, while valid decoded input receives a valid encoded certificate. Thus
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamSolverTotalExecution end Lax109476Proofs.RamSolverTotalExecution
Formal statement
theorem Lax109476Proofs.RamSolverTotalExecution.solve_spec_native : ∀ (xs : List Nat) (w : Nat),
@LE.le Nat instLENat (Lax109476Proofs.RamUniformSolverBounds.wordWidth (Lax759944.BinaryWordEncoding.bitSize xs)) 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.RamSolverTotalExecution.Input
(@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)
xs)
Lax109476Proofs.RamExactSolverProgram.solve (Lax109476Proofs.RamSolverTotalExecution.Result xs)
(Lax109476Proofs.RamUniformSolverBounds.instructionBound (Lax759944.BinaryWordEncoding.bitSize xs)) := by sorrySource