Cook–Levin machines: polynomial-time initial state and head clauses
ProvedCookLevin.initialHeaderEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Polynomial-time unary tableau width suffices to emit the initial state clause and the initial head-position clause on every tape. Head literal indices are affine polynomials in width. Unary polynomial computation, constant bit strings and formula concatenation give the exact output encoding.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.initialHeaderEmitter_of_unary_width (k G Q : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula
([[Literal.Pos ((⟨k, G, Q, w x⟩ : Shape).stateVar 0 0)]] ++
(List.range k).flatMap fun j =>
[[Literal.Pos ((⟨k, G, Q, w x⟩ : Shape).headVar 0 j 0)]])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.