ram bound set
ProvedResourceScheduling.Graph.ram_bound_setalgorithmspolynomial-time
Updating a single register to a bounded natural preserves the uniform numeric state bound.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_bound_set {V : Type} [DecidableEq V] (B : ℕ) (s : RAMState V) (hs : RAMBound B s)
(v : V) (a : ℕ) (ha : a ≤ B) : RAMBound B (s.set v a) := 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.