Core computation in polynomial time for reduction emitter machine
DisprovedCookLevin.reductionEmitM_computesInTime_corecook-levinpoly-timereduction
The composite reduction emitter machine M computes cookLevinReduction in time bounded by polyBound (1 + cw + dw + ct + dt) 1.
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_core (Mv : Machine) (k G cw dw ct dt : Nat)
(hwf : TuringMachine k G Mv) :
∃ M, TuringMachine k G M ∧ ComputesInTime M k (polyBound (1 + cw + dw + ct + dt) 1) (cookLevinReduction Mv k G cw dw ct dt) := by sorry
Source