Core 6-tape decision machine for CNF formula evaluation bounded by product of lengths
ProvedCookLevin.satisfiesB_machine_product_corecook-levinproduct-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_product_core :
∃ (M : Machine) (c1 : Nat),
TuringMachine 6 4 M ∧
∀ x w : List Bool,
DecidesIn M 6 (boolsToSymbols x) (boolsToSymbols w)
(c1 * (x.length + 1) * (w.length + 1))
(satisfiesB (decodeAssignment w) (decodeFormula x)) := by sorrySource