Cook–Levin machines: polynomial-time initialization of all blank work tapes
ProvedCookLevin.blankWorkTapeEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Polynomial-time unary tableau width suffices to emit all blank work-tape initialization clauses, in tape and position order, including machines with fewer than three tapes. The proof specializes the general choice-cell emitter to zero choice bound and uses polynomial-time formula concatenation.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.blankWorkTapeEmitter_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 (k - 2)).flatMap fun j =>
(List.range (w x + 1)).map fun p =>
[Literal.Pos ((⟨k, G, Q, w x⟩ : Shape).cellVar 0 (j + 2) p (contents [] p))])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.