block laws
ProvedResourceScheduling.Graph.block_lawsalgorithmspolynomial-time
Concatenated command blocks compose their semantics and preserve bounded-execution certificates.
Preamble
import Definitions.Def_ResourceScheduling_Graph_ReductionProgram import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph GraphReg GraphProgram
Formal statement
namespace ResourceScheduling.Graph
theorem block_laws (ps qs : List Code) (B : ℕ) (s : RAMState GraphReg) :
(block (ps ++ qs)).eval s = (block qs).eval ((block ps).eval s) ∧
(RAMSafe (block ps) B s → RAMSafe (block qs) B ((block ps).eval s) →
RAMSafe (block (ps ++ qs)) 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.