Actual weighted native execution with zero blow-up order
OpenLax263307Proofs.NativeQptasZero.command_specalgorithmscomputational-complexitygraph-theory
Fix the selected native implementation, a graph, arbitrary signed rational weights and positive rational accuracy. Assume the zero rounded blow-up order case and all published numeric, word-width, initialization and allocated-extent guards. The fixed weighted command returns exactly the functional weighted answer, with its complete charged instruction bound:
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.NativeQptasZero.command_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax263307Proofs.NativeQptasZero
theorem command_spec : ∀ {n : Nat} (B M : Nat),
Nat.le ((1:Nat)) M →
Nat.le n M →
∀ (cfg : Lax263307Proofs.NativeCoreMachine.Config) (C d Q e : Nat) (lp flow : List Nat → List Nat)
(G : SimpleGraph (Fin n)) [inst : @DecidableRel (Fin n) (Fin n) (@SimpleGraph.Adj (Fin n) G)]
(weights : Fin n → Rat) (ε : Rat),
@LT.lt Rat Rat.instLT (@OfNat.ofNat Rat (nat_lit 0) (@Rat.instOfNat (nat_lit 0))) ε →
(∀ (v : Fin n),
And (Nat.le (weights v).num.natAbs M) (Nat.le (weights v).den M)) →
And (Nat.le ε.num.natAbs M) (Nat.le ε.den M) →
Nat.lt
(Nat.add
(Nat.mul
((2:Nat))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
M ((4:Nat))))
((3:Nat)))
B →
Nat.lt
(Nat.add
(Nat.add
(Nat.mul n n)
(Nat.mul
((3:Nat)) n))
((3:Nat)))
B →
@Eq Nat
(∑ v : Fin n,
@Lax263307.WeightRounding.copies n (@Lax263307.PositiveWeights.positiveWeights n weights) ε v)
((0:Nat)) →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Eq (List Nat) σ.inp (@Lax263307.IndependentSetEncoding.encodeInput n G inst weights ε))
(And
(Nat.le
(Nat.add
(Nat.add
(Nat.mul n n)
(Nat.mul
((3:Nat)) n))
((3:Nat)))
(@List.length Nat (σ.arrs "input.data")))
(And (Nat.le n (@List.length Nat (σ.arrs "copy.counts")))
(@Eq Nat (@List.length Nat (σ.arrs "weighted.output")) n))))
(Lax263307Proofs.NativeQptasProgram.command cfg C d Q e)
(fun (σ τ : Lax808846Proofs.Imp.Env) =>
@Eq (List Nat) τ.out
(@HAppend.hAppend (List Nat) (List Nat) (List Nat)
(@instHAppendOfAppend (List Nat) (@List.instAppend Nat)) σ.out
(@Lax263307.IndependentSetEncoding.encodeOutput n
(@Lax263307.WeightedAlgorithm.solve n lp flow cfg.a cfg.K cfg.b G inst weights ε))))
(Nat.add
(Nat.add
(Lax263307Proofs.NativeBlowUp.cost n
((0:Nat)))
(Nat.mul
((24:Nat)) n))
((20:Nat))) := by sorry
end Lax263307Proofs.NativeQptasZero
Source