word program validation
ProvedResourceScheduling.Graph.word_program_validationalgorithmspolynomial-time
The Boolean natural-index validator recognizes exactly the decoded adjacency-matrix conditions.
Preamble
import Definitions.Def_ResourceScheduling_Graph_WordProgram open CookPvsNP open ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem word_program_validation (n : ℕ) (bits : List Letter) :
checkGraphBody n bits = true ↔ ValidGraphBody n bits := 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.