Execution of stored rational feasibility decisions
ProvedLax109476Proofs.RamCertificateDecision.decideFeasible_specalgorithmscomputational-complexitylinear-programming
Let be an integer linear system with rows and columns. Let bound these dimensions and let bound its coefficient magnitudes. The feasibility command uses word width , a source array prefix and a disjoint target prefix. Assume the stated decision-width bound and that the source system is encoded correctly. Then the command preserves the source representation and source-data predicate, and writes a Boolean feasibility decision at the target:
Its operational running time is at most the explicit decision-cost function of . Array-prefix disjointness and all required word-range conditions are hypotheses. This result supplies the actual feasibility subroutine used when selecting optimality, infeasibility or unboundedness certificates.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax109476Proofs.RamCertificateDecision.decideFeasible_spec : ∀ (r s S w : ℕ) (F : Lax109476.LinearProgram.Program ℤ r s) (source target : String),
2 ^ (2 * S) < 2 ^ w →
r * s + r + s + 4 < 2 ^ w →
Lax109476Proofs.RamStoredFeasibility.wordWidth (Lax109476Proofs.RamCertificateDecision.sizeBound r s S) ≤ w →
(∀ (i : Fin r) (j : Fin s), (F.A i j).natAbs ≤ 2 ^ (2 * S)) →
(∀ (i : Fin r), (F.b i).natAbs ≤ 2 ^ (2 * S)) →
(∀ (j : Fin s), F.c j = 0) →
Lax109476Proofs.RamCopy.Disjoint (source ++ "system.A") (target ++ "lp.A") →
Lax109476Proofs.RamCopy.Disjoint (source ++ "system.b") (target ++ "lp.A") →
Lax109476Proofs.RamCopy.Disjoint (source ++ "system.b") (target ++ "lp.b") →
(∀ t ∈ Lax109476Proofs.RamCopy.suffixes,
source ++ ("system.A" ++ t) ∉
(Lax109476Proofs.RamCertificateDecision.decideFeasible source target).warrs) →
(∀ t ∈ Lax109476Proofs.RamCopy.suffixes,
source ++ ("system.b" ++ t) ∉
(Lax109476Proofs.RamCertificateDecision.decideFeasible source target).warrs) →
Lax808846Proofs.Reasoning.Spec (2 ^ w)
(Lax109476Proofs.RamCertificateDecision.Input F source target)
(Lax109476Proofs.RamCertificateDecision.decideFeasible source target)
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamEquationData.Data F
(Lax109476Proofs.RamCertificateDecision.prefixedView source τ) ∧
Lax808846Proofs.Imp.Cond.evalB (2 ^ w) Lax109476Proofs.RamBisectionCommit.condition τ =
Option.some
(Lax109476Proofs.RationalFeasibilityDecision.feasible
(Lax109476Proofs.IntegerEncoding.rationalProgram F)))
(Lax109476Proofs.RamCertificateDecision.instructionBound r s S) := by sorrySource