Cook–Levin machines: all runtime head-position exclusions
ProvedCookLevin.machine_emit_head_exclusion_blockcomplexitycook-levinloopsturing-machines
Emit every ordered off-diagonal pair of head positions below runtime n, preserving the exact encoded clause order. Both position fuels are restored, the inner literal counter returns to zero, and the outer counter reaches position n. Runtime n*(n*(A*(2*a(n)+c)+B+28)+22)+4.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_head_exclusion_block {k G : Nat} (hk : 8 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j n c : Nat) (input : Tape) (bits : List Bool)
(flag inner outer : Nat → Symbol) (saved : List Tape),
saved.length + 8 = k →
inner 0 ≠ oneSymbol → outer 0 ≠ oneSymbol →
(∀ i, i < n → inner (1 + i) = oneSymbol) →
(∀ i, i < n → outer (1 + i) = oneSymbol) →
inner (1 + n) ≠ oneSymbol → outer (1 + n) ≠ oneSymbol →
let a := fun p => literalN (.Neg (sh.headVar t j p))
let chunk := (List.range n).flatMap fun p => (List.range n).flatMap fun q => if p = q then [] else
(encodeFormula [[Literal.Neg (sh.headVar t j p), Literal.Neg (sh.headVar t j q)]]).dropLast
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: (flag, 1) :: (inner, 1) :: (outer, 1) :: saved)
(n * (n * (A * (a n + a n + c) + B + 28) + 22) + 4)
(input :: (contents (boolsToSymbols (List.replicate (a n) true)), 1 + a n) ::
(contents (boolsToSymbols (List.replicate (a 0) true)), 1 + a 0) ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
((fun i => if n = 0 then flag i else if i = 1 then oneSymbol else flag i), 1) ::
(inner, 1) :: (outer, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.