Core 6-tape decision machine for CNF formula evaluation bounded by quadratic length sum
ProvedCookLevin.satisfiesB_machine_quad_corecook-levinquadratic-timesatisfiesb
There exists a 6-tape, 4-symbol multi-tape Turing machine and constant such that decides whether an assignment satisfies a CNF formula in time bounded by .
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.satisfiesB_machine_quad_core :
∃ (M : Machine) (c0 : Nat),
TuringMachine 6 4 M ∧
∀ x w : List Bool,
DecidesIn M 6 (boolsToSymbols x) (boolsToSymbols w)
(c0 * (x.length + w.length + 1) ^ 2)
(satisfiesB (decodeAssignment w) (decodeFormula x)) := by sorrySource