One polynomial budget for selected native backends
ProvedLax263307Proofs.NativeSelectedBudget.exists_budget_nativealgorithmscomputational-complexitygraph-theory
Fix a native core configuration, a selected LP program, a selected separator-call program and the rounded-update coefficient. The complete native demand function, including their width, time and storage allowances, is bounded by one natural polynomial envelope. Positive constants are chosen before every resource argument:
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax263307Proofs.NativeSelectedBudget end Lax263307Proofs.NativeSelectedBudget
Formal statement
theorem Lax263307Proofs.NativeSelectedBudget.exists_budget_native : ∀ {lp flow : List Nat → List Nat} (cfg : Lax263307Proofs.NativeCoreMachine.Config)
(p : Lax263307Proofs.NativeSelectedLP.Program lp) (q : Lax263307Proofs.NativeSelectedNear.Program flow) (c : Nat),
∃ (Q : Nat) (e : Nat),
And (@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) Q)
(And (@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) e)
(∀ (R : Nat),
@LE.le Nat instLENat (@Lax263307Proofs.NativeSelectedBudget.demand lp flow cfg p q c R)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) Q
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) R
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
e)))) := by sorrySource