word non edges
ProvedResourceScheduling.Graph.word_non_edgesalgorithmspolynomial-time
Natural-index resource enumeration agrees with the original ordered graph non-edge list.
Preamble
import Definitions.Def_ResourceScheduling_Graph_WordProgram open CookPvsNP open ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem word_non_edges (n : ℕ) (bits : List Letter) (G : SimpleGraph (Fin n))
[DecidableRel G.Adj]
(h : ∀ i j : Fin n, G.Adj i j ↔ bits.getD (i.val * n + j.val) Letter.sep = Letter.one) :
wordNonEdges n bits = (nonEdgeList G).map (fun p => (p.1.val, p.2.val)) := 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.