Polynomial-time decision of satVerifier by multi-tape TM
ProvedCookLevin.satVerifierMachine_decidesInTimecook-levinpoly-timeverifier
The SAT verifier satVerifier is decided 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_Verifier
open CookLevin
theorem CookLevin.satVerifierMachine_decidesInTime :
∃ M k G c d, TuringMachine k G M ∧ ∀ x w : List Bool, DecidesIn M k (boolsToSymbols x) (boolsToSymbols w) (polyBound c d (x.length + w.length)) (satVerifier x w) := by sorry
Source