emit header
ProvedResourceScheduling.Graph.emit_headeralgorithmspolynomial-time
The emission prefix writes the two speeds, dimension, and resource count as exact unary fields while keeping numeric registers bounded.
Preamble
import Definitions.Def_ResourceScheduling_Graph_ReductionProgram import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph GraphReg GraphProgram
Formal statement
namespace ResourceScheduling.Graph
theorem emit_header (B : ℕ) (s : RAMState GraphReg) (hs : RAMBound B s) (hB : 2 ≤ B) :
let p := block [.zero num, .inc num, .inc num, .emit num,
.zero num, .inc num, .emit num, .emit n, .emit count]
RAMSafe p B s ∧ p.eval s =
{ s.set num 1 with out :=
(unary 2 ++ unary 1 ++ unary (s.val n) ++ unary (s.val count)).reverse ++ s.out } := 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.