Execution of every eligible recursive MWIS node
ProvedLax263307Proofs.NativeNodeExecution.executesalgorithmscomputational-complexitylinear-programming
Fix a native core configuration, the chosen LP and flow functions, array extents, and an eligibility predicate. Let denote the precision denominator, frame stride, virtual word width and host word width. Suppose the published resource contract holds with local step bound , local time bound , and branching bound .
For every recursion fuel , every eligible node has the complete operational execution promised by the node protocol, with step and time bounds
where and . The protocol includes the returned answer, graph and stack-frame invariants and the actual return phase. This theorem converts uniform local resource data into executions of the entire bounded recursion.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax263307Proofs.NativeNodeExecution.executes : ∀ (D S v w localSteps localTime branches : ℕ) (cfg : Lax263307Proofs.NativeCoreMachine.Config)
(lp flow : List ℕ → List ℕ) (extent : String → ℕ) (eligible : Lax263307Proofs.NativeNodeProtocol.Eligible)
(resources :
Lax263307Proofs.NativeNodeExecution.Resources D S v w localSteps localTime branches cfg lp flow extent eligible)
(fuel : ℕ),
Lax263307Proofs.NativeNodeProtocol.Executes (2 ^ w) D fuel S v
(Lax263307Proofs.NativeRecursionBudget.work localSteps branches fuel)
(Lax263307Proofs.NativeRecursionBudget.work localTime branches fuel) cfg lp flow extent eligible := by sorrySource