Total rational feasibility from the stored query interface
ProvedLax109476Proofs.RamRationalFeasibility.decideFeasible_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a rational LP and its canonical binary encoding size. Assume the complete stored feasibility-query input and . The same fixed rational feasibility command halts within instructions and returns precisely the feasibility decision for the constraints of :
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamRationalFeasibility end Lax109476Proofs.RamRationalFeasibility
Formal statement
theorem Lax109476Proofs.RamRationalFeasibility.decideFeasible_spec_native : ∀ (m n : Nat) (P : Lax109476.LinearProgram.Program Rat m n) (w : Nat),
@LE.le Nat instLENat
(Lax109476Proofs.RamRationalFeasibility.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.RamFeasibilityQuery.Input m n P) Lax109476Proofs.RamRationalFeasibility.decideFeasible
(fun (x τ : Lax808846Proofs.Imp.Env) =>
@Eq Bool
(@Decidable.decide (@Eq Nat (τ.vars "search.found") (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(instDecidableEqNat (τ.vars "search.found") (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Lax109476Proofs.RationalFeasibilityDecision.feasible m n P))
(Lax109476Proofs.RamRationalFeasibility.instructionBound
(Lax759944.BinaryWordEncoding.bitSize (@Lax109476.RationalEncoding.encodeProgram m n P))) := by sorrySource