Native processing of an exact distance-LP certificate
ProvedLax263307Proofs.NativeProjectionResult.command_specalgorithmsgraph-theorylinear-programming
Let be a rational program with rows and variables, a rational tolerance, and a certificate for its distance program. Assume the certificate and tolerance meet the stated height bound , the host bound satisfies and , and the declared storage is available.
The actual certificate-processing command returns exactly the classified projection outcome for , preserves the encoded source program, and records the correct dimension . Its execution has at most the published projection-result cost . The output includes the stored near point, separating cut, or rejection data required by that outcome. This interface converts the solver certificate into the rational query result used by the oracle.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOracleInterfaces
Formal statement
theorem Lax263307Proofs.NativeProjectionResult.command_spec : ∀ (B M m n : ℕ) (P : Lax109476.LinearProgram.Program ℚ m n)
(c : Lax109476.RationalCertificates.Certificate (m + (n + n)) (n + 1)) (ρ : ℚ),
2 * M ^ 2 + 3 < B →
3 * m + 10 * n + 20 < B →
Lax263307Proofs.NativeProjectionResult.CertificateBounded M c →
Lax263307Proofs.NativeSignedArithmetic.Bounded M ρ →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
Lax455465Proofs.RamVirtualState.Prefix (Lax109476.RationalEncoding.encodeProgram P) "lp.input" σ ∧
Lax455465Proofs.RamVirtualState.Prefix (Lax109476.RationalEncoding.encodeCertificate c) "vm.output" σ ∧
Lax263307Proofs.NativeSignedArithmetic.Stored "projection.tolerance" ρ σ ∧
3 * n < (σ.arrs "lp.word").length)
Lax263307Proofs.NativeProjectionResult.command
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax263307Proofs.NativeProjectionResult.Output (Lax263307.RationalProjection.classify P ρ c) τ ∧
Lax455465Proofs.RamVirtualState.Prefix (Lax109476.RationalEncoding.encodeProgram P) "lp.input" τ ∧
τ.vars "projection.n" = n)
(Lax263307Proofs.NativeProjectionResult.cost M n) := by sorrySource