Time complexity bound for cookLevinReduction
ProvedCookLevin.reductionEmitM_computesInTimecook-levinpoly-timereduction
The tableau reduction function cookLevinReduction is computable in polynomial time by a multi-tape Turing machine.
Formal statement
import Definitions.Def_CookLevin_Basic
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_CookLevin_Reduction
open CookLevin
theorem CookLevin.reductionEmitM_computesInTime (Mv : Machine) (k G cw dw ct dt : Nat)
(hwf : TuringMachine k G Mv) :
IsPolyTimeComputable (cookLevinReduction Mv k G cw dw ct dt) := by sorry
Source