One polynomial budget for selected native backends
OpenLax263307Proofs.NativeSelectedBudget.exists_budgetalgorithmscomputational-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.
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.NativeSelectedBudget.exists_budget_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax263307Proofs.NativeSelectedBudget
theorem exists_budget : ∀ {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 (Nat.lt ((0:Nat)) Q)
(And (Nat.lt ((0:Nat)) e)
(∀ (R : Nat),
Nat.le (@Lax263307Proofs.NativeSelectedBudget.demand lp flow cfg p q c R)
(Nat.mul Q
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(Nat.add R
((1:Nat)))
e)))) := by sorry
end Lax263307Proofs.NativeSelectedBudget
Source