Product-time CNF evaluator machine
OpenCookLevin.satisfiesB_product_evaluator_machinepolynomial-timesat-verifierturing-machine
Retired because it duplicated CookLevin.satisfiesB_machine_product rather than decomposing the evaluator construction into a genuinely smaller obligation.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin
theorem satisfiesB_product_evaluator_machine :
∃ (M : Machine) (k G : Nat) (c1 : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(c1 * (x.length + 1) * (w.length + 1))
(satisfiesB (decodeAssignment w) (decodeFormula x)) := by sorry
end CookLevinSource