Cook–Levin machines: polynomial-time choice-cell initialization on any tape
ProvedCookLevin.choiceCellEmitter_of_unary_boundscomplexitycook-levinloopsturing-machines
Polynomial-time unary width and choice bounds suffice to generate the certificate-choice formula at any fixed logical tape index. The construction computes both bounds, canonicalizes their outputs, initializes the counter, emits clauses and proves the standard output decoding and polynomial runtime. A zero choice bound gives blank-tape initialization.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.choiceCellEmitter_of_unary_bounds (k G Q j : Nat) (w m : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true))
(hm : IsPolyTimeComputable (fun x => List.replicate (m x) true)) :
IsPolyTimeComputable (fun x => encodeFormula ((List.range (w x + 1)).map fun p =>
(reductionInit [] (m x) 1 p).map fun s =>
Literal.Pos ((⟨k, G, Q, w x⟩ : Shape).cellVar 0 j p s))) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.