Read a stored integer matrix coefficient as a rational
ProvedLax109476Proofs.RamCertificateLoad.matrix_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a stored integer program with rows and columns, and let , . Suppose , the matrix coefficient has magnitude at most , and . The fixed coefficient reader preserves the source storage and returns the signed rational value
in at most instructions. The query registers initially specify .
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBlockInterfaces namespace Lax109476Proofs.RamCertificateLoad end Lax109476Proofs.RamCertificateLoad
Formal statement
theorem Lax109476Proofs.RamCertificateLoad.matrix_spec_native : ∀ (B M m n : Nat) (P : Lax109476.LinearProgram.Program Int m n) (i : Fin m) (j : Fin n),
@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)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) (@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) m n)
m)
n)
(@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
B →
@LE.le Nat instLENat (@Lax109476.LinearProgram.Program.A Int m n P i j).natAbs M →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamCertificateSource.Data m n P σ)
(And (@Eq Nat (σ.vars "query.a.row") (@Fin.val m i)) (@Eq Nat (σ.vars "query.a.col") (@Fin.val n j))))
Lax109476Proofs.RamCertificateLoad.matrix
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamCertificateSource.Data m n P τ)
(Lax109476Proofs.RamRational.FractionOutput
(@Int.cast Rat Rat.instIntCast (@Lax109476.LinearProgram.Program.A Int m n P i j)) τ))
(@OfNat.ofNat Nat (nat_lit 21) (instOfNatNat (nat_lit 21))) := by sorrySource