Core decision machine for decoded CNF formula evaluation
ProvedCookLevin.decodeCnf_evaluate_machine_corecnf-evaluatorcook-levinpoly-time
There exists a multi-tape Turing machine that parses a binary CNF formula encoding and evaluates it against an assignment 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.decodeCnf_evaluate_machine_core :
∃ (M : Machine) (k G c : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(c * (x.length + 1) * (w.length + 1))
((decodeFormula x).all (fun clause =>
clause.any (fun lit => match lit with
| Literal.Neg n => !(w.getD n false)
| Literal.Pos n => w.getD n false))) := by sorrySource