Uniform bounded execution of exact ellipsoid search
ProvedLax109476Proofs.RamSearchBounds.search_bounded_spec_nativealgorithmscomputational-complexitygraph-theory
Let be an integer matrix with , let be rational, and let be a search budget. Suppose matrix magnitudes and right-hand-side heights are bounded by , and the host width meets the explicit search bound. From the complete stored rows, right-hand side and ellipsoid workspace, the fixed search command runs within instructions and returns the exact first successful trajectory index:
Success means the rational trajectory point has no violated row. The full search invariant is retained, without assuming the existence of a feasible point.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBlockInterfaces namespace Lax109476Proofs.RamSearchBounds end Lax109476Proofs.RamSearchBounds
Formal statement
theorem Lax109476Proofs.RamSearchBounds.search_bounded_spec_native : ∀ {m n : Nat} (A : Matrix (Fin m) (Fin n) Int) (b : Fin m → Rat),
@LE.le Nat instLENat (@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) n →
∀ (N l w : Nat),
(∀ (i : Fin m) (j : Fin n),
@LE.le Nat instLENat (A i j).natAbs
(@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))) l)) →
(∀ (i : Fin m),
Lax109476Proofs.RationalArithmeticBounds.Height (b i)
(@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))) l)) →
@LE.le Nat instLENat (Lax109476Proofs.RamSearchBounds.wordWidth m n N l) 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.RamSearchBounds.Input m n A b N) Lax109476Proofs.RamSearchLoop.search
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamSearchLoop.Invariant m n A b N τ)
(@Eq (Option Nat)
(Lax109476Proofs.EllipsoidSearch.findFirst
(fun (j : Nat) =>
@Decidable.decide
(@Eq (Option (Fin m))
(@Lax109476Proofs.RationalSeparation.firstViolation m n A b
(@Prod.snd (Matrix (Fin n) (Fin n) Rat) (Fin n → Rat)
(@Lax109476Proofs.EllipsoidSearch.trajectory m n A b j)))
(@Option.none (Fin m)))
(@Option.decidableEqNone (Fin m)
(@Lax109476Proofs.RationalSeparation.firstViolation m n A b
(@Prod.snd (Matrix (Fin n) (Fin n) Rat) (Fin n → Rat)
(@Lax109476Proofs.EllipsoidSearch.trajectory m n A b j)))))
(@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) N)
(@ite (Option Nat)
(@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))))
(@Option.some Nat (τ.vars "iter.k")) (@Option.none Nat))))
(Lax109476Proofs.RamSearchBounds.instructionBound m n N l) := by sorrySource