Core polynomial-time computation of machine transition clauses
ProvedCookLevin.transitionClauseEmitter_polyTime_corecook-levinpoly-timetransition-clauses
For a fixed well-formed multi-tape machine with parameters , emitting the encoded transition clauses is computable in polynomial time in .
Formal statement
import Definitions.Def_CookLevin_Reduction
open CookLevin
theorem CookLevin.transitionClauseEmitter_polyTime_core (Mv : Machine) (k G cw dw ct dt : Nat)
(hwf : TuringMachine k G Mv) :
IsPolyTimeComputable (fun x =>
encodeFormula (transitionClauses
⟨k, G, Mv.length, tabWidth cw dw ct dt x⟩ Mv)) := by sorrySource