emit program
ProvedResourceScheduling.Graph.emit_programalgorithmspolynomial-time
The complete emitter produces the exact original unary Q2 encoding with header, lexicographic resource matrix, and threshold, within the uniform numeric bound.
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_program (B : ℕ) (s : RAMState GraphReg) (hs : RAMBound B s)
(hn : s.val n = 3 * s.val t) (hc : s.val count = (wordNonEdges (s.val n) s.word).length)
(hB : s.val n * s.val n + s.val n ≤ B) (hpos : 2 ≤ B) :
RAMSafe emit B s ∧ (emit.eval s).out = (emitQ2Word (s.val t) s.word).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.