Core polynomial-time generation of initial tableau clauses
ProvedCookLevin.initialClauseEmitter_polyTime_corecook-levininitial-clausespoly-time
For fixed parameters , emitting the encoded initial clauses is computable in polynomial time in .
Formal statement
import Definitions.Def_CookLevin_Reduction
open CookLevin
theorem CookLevin.initialClauseEmitter_polyTime_core (k G Q cw dw ct dt : Nat) :
IsPolyTimeComputable (fun x =>
encodeFormula (startClauses ⟨k, G, Q, tabWidth cw dw ct dt x⟩
(reductionInit (boolsToSymbols x) (certLen cw dw x)))) := by sorrySource