Cook–Levin machines: polynomial-time cell constraints from unary width
ProvedCookLevin.cellClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
If a width function is computable in polynomial time in unary, then the complete cellClauses formula for every fixed tape, alphabet, and state bound is computable in polynomial time, with the actual variable numbering and canonical formula encoding. The proof constructs the complete standard-input machine, prepares reusable canonical fuel, emits all nested cell constraints, and supplies an explicit polynomial time bound. Zero bounds are included.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.cellClauseEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (cellClauses ⟨k, G, Q, w x⟩)) := by sorrySource
Compose width computation, canonical copying, head resets, and the full cell emitter. Use width-output length bounds and a fourth-degree polynomial in the unary-width running-time bound, then decode canonical output.