Execute the initialized bounded ellipsoid-search loop
ProvedLax109476Proofs.RamSearchLoop.searchLoop_spec_nativealgorithmscomputational-complexitygraph-theory
Let be an integer matrix with and coefficient magnitudes at most , and let the rational vector have the same height bound. Assume and the complete ellipsoid bit-width, dimension and separation arithmetic guards. Starting from the source’s full initialized invariant, the native loop runs through its bounded search and returns
Its instruction count is at most . The invariant retains the exact trajectory and first-success interpretation of the output flag and index.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBoundsInterfaces namespace Lax109476Proofs.RamSearchLoop end Lax109476Proofs.RamSearchLoop
Formal statement
theorem Lax109476Proofs.RamSearchLoop.searchLoop_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),
@LT.lt Nat instLTNat N
(@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) →
(∀ (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.RamEllipsoidBitBounds.wordWidth n (Lax109476Proofs.RamTrajectoryBounds.stateBits n N l)
N)
w →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m n)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) m n))
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@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) →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HPow.hPow Nat Nat Nat
(@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(Lax109476Proofs.RamDotProduct.cap n
(@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)))
(Lax109476Proofs.RamTrajectoryBounds.stateBits n N l)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(@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) →
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)
(fun (σ : Lax808846Proofs.Imp.Env) =>
And
(@Lax109476Proofs.RamSearchStep.State m n A b
(@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) σ)
(And (@Eq Nat (σ.vars "search.limit") N)
(@Eq Nat (σ.vars "search.found") (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))))
Lax109476Proofs.RamSearchLoop.searchLoop
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamSearchLoop.Invariant m n A b N τ)
(@Eq (Option Bool)
(Lax808846Proofs.Imp.Cond.evalB
(@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)
(Lax808846Proofs.Imp.Cond.lt (Lax808846Proofs.Imp.Expr.var "iter.k")
(Lax808846Proofs.Imp.Expr.var "search.limit"))
τ)
(@Option.some Bool Bool.false)))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) (Lax109476Proofs.RamSearchStep.cost m n N l)
(@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
N)
(@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) := by sorrySource