Read a bound of the primal-dual certificate system
OpenLax109476Proofs.RamPairSelector.selectBound_specalgorithmscomputational-complexitygraph-theory
Let be an integer LP with constraints and variables, whose stored coefficients meet the published bound . The joint primal-dual feasibility system has rows and columns. For each valid requested index, under the stated source-storage and host-word guards, the selector command reads its right-hand-side entry into the signed rational result registers:
This is a reusable source interface for composing the complete finite-program implementation.
Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax109476Proofs.RamPairSelector.selectBound_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamPairSelector
theorem selectBound_spec : ∀ (B M m n : Nat) (P : Lax109476.LinearProgram.Program Int m n)
(i :
Fin
(Nat.add m
(Nat.add n
((2:Nat))))),
Nat.le ((1:Nat)) M →
Nat.lt M B →
Nat.lt
(Nat.add (Nat.add m n)
((4:Nat)))
B →
(∀ (r : Fin m), Nat.le (@Lax109476.LinearProgram.Program.b Int m n P r).natAbs M) →
(∀ (s : Fin n), Nat.le (@Lax109476.LinearProgram.Program.c Int m n P s).natAbs M) →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamCertificateSource.Data m n P σ)
(@Eq Nat (σ.vars "query.row")
(@Fin.val
(Nat.add m
(Nat.add n
((2:Nat))))
i)))
Lax109476Proofs.RamPairSelector.selectBound
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamCertificateSource.Data m n P τ)
(Lax109476Proofs.RamRational.FractionOutput
(@Int.cast Rat Rat.instIntCast (@Lax109476Proofs.CertificateFamilyEntries.pairRhs m n P i)) τ))
((40:Nat)) := by sorry
end Lax109476Proofs.RamPairSelector
Source