Rational feasibility execution with a Boolean output flag
ProvedLax109476Proofs.RamRationalFeasibility.decideFeasible_with_flag_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a rational linear program with constraints and variables, and let be the binary size of its encoding. Suppose is at least the published feasibility word-width bound and the complete input and workspace predicate holds. The fixed rational feasibility command terminates within instructions and produces a genuine Boolean flag satisfying
Here feasibility is the source's total exact decision predicate, and the bound and decision are uniform in all rational input data. Retaining the Boolean range is needed to use the flag in actual conditional execution.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativePhaseInterfaces namespace Lax109476Proofs.RamRationalFeasibility end Lax109476Proofs.RamRationalFeasibility
Formal statement
theorem Lax109476Proofs.RamRationalFeasibility.decideFeasible_with_flag_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) =>
And (@LE.le Nat instLENat (τ.vars "search.found") (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@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