ram frames
ProvedResourceScheduling.Graph.ram_framesalgorithmspolynomial-time
Updating one register, input word, or output preserves the representation relation with the corresponding semantic update; stack nonemptiness recognizes positive registers.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAM open CookPvsNP ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_frames {V : Type} [DecidableEq V] (s : RAMState V)
(l : RAMWire V → List Letter) (hr : RAMRep s l) :
(∀ v w, RAMRep (s.set v w.length) (Function.update l (ramReg v) w)) ∧
(∀ w, RAMRep { s with word := w } (Function.update l ramInput w)) ∧
(∀ w, RAMRep { s with out := w } (Function.update l ramOutput w)) ∧
(∀ v, ((l (ramReg v)).head?).isSome = decide (0 < s.val v)) := 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.