Execution of exact feasibility for a stored rational program
ProvedLax109476Proofs.RamStoredFeasibility.decideFeasible_condition_specalgorithmscomputational-complexitylinear-programming
Let be a rational linear program with constraints and variables, and write for the binary length of its published encoding. Let be at least the prescribed stored-feasibility word-width function at . Starting from the stored-program input and allocated workspace, the deterministic feasibility command returns a condition with exactly the mathematical feasibility value:
The actual execution is bounded by the published instruction-bound function at . The feasibility predicate concerns the constraints of , without any assumption on its objective coefficients. This is the reusable operational interface used by the certificate-system decision routine.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax109476Proofs.RamStoredFeasibility.decideFeasible_condition_spec : ∀ (m n : ℕ) (P : Lax109476.LinearProgram.Program ℚ m n) (w : ℕ),
Lax109476Proofs.RamStoredFeasibility.wordWidth
(Lax759944.BinaryWordEncoding.bitSize (Lax109476.RationalEncoding.encodeProgram P)) ≤
w →
Lax808846Proofs.Reasoning.Spec (2 ^ w) (Lax109476Proofs.RamStoredFeasibility.Input P)
Lax109476Proofs.RamStoredFeasibility.decideFeasible
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax808846Proofs.Imp.Cond.evalB (2 ^ w)
(Lax808846Proofs.Imp.Cond.eq (Lax808846Proofs.Imp.Expr.var "search.found") (Lax808846Proofs.Imp.Expr.lit 1))
τ =
Option.some (Lax109476Proofs.RationalFeasibilityDecision.feasible P))
(Lax109476Proofs.RamStoredFeasibility.instructionBound
(Lax759944.BinaryWordEncoding.bitSize (Lax109476.RationalEncoding.encodeProgram P))) := by sorrySource