ram budget
ProvedResourceScheduling.Graph.ram_budgetalgorithmspolynomial-time
Uniformly bounded numeric registers and word lengths give the structural polynomial source-step bound, one additional degree per loop nesting.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMBudget open CookPvsNP ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_budget {V : Type} [DecidableEq V] (p : RAMCode V) (B : ℕ) (s : RAMState V)
(h : p.Bounded B s) : p.cost s ≤ p.weight * (B + 1)^p.degree := by sorry
end ResourceScheduling.GraphSource
New auxiliary formalization for the ResourceScheduling Q2 reduction. The target is the unchanged CookPvsNP one-tape machine model, following Cook, The P versus NP problem, Clay Mathematics Institute (2000), Appendix. This explicit finite-column stack compiler and its simulation lemmas are new contributions, not numbered claims from Cook or the scheduling source paper.