Actual bounded execution of the native weighted approximation command
ProvedLax263307Proofs.NativeWeightedExecution.command_specalgorithmscomputational-complexitygraph-theory
For a fixed implementation of a hereditary separator class, every member , rational weight vector and rational has an independent-set approximation for which the actual weighted command terminates within its declared instruction bound:
The execution starts from the encoded weighted input, produces the encoded membership output, and obeys the explicit workspace and word-width bounds.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax263307Proofs.NativeWeightedExecution.command_spec : ∀ {C : Lax263307.GraphClasses.GraphClass} (i : Lax263307Proofs.NativeQptasImplementation.Fixed C) {n : ℕ}
(G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj],
G ∈ C n →
∀ (weights : Fin n → ℚ) (ε : ℚ),
0 < ε →
ε < 1 →
∃ (I : Finset (Fin n)) (ext : String → ℕ),
Lax263307.WeightedIndependentSet.IsApproximation G weights ε I ∧
Lax808846Proofs.Reasoning.Spec (2 ^ Lax263307Proofs.NativeQptasWordBounds.width i weights ε)
(fun (σ : Lax808846Proofs.Imp.Env) =>
σ = Lax808846Proofs.Imp.initEnv ext (Lax263307.IndependentSetEncoding.encodeInput G weights ε))
(Lax263307Proofs.NativeWeightedExecution.command i)
(fun (x τ : Lax808846Proofs.Imp.Env) => τ.out = Lax263307.IndependentSetEncoding.encodeOutput I)
(Lax263307Proofs.NativeWeightedExecution.cost i weights ε) := by sorrySource