Cook–Levin: polynomial-time transition formula emission
ProvedCookLevin.transitionClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
For a fixed verifier, a polynomial-time unary width suffices to emit the exact full transitionClauses formula. The construction starts from standard input, computes and copies width, initializes counters, iterates in original clause order and proves a quartic polynomial runtime bound.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.transitionClauseEmitter_of_unary_width (M : Machine) (k G : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (transitionClauses ⟨k, G, M.length, w x⟩ M)) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.