Uniform backend choices and weighted algorithm correctness
OpenLax263307Proofs.NativeSolverSemantics.exists_solvers_with_partsLet be hereditary with strongly edge-sublinear separators. There are fixed polynomial word-RAM LP and flow functions and positive integer structural parameters. The LP function satisfies the exact certificate-reader contract; the flow and recursive oracle contracts hold on the independent blow-up class. For every , rational weight vector and , the same selected functions satisfy
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 Lax263307Proofs.NativeSolverSemantics.exists_solvers_with_parts_native.
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
namespace Lax263307Proofs.NativeSolverSemantics
theorem exists_solvers_with_parts : ∀ (C : Lax263307.GraphClasses.GraphClass),
Lax263307.GraphClasses.IsHereditary C →
Lax263307.EdgeSublinearSeparators.HasStronglyEdgeSublinearSeparators C →
∃ (lp : List Nat → List Nat) (flow : List Nat → List Nat) (a : Nat) (A : Nat) (K : Nat) (b : Nat),
And (Lax759944.RamPolytime.RamPolytime lp)
(And (Lax263307Proofs.NativeEncodedLP.Encoded lp)
(And (Lax759944.RamPolytime.RamPolytime flow)
(And (Nat.lt ((0:Nat)) a)
(And (Nat.lt ((0:Nat)) A)
(And (Nat.lt ((0:Nat)) K)
(And (Nat.lt ((0:Nat)) b)
(And (Lax263307.PowerBagBounds.HasPowerBagBound (Lax263307.BlowUpClasses.blowUpClass C) a A)
(And
(Lax263307Proofs.NearOracle.SeparatorCorrect (Lax263307.BlowUpClasses.blowUpClass C) flow a K
b)
(And
(Lax263307Proofs.NativeRecursiveOracle.OracleCorrect (Lax263307.BlowUpClasses.blowUpClass C)
lp flow a K b)
(∀ (n : Nat) (G : SimpleGraph (Fin n))
[inst : @DecidableRel (Fin n) (Fin n) (@SimpleGraph.Adj (Fin n) G)],
@Membership.mem (SimpleGraph (Fin n)) (Set (SimpleGraph (Fin n)))
(@Set.instMembership (SimpleGraph (Fin n))) (C n) G →
∀ (weights : Fin n → Rat) (ε : Rat),
@LT.lt Rat Rat.instLT (@OfNat.ofNat Rat (nat_lit 0) (@Rat.instOfNat (nat_lit 0))) ε →
@LT.lt Rat Rat.instLT ε
(@OfNat.ofNat Rat (nat_lit 1) (@Rat.instOfNat (nat_lit 1))) →
@Lax263307.WeightedIndependentSet.IsApproximation n G weights ε
(@Lax263307.WeightedAlgorithm.solve n lp flow a K b G inst weights ε))))))))))) := by sorry
end Lax263307Proofs.NativeSolverSemantics