Cook–Levin machines: polynomial state-clause emission from unary width
ProvedCookLevin.stateClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
For all fixed tape, alphabet and state parameters k,G,Q, and any polynomial-time unary width function w, the complete encoded state-clause formula for shape (k,G,Q,w(x)) is polynomial-time computable. The proof constructs a standard-input Turing machine, emits the actual exactly-one-state clauses at every time including the final time, and proves the canonical verdict tape decodes to precisely that formula. No positivity assumptions on k,G,Q are imposed.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.stateClauseEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (stateClauses ⟨k, G, Q, w x⟩)) := by sorrySource
Compute unary w+1 using polynomial closure, compose all-head reset and the accepted bank emitter, and decode canonical final output. Bound the time-point count by the unary computation runtime and derive a polynomial of degree twice the source degree.