Cook–Levin machines: polynomial-time blank-suffix emission from unary width
ProvedCookLevin.blankSuffixClauseEmitter_of_unary_widthcomplexitycook-levinloopsturing-machines
Whenever the tableau width has a polynomial-time unary computation, the full blank-suffix clause formula for any fixed tableau parameters and tape index has a polynomial-time emitter. The machine computes the initial literal counter as a polynomial in the width, composes the checked standard-input clause machine, and decodes its canonical final output. All zero-valued natural parameters are included.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.blankSuffixClauseEmitter_of_unary_width (k G Q j : Nat) (w : List Bool → Nat)
(hw : IsPolyTimeComputable (fun x => List.replicate (w x) true)) :
IsPolyTimeComputable (fun x => encodeFormula (blankSuffixClauses ⟨k, G, Q, w x⟩ j)) := by sorrySource
Evaluate the initial literal counter polynomial, compose the standard-input blank-suffix machine, verify decoding, and dominate its runtime by a natural polynomial.