read eval
ProvedResourceScheduling.Graph.read_evalalgorithmspolynomial-time
The matrix-read macro computes row times dimension plus column, then reads exactly that ordinary input symbol.
Preamble
import Definitions.Def_ResourceScheduling_Graph_ReductionProgram open ResourceScheduling.Graph GraphReg
Formal statement
namespace ResourceScheduling.Graph
theorem read_eval (a b dst : GraphReg) (h : b ≠ index) (s : RAMState GraphReg) :
(GraphProgram.read a b dst h).eval s =
let z := s.val a * s.val n + s.val b
(s.set index z).set dst (if s.word.getD z Letter.sep = Letter.one then 1 else 0) := 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.