stack repeat copy
ProvedCookPvsNP.stack_repeat_copyalgorithmspolynomial-time
Repeated copying prepends the replicated source word, consumes the counter, and has the stated bilinear source-step count.
Preamble
import Definitions.Def_CookPvsNP_StackRepeat open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_repeat_copy {K A : Type} [DecidableEq K] (r : Fin 4 ↪ K)
(s : K → List A) (he : s (r 3) = []) :
(repeatCopyProg r).Exec s
(Function.update (Function.update s (r 2) []) (r 1)
((List.replicate (s (r 2)).length (s (r 0))).flatten ++ s (r 1)))
((6 * (s (r 0)).length + 7) * (s (r 2)).length + 1) := by sorry
end CookPvsNPSource
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.