split ones
ProvedResourceScheduling.Graph.split_onesalgorithmspolynomial-time
The leading-ones split reconstructs every input, gives a length identity, stops at a non-one, and agrees with readUnary including missing separators.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMParse open CookPvsNP ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem split_ones (w : List Letter) :
w = List.replicate (splitOnes w).1 Letter.one ++ (splitOnes w).2 ∧
(splitOnes w).2.head? ≠ some Letter.one ∧
(splitOnes w).1 + (splitOnes w).2.length = w.length ∧
readUnary w = if (splitOnes w).2 = [] then none
else some ((splitOnes w).1, (splitOnes w).2.tail) := 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.