Generic decoded-CNF evaluator machine
ProvedCookLevin.decodeCnf_evaluate_machinepolynomial-timesat-verifierturing-machine
There is a fixed multi-tape machine that parses a binary CNF encoding and evaluates each decoded literal against a binary assignment. It accepts precisely when every decoded clause contains a satisfied literal, within a constant multiple of the product of the two augmented input lengths. This statement isolates the operational nested-loop evaluator from the higher-level satisfiesB and assignment-decoding wrappers.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin
theorem decodeCnf_evaluate_machine :
∃ (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 sorry
end CookLevinSource