Core decision lemma for satVerifier multi-tape Turing machine
DisprovedCookLevin.satVerifierMachine_decides_corecook-levindecides-inverifier
There exists a 6-tape multi-tape machine M that decides satVerifier(x, w) in time bounded by polyBound 1 2 (x.length + w.length).
Formal statement
import Definitions.Def_CookLevin_Basic
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_CookLevin_Verifier
open CookLevin
theorem CookLevin.satVerifierMachine_decides_core :
∃ M, TuringMachine 6 4 M ∧ ∀ x w : List Bool, DecidesIn M 6 (boolsToSymbols x) (boolsToSymbols w) (polyBound 1 2 (x.length + w.length)) (satVerifier x w) := by sorry
Source