Core polynomial-time generation of structural clause families
ProvedCookLevin.structuralClauseEmitters_polyTime_corecook-levinpoly-timestructural-clauses
For fixed parameters , each of the nine structural clause families (cell, head, state, read, link, inertia, halt, accept, blankSuffix) is computable in polynomial time in .
Formal statement
import Definitions.Def_CookLevin_Reduction
open CookLevin
theorem CookLevin.structuralClauseEmitters_polyTime_core (k G Q cw dw ct dt : Nat) :
∀ family ∈ ([cellClauses, headClauses, stateClauses, readClauses,
linkClauses, inertiaClauses, haltClauses, acceptClauses,
fun sh => blankSuffixClauses sh 1] : List (Shape → Formula)),
IsPolyTimeComputable (fun x =>
encodeFormula (family ⟨k, G, Q, tabWidth cw dw ct dt x⟩)) := by sorrySource