Cook–Levin machines: polynomial-time input-cell initialization
ProvedCookLevin.inputCellEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Any polynomial-time unary width suffices to compute the complete input-tape cell initialization formula, with the actual input symbols, start marker and blank suffix. The implementing machine uses standard input and canonical output decoding. Its explicit runtime polynomial has exponent twice the unary width computation exponent and includes head resets, initialization and final markers. This is the input-cell component of startClauses, not the entire initialization family.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.inputCellEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula ((List.range (w x + 1)).map fun p =>
[Literal.Pos ((⟨k, G, Q, w x⟩ : Shape).cellVar 0 0 p (contents (boolsToSymbols x) p))])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.