Selecting a recovery query right-hand-side entry
ProvedLax109476Proofs.RamRecoveryBoundSelector.selectBound_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a rational linear program, a rational prefix vector, and a rational threshold. Under the stated height and word-range bounds, the fixed right-hand-side selector returns
for each query row , from the stored constraint bounds, prefix values and threshold. It uses at most eighty bounded operational steps.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeNextInterfaces namespace Lax109476Proofs.RamRecoveryBoundSelector end Lax109476Proofs.RamRecoveryBoundSelector
Formal statement
theorem Lax109476Proofs.RamRecoveryBoundSelector.selectBound_spec_native : ∀ (B M m n k : Nat) (P : Lax109476.LinearProgram.Program Rat m n) (x : Fin n → Rat),
@LT.lt Nat instLTNat k n →
∀ (t : Rat)
(i :
Fin
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) n n))
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))),
@LE.le Nat instLENat (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) M →
@LT.lt Nat instLTNat M B →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) n n))
(@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
B →
(∀ (i : Fin m),
Lax109476Proofs.RationalArithmeticBounds.Height (@Lax109476.LinearProgram.Program.b Rat m n P i) M) →
(∀ (j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (x j) M) →
Lax109476Proofs.RationalArithmeticBounds.Height t M →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And
(Lax109476Proofs.RamRationalArrays.Represents "point.b"
(@List.ofFn Rat m (@Lax109476.LinearProgram.Program.b Rat m n P)) σ)
(And (Lax109476Proofs.RamRationalArrays.Represents "point.x" (@List.ofFn Rat n x) σ)
(And (Lax109476Proofs.RamRationalScalars.Value "bisect.mid" t σ)
(And (@Eq Nat (σ.vars "point.m") m)
(And (@Eq Nat (σ.vars "point.n") n)
(And (@Eq Nat (σ.vars "point.k") k)
(@Eq Nat (σ.vars "query.row")
(@Fin.val
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) n n))
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
i))))))))
Lax109476Proofs.RamRecoveryBoundSelector.selectBound
(fun (x_1 τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRational.FractionOutput
(@Lax109476Proofs.RecoveryQueryEntries.bound m n P x k t i) τ)
(@OfNat.ofNat Nat (nat_lit 80) (instOfNatNat (nat_lit 80))) := by sorrySource