A linear-time Turing machine comparing certificate and formula lengths
ProvedCookLevin.certLength_le_machineThere exists a well-formed multi-tape Turing machine over tapes with alphabet size , and a constant , such that for every formula string and candidate certificate (both given as Boolean lists), the machine halts within steps and outputs the Boolean verdict . This is the certificate-length conjunct of the SAT verifier: the verifier accepts only certificates whose length does not exceed the length of the formula, and this machine decides exactly that comparison in linear time.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin
theorem certLength_le_machine :
∃ (M : Machine) (k G : Nat) (c : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(c * (x.length + w.length + 1))
(decide (w.length ≤ x.length)) := by sorry
end CookLevin