Execution of unboundedness-certificate system construction
ProvedLax109476Proofs.RamCertificateFamilies.unbounded_specalgorithmscomputational-complexitylinear-programming
Let be an integer linear program with constraints and variables. Let bound the absolute values of all entries, and let be the machine modulus. Put and . Assume
Given the stored source program and allocated target arrays of lengths and , the unboundedness-family command writes the exact matrix and right-hand side of the published ray-certificate system and preserves the source representation. Its actual execution satisfies
The statement includes zero-dimensional inputs. It provides the operational construction needed before deciding and recovering an unboundedness certificate.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax109476Proofs.RamCertificateFamilies.unbounded_spec : ∀ (B M m n : ℕ) (P : Lax109476.LinearProgram.Program ℤ m n),
1 ≤ M →
M < B →
m * n + 2 * m + 2 * n + 8 < B →
(m + (m + 1)) * (n + n) + (m + (m + 1)) + (n + n) + 4 < B →
(∀ (i : Fin m) (j : Fin n), (P.A i j).natAbs ≤ M) →
(∀ (i : Fin m), (P.b i).natAbs ≤ M) →
(∀ (j : Fin n), (P.c j).natAbs ≤ M) →
Lax808846Proofs.Reasoning.Spec B (Lax109476Proofs.RamCertificateFamilies.Input P (m + (m + 1)) (n + n))
Lax109476Proofs.RamCertificateFamilies.unbounded
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamCertificateSource.Data P τ ∧
Lax109476Proofs.RamEquationData.Data (Lax109476Proofs.CertificateFamilyPrograms.unbounded P) τ)
(134 * ((m + (m + 1)) * (n + n)) + 90 * (m + (m + 1)) + 74) := by sorrySource