ram safe laws
ProvedResourceScheduling.Graph.ram_safe_lawsalgorithmspolynomial-time
Bounded executions with bounded final states compose through skip, sequencing, and branching.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_safe_laws {V : Type} [DecidableEq V] (p q : RAMCode V) (v : V) (B : ℕ) (s : RAMState V) :
(RAMBound B s → RAMSafe (.skip : RAMCode V) B s) ∧
(RAMSafe p B s → RAMSafe q B (p.eval s) → RAMSafe (p.seq q) B s) ∧
(RAMSafe p B s → RAMSafe q B s → RAMSafe (.branch v p q) B s) := 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.