CookPvsNP StackRepeat
DefinitionCookPvsNP_StackRepeatalgorithmspolynomial-time
Repeatedly copy a fixed word into a destination while consuming a unary counter.
Definition code
import Definitions.Def_CookPvsNP_StackMacros
set_option autoImplicit false
namespace CookPvsNP
/-- Ports are immutable source word, destination, consumed loop counter, empty scratch. -/
def repeatCopyProg {K A : Type} [DecidableEq K] (r : Fin 4 ↪ K) : StackProg K A :=
.loop (fun h => (h (r 2)).isSome)
(.seq (popProg (r 2)) (copyProg (r 0) (r 1) (r 3)))
end CookPvsNP
Source
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.