Cook–Levin machines: polynomial-time certificate-cell initialization
ProvedCookLevin.certificateCellEmitter_of_unary_boundscomplexitycook-levinloopsturing-machines
Polynomial-time unary width and certificate bounds suffice to generate the exact certificate-cell initialization formula. The standard-input machine computes both bounds independently, copies each output to a canonical tape, resets heads and emits the formula. The proof includes output decoding and an explicit polynomial runtime bound of exponent twice the sum of the two source exponents. This is the certificate-cell component of initialization; it does not claim the full reduction.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.certificateCellEmitter_of_unary_bounds (k G Q : 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 1 p s))) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.