Cook–Levin machines: head-exclusion row with inner-counter reset
ProvedCookLevin.machine_emit_head_pair_row_stepcomplexitycook-levinloopsturing-machines
Emit one full ordered head-exclusion row, reset the inner literal counter to position zero using reusable fuel, then advance the outer literal counter. Both fuel traversals restore their heads. Runtime n*(A*(a(p)+a(n)+c)+B+28)+16.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_head_pair_row_step {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (t j p n c : Nat) (input : Tape) (bits : List Bool)
(flag fuel : Nat → Symbol) (saved : List Tape),
saved.length + 7 = k →
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let a := fun p => literalN (.Neg (sh.headVar t j p))
let chunk := (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 p) true)), 1 + a p) ::
(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) :: (fuel, 1) :: saved)
(n * (A * (a p + a n + c) + B + 28) + 16)
(input :: (contents (boolsToSymbols (List.replicate (a (p + 1)) true)), 1 + a (p + 1)) ::
(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 boolSym (decide (p = n - 1)) else flag i), 1) :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.