count program
ProvedResourceScheduling.Graph.count_programalgorithmspolynomial-time
The complete nested counting program computes the exact length of the ordered non-edge list and preserves the uniform numeric bound.
Preamble
import Definitions.Def_ResourceScheduling_Graph_ReductionProgram import Definitions.Def_ResourceScheduling_Graph_RAMFields import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph GraphReg GraphProgram
Formal statement
namespace ResourceScheduling.Graph
theorem count_program (B N : ℕ) (s : RAMState GraphReg) (hs : RAMBound B s)
(hn : s.val n = N) (hB : N * N + N + 1 ≤ B) :
RAMSafe countEdges B s ∧ (countEdges.eval s).val count = (wordNonEdges N s.word).length := 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.