Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CookLevin Reduction and cookLevinReduction

Definition
CookLevin_Reduction

by Rizwan G Mir · Sep 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

cook-levinreductiontableau-reduction

The Cook-Levin reduction function cookLevinReduction, reductionInit, cookLevinReduction_correct, and ReductionIsPolyTime.

Definition code
import Definitions.Def_CookLevin_Tableau
set_option autoImplicit true
/-
  CookLevinLean/Reduction.lean

  The Cook-Levin reduction.

  Given a verifier machine `Mv` and its parameters, `cookLevinReduction`
  produces, for each input `x`, the CNF tableau saying

      "there is a certificate `w` of length `polyBound cw dw |x|` such that
       `Mv` accepts `(x, w)` within `tabWidth` steps".

  The definition mentions only `Mv`, its parameters and `x`.  In particular it
  never mentions the language being reduced, and it never runs `Mv`: the
  previous version of this file defined the reduction as
  `fun x => if InLang x L' then encodeFormula [] else encodeFormula [[]]`,
  which decides `L'` in order to reduce it.
-/


namespace CookLevin

/-! ## Configurations are determined by their tapes -/

theorem config_ext {cfg1 cfg2 : Config} (hst : cfg1.1 = cfg2.1)
    (hlen : cfg1.2.length = cfg2.2.length)
    (h : ∀ j, j < cfg1.2.length → tapeAt cfg1 j = tapeAt cfg2 j) : cfg1 = cfg2 := by
  obtain ⟨q1, tps1⟩ := cfg1
  obtain ⟨q2, tps2⟩ := cfg2
  simp only at hst hlen h
  subst hst
  refine congrArg _ (List.ext_getElem hlen ?_)
  intro i hi1 hi2
  have e1 : tapeAt ((q1, tps1) : Config) i = tps1[i] := getD_of_lt _ _ hi1
  have e2 : tapeAt ((q1, tps2) : Config) i = tps2[i] := getD_of_lt _ _ hi2
  rw [← e1, ← e2]
  exact h i hi1

/-! ## The tapes of a two-input start configuration -/

/-- The contents of tape `j` in `startConfig2 k xs ws`. -/
def startTape (xs ws : List Symbol) (j : TapeIdx) : Nat → Symbol :=
  if j = 0 then contents xs else if j = 1 then contents ws else contents []

theorem tapeAt_startConfig2 {k : Nat} (hk : 2 ≤ k) (xs ws : List Symbol) {j : Nat}
    (hj : j < k) : tapeAt (startConfig2 k xs ws) j = (startTape xs ws j, 0) := by
  match j with
  | 0 => rfl
  | 1 => rfl
  | (n + 2) =>
    unfold tapeAt startConfig2 startTape
    rw [getD_of_lt _ _ (by simp; omega)]
    simp

theorem tapeFun_startConfig2 {k : Nat} (hk : 2 ≤ k) (xs ws : List Symbol) {j : Nat}
    (hj : j < k) (p : Nat) : tapeFun (startConfig2 k xs ws) j p = startTape xs ws j p := by
  rw [tapeFun_eq, tapeAt_startConfig2 hk xs ws hj]

theorem headPos_startConfig2 {k : Nat} (hk : 2 ≤ k) (xs ws : List Symbol) {j : Nat}
    (hj : j < k) : headPos (startConfig2 k xs ws) j = 0 := by
  rw [headPos_eq, tapeAt_startConfig2 hk xs ws hj]

/-! ## The start condition of the reduction

Tape `0` is pinned to the instance, tape `1` is left free on cells `1 … m`
(restricted to the two bit symbols), and every other cell is pinned. -/

/-- The allowed symbols of cell `p` of tape `j` at time `0`. -/
def reductionInit (xs : List Symbol) (m : Nat) : TapeIdx → Nat → List Symbol := fun j p =>
  if j = 0 then [contents xs p]
  else if j = 1 then
    (if p = 0 then [startSymbol]
     else if p ≤ m then [zeroSymbol, oneSymbol, blankSymbol]
     else [blankSymbol])
  else [contents [] p]

theorem reductionInit_lt {xs : List Symbol} {m G : Nat} (hG : 4 ≤ G)
    (hxs : ∀ s ∈ xs, s < G) (j p : Nat) : ∀ s ∈ reductionInit xs m j p, s < G := by
  have hcontents : ∀ (ys : List Symbol), (∀ s ∈ ys, s < G) → ∀ q, contents ys q < G := by
    intro ys hys q
    unfold contents
    split
    · show 1 < G; omega
    · split
      · rename_i h1 h2
        rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (by omega)]
        exact hys _ (List.getElem_mem _)
      · show 0 < G; omega
  intro s hs
  unfold reductionInit at hs
  split at hs
  · simp only [List.mem_singleton] at hs
    exact hs ▸ hcontents xs hxs p
  · split at hs
    · split at hs
      · simp only [List.mem_singleton] at hs
        exact hs ▸ (by show 1 < G; omega)
      · split at hs
        · simp only [List.mem_cons, List.not_mem_nil, or_false] at hs
          rcases hs with rfl | rfl | rfl
          · show 2 < G; omega
          · show 3 < G; omega
          · show 0 < G; omega
        · simp only [List.mem_singleton] at hs
          exact hs ▸ (by show 0 < G; omega)
    · simp only [List.mem_singleton] at hs
      exact hs ▸ hcontents [] (by simp) p

/-! ## Certificate tapes -/

/-- The bits a configuration holds on cells `1 … m` of its certificate tape. -/
def witnessOf (cfg : Config) (m : Nat) : List Bool :=
  (List.range m).map fun i => decide (tapeFun cfg 1 (i + 1) = oneSymbol)

@[simp] theorem length_witnessOf (cfg : Config) (m : Nat) : (witnessOf cfg m).length = m := by
  simp [witnessOf]

theorem boolSym_inj {b b' : Bool} (h : boolSym b = boolSym b') : b = b' := by
  cases b <;> cases b' <;> first | rfl | (exfalso; exact absurd h (by decide))

theorem boolsToSymbols_lt_four' {w : List Bool} : ∀ s ∈ boolsToSymbols w, s = 2 ∨ s = 3 := by
  intro s hs
  simp only [boolsToSymbols, List.mem_map] at hs
  obtain ⟨b, _, rfl⟩ := hs
  cases b
  · exact Or.inl rfl
  · exact Or.inr rfl

/-- A certificate string of *any* length up to `m`, laid out on the tape,
satisfies the start condition. -/
theorem startTape_mem_reductionInit {xs : List Symbol} {w : List Bool} {m : Nat}
    (hw : w.length ≤ m) (j p : Nat) :
    startTape xs (boolsToSymbols w) j p ∈ reductionInit xs m j p := by
  have hlen : (boolsToSymbols w).length ≤ m := by simp [hw]
  match j with
  | 0 => exact List.mem_cons_self
  | 1 =>
    show contents (boolsToSymbols w) p ∈
      (if p = 0 then [startSymbol]
       else if p ≤ m then [zeroSymbol, oneSymbol, blankSymbol] else [blankSymbol])
    by_cases hp0 : p = 0
    · rw [if_pos hp0, hp0, contents_zero]
      exact List.mem_cons_self
    · rw [if_neg hp0]
      by_cases hpm : p ≤ m
      · rw [if_pos hpm]
        by_cases hpw : p ≤ (boolsToSymbols w).length
        · rw [contents_of_lt _ (by omega) hpw]
          have hmem : (boolsToSymbols w)[p - 1]! ∈ boolsToSymbols w := by
            rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (by omega)]
            exact List.getElem_mem _
          rcases boolsToSymbols_lt_four' _ hmem with h | h
          · rw [h]; exact List.mem_cons_self
          · rw [h]; exact List.mem_cons_of_mem _ List.mem_cons_self
        · rw [contents_of_gt _ (by omega)]
          exact List.mem_cons_of_mem _ (List.mem_cons_of_mem _ List.mem_cons_self)
      · rw [if_neg hpm, contents_of_gt _ (by omega)]
        exact List.mem_cons_self
  | (n + 2) => exact List.mem_cons_self

/-- A bit string laid out on a tape has the blank-suffix property: the bits
occupy an initial segment, and everything after them is blank. -/
theorem blankSuffix_startConfig2 {k G Q T : Nat} (hk : 2 ≤ k) (xs : List Symbol)
    (w : List Bool) :
    BlankSuffix ⟨k, G, Q, T⟩ (startConfig2 k xs (boolsToSymbols w)) 1 := by
  intro p _ hb
  have h1k : (1 : Nat) < k := by omega
  rw [tapeFun_startConfig2 hk xs _ h1k] at hb
  rw [tapeFun_startConfig2 hk xs _ h1k]
  have hb' : contents (boolsToSymbols w) p = blankSymbol := hb
  show contents (boolsToSymbols w) (p + 1) = blankSymbol
  refine contents_of_gt _ ?_
  by_cases hgt : (boolsToSymbols w).length < p
  · omega
  · exfalso
    by_cases hp0 : p = 0
    · rw [hp0, contents_zero] at hb'
      exact absurd hb' (by decide)
    · rw [contents_of_lt _ (by omega) (by omega)] at hb'
      have hmem : (boolsToSymbols w)[p - 1]! ∈ boolsToSymbols w := by
        rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (by omega)]
        exact List.getElem_mem _
      rcases boolsToSymbols_lt_four' _ hmem with h | h <;> rw [h] at hb' <;>
        exact absurd hb' (by decide)

/-! ## The start configurations allowed by `reductionInit`

They are exactly the configurations `startConfig2 k xs (boolsToSymbols w)` with
`|w| = m`.  This is what turns the tableau's "some allowed start configuration
accepts" into "some certificate is accepted". -/

theorem contents_lt {G : Nat} (hG : 4 ≤ G) {ys : List Symbol} (hys : ∀ s ∈ ys, s < G)
    (q : Nat) : contents ys q < G := by
  unfold contents
  split
  · show 1 < G; omega
  · split
    · rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (by omega)]
      exact hys _ (List.getElem_mem _)
    · show 0 < G; omega

theorem startTape_of_gt {xs ws : List Symbol} {T p : Nat} (j : TapeIdx)
    (hx : xs.length ≤ T) (hws : ws.length ≤ T) (hp : T < p) :
    startTape xs ws j p = blankSymbol := by
  unfold startTape
  split
  · exact contents_of_gt _ (by omega)
  · split
    · exact contents_of_gt _ (by omega)
    · exact contents_of_gt _ (by simp; omega)

theorem startOK_startConfig2 {k G Q T m : Nat} {xs : List Symbol} {w : List Bool}
    (hk : 2 ≤ k) (hG : 4 ≤ G) (hxs : ∀ s ∈ xs, s < G) (hw : w.length ≤ m)
    (hxT : xs.length ≤ T) (hmT : m ≤ T) :
    StartOK ⟨k, G, Q, T⟩ (reductionInit xs m) (startConfig2 k xs (boolsToSymbols w)) := by
  have hlen : (boolsToSymbols w).length ≤ m := by simp [hw]
  refine ⟨startConfig2_length hk xs _, rfl, fun j hj => headPos_startConfig2 hk xs _ hj,
    ?_, ?_, ?_⟩
  · intro j hj p _
    rw [tapeFun_startConfig2 hk xs _ hj]
    exact startTape_mem_reductionInit hw j p
  · intro j hj p hp
    rw [tapeFun_startConfig2 hk xs _ hj]
    exact startTape_of_gt j hxT (by omega) hp
  · intro j hj p
    rw [tapeFun_startConfig2 hk xs _ hj]
    unfold startTape
    split
    · exact contents_lt hG hxs p
    · split
      · refine contents_lt hG ?_ p
        intro s hs
        rcases boolsToSymbols_lt_four' _ hs with h | h <;>
          (rw [h]; exact Nat.lt_of_lt_of_le (by omega) hG)
      · exact contents_lt hG (by simp) p

/-! ## Reading the certificate off a start configuration

The certificate region of tape `1` may hold blanks as well as bits, so the
certificate is the *initial run* of non-blank cells.  `BlankSuffix` guarantees
that this run really is initial, i.e. that there are no blanks in the middle. -/

/-- The length of the certificate on cells `1 … m` of tape `1`: the largest
index `≤ m` whose cell is non-blank. -/
def certRun (cfg : Config) : Nat → Nat
  | 0 => 0
  | n + 1 => if tapeFun cfg 1 (n + 1) = blankSymbol then certRun cfg n else n + 1

theorem certRun_succ (cfg : Config) (n : Nat) :
    certRun cfg (n + 1) =
      if tapeFun cfg 1 (n + 1) = blankSymbol then certRun cfg n else n + 1 := rfl

theorem certRun_le (cfg : Config) (m : Nat) : certRun cfg m ≤ m := by
  induction m with
  | zero => exact Nat.le_refl 0
  | succ n ih =>
    rw [certRun_succ]
    split
    · omega
    · exact Nat.le_refl _

theorem certRun_nonblank (cfg : Config) (m : Nat) (h : 0 < certRun cfg m) :
    tapeFun cfg 1 (certRun cfg m) ≠ blankSymbol := by
  induction m with
  | zero => exact absurd h (Nat.lt_irrefl 0)
  | succ n ih =>
    rw [certRun_succ] at h ⊢
    by_cases hb : tapeFun cfg 1 (n + 1) = blankSymbol
    · rw [if_pos hb] at h ⊢
      exact ih h
    · rw [if_neg hb] at h ⊢
      exact hb

theorem certRun_blank_of_gt (cfg : Config) (m : Nat) {p : Nat}
    (hlt : certRun cfg m < p) (hpm : p ≤ m) : tapeFun cfg 1 p = blankSymbol := by
  induction m with
  | zero => omega
  | succ n ih =>
    rw [certRun_succ] at hlt
    by_cases hb : tapeFun cfg 1 (n + 1) = blankSymbol
    · rw [if_pos hb] at hlt
      by_cases hpn : p ≤ n
      · exact ih hlt hpn
      · exact (show p = n + 1 by omega) ▸ hb
    · rw [if_neg hb] at hlt
      omega

theorem certRun_nonblank_of_le {k G Q T : Nat} {cfg : Config} {m : Nat}
    (hbs : BlankSuffix ⟨k, G, Q, T⟩ cfg 1) (hmT : m ≤ T) {p : Nat}
    (hp1 : 1 ≤ p) (hple : p ≤ certRun cfg m) : tapeFun cfg 1 p ≠ blankSymbol := by
  intro hblank
  have hcm : certRun cfg m ≤ m := certRun_le cfg m
  exact certRun_nonblank cfg m (by omega)
    (BlankSuffix.mono hbs hple (show certRun cfg m ≤ T by omega) hblank)

/-- The certificate written on tape `1`. -/
def certOf (cfg : Config) (m : Nat) : List Bool :=
  ((List.range m).map fun i => decide (tapeFun cfg 1 (i + 1) = oneSymbol)).take (certRun cfg m)

theorem length_certOf (cfg : Config) (m : Nat) : (certOf cfg m).length = certRun cfg m := by
  unfold certOf
  rw [List.length_take, List.length_map, List.length_range]
  exact Nat.min_eq_left (certRun_le cfg m)

theorem length_certOf_le (cfg : Config) (m : Nat) : (certOf cfg m).length ≤ m := by
  rw [length_certOf]
  exact certRun_le cfg m

theorem getElem!_boolsToSymbols_certOf {cfg : Config} {m i : Nat} (hi : i < certRun cfg m) :
    (boolsToSymbols (certOf cfg m))[i]! =
      boolSym (decide (tapeFun cfg 1 (i + 1) = oneSymbol)) := by
  have hlen : (certOf cfg m).length = certRun cfg m := length_certOf cfg m
  have hbit : (certOf cfg m)[i]'(by omega) = decide (tapeFun cfg 1 (i + 1) = oneSymbol) := by
    unfold certOf
    rw [List.getElem_take]
    simp
  rw [List.getElem!_eq_getElem?_getD]
  unfold boolsToSymbols
  rw [List.getElem?_map, List.getElem?_eq_getElem (show i < (certOf cfg m).length by omega), hbit]
  rfl

/-- **The certificate really is what the tape says.** -/
theorem contents_certOf {k G Q T m : Nat} {xs : List Symbol} {cfg : Config}
    (hk : 2 ≤ k) (hmT : m ≤ T)
    (h : StartOK ⟨k, G, Q, T⟩ (reductionInit xs m) cfg)
    (hbs : BlankSuffix ⟨k, G, Q, T⟩ cfg 1) (p : Nat) :
    contents (boolsToSymbols (certOf cfg m)) p = tapeFun cfg 1 p := by
  have h1k : (1 : Nat) < k := by omega
  have hLm : certRun cfg m ≤ m := certRun_le cfg m
  have hwslen : (boolsToSymbols (certOf cfg m)).length = certRun cfg m := by
    simp [length_certOf]
  by_cases hp0 : p = 0
  · subst hp0
    rw [contents_zero]
    have hc : tapeFun cfg 1 0 ∈ [startSymbol] := h.cells 1 h1k 0 (by omega)
    exact (by simpa using hc : tapeFun cfg 1 0 = startSymbol).symm
  · by_cases hpL : p ≤ certRun cfg m
    · rw [contents_of_lt _ (by omega) (by omega),
        getElem!_boolsToSymbols_certOf (show p - 1 < certRun cfg m by omega),
        show p - 1 + 1 = p by omega]
      have hmem : tapeFun cfg 1 p ∈
          (if p = 0 then [startSymbol]
           else if p ≤ m then [zeroSymbol, oneSymbol, blankSymbol] else [blankSymbol]) :=
        h.cells 1 h1k p (show p ≤ T by omega)
      rw [if_neg hp0, if_pos (show p ≤ m by omega)] at hmem
      have hnb : tapeFun cfg 1 p ≠ blankSymbol :=
        certRun_nonblank_of_le hbs hmT (by omega) hpL
      simp only [List.mem_cons, List.not_mem_nil, or_false] at hmem
      rcases hmem with h2 | h3 | hb
      · rw [h2]; rfl
      · rw [h3]; rfl
      · exact absurd hb hnb
    · by_cases hpm : p ≤ m
      · rw [contents_of_gt _ (by omega)]
        exact (certRun_blank_of_gt cfg m (by omega) hpm).symm
      · by_cases hpT : p ≤ T
        · rw [contents_of_gt _ (by omega)]
          have hmem : tapeFun cfg 1 p ∈
              (if p = 0 then [startSymbol]
               else if p ≤ m then [zeroSymbol, oneSymbol, blankSymbol] else [blankSymbol]) :=
            h.cells 1 h1k p hpT
          rw [if_neg hp0, if_neg hpm] at hmem
          exact (by simpa using hmem : tapeFun cfg 1 p = blankSymbol).symm
        · rw [contents_of_gt _ (by omega)]
          exact (h.blank 1 h1k p (show T < p by omega)).symm

theorem eq_startConfig2_of_startOK {k G Q T m : Nat} {xs : List Symbol} {cfg : Config}
    (hk : 2 ≤ k) (hxT : xs.length ≤ T) (hmT : m ≤ T)
    (h : StartOK ⟨k, G, Q, T⟩ (reductionInit xs m) cfg)
    (hbs : BlankSuffix ⟨k, G, Q, T⟩ cfg 1) :
    cfg = startConfig2 k xs (boolsToSymbols (certOf cfg m)) := by
  refine config_ext (by rw [h.st]; rfl) (by rw [h.len, startConfig2_length hk]) ?_
  intro j hj
  rw [h.len] at hj
  rw [tapeAt_startConfig2 hk xs _ hj]
  refine Prod.ext (funext fun p => ?_) (by rw [← headPos_eq, h.hd j hj])
  show tapeFun cfg j p = startTape xs (boolsToSymbols (certOf cfg m)) j p
  match j with
  | 0 =>
    show tapeFun cfg 0 p = contents xs p
    by_cases hpT : p ≤ T
    · have hc : tapeFun cfg 0 p ∈ [contents xs p] := h.cells 0 (by omega) p hpT
      simpa using hc
    · rw [h.blank 0 (by omega) p (show T < p by omega), contents_of_gt _ (by omega)]
  | 1 =>
    show tapeFun cfg 1 p = contents (boolsToSymbols (certOf cfg m)) p
    exact (contents_certOf hk hmT h hbs p).symm
  | (n + 2) =>
    show tapeFun cfg (n + 2) p = contents [] p
    by_cases hpT : p ≤ T
    · have hc : tapeFun cfg (n + 2) p ∈ [contents [] p] := h.cells (n + 2) hj p hpT
      simpa using hc
    · rw [h.blank (n + 2) hj p (show T < p by omega), contents_of_gt _ (by simp; omega)]

/-! ## Extending a halting computation -/

theorem decidesIn_of_le {M : Machine} {k : Nat} {xs ws : List Symbol} {t T : Nat} {b : Bool}
    (h : DecidesIn M k xs ws t b) (hle : t ≤ T) : DecidesIn M k xs ws T b := by
  obtain ⟨hst, hout⟩ := h
  have heq : execute M (startConfig2 k xs ws) T = execute M (startConfig2 k xs ws) t :=
    execute_of_halted_le hst hle
  exact ⟨by rw [heq]; exact hst, by rw [heq]; exact hout⟩

/-! ## The reduction -/

/-- The certificate length prescribed by the verifier's parameters. -/
def certLen (cw dw : Nat) (x : List Bool) : Nat := polyBound cw dw x.length

/-- The width of the tableau: wide enough for the verifier's running time, and
at least as wide as the input plus the certificate, so that every cell the
machine can reach is tracked. -/
def tabWidth (cw dw ct dt : Nat) (x : List Bool) : Nat :=
  max (polyBound ct dt (x.length + certLen cw dw x)) (x.length + certLen cw dw x + 1)

theorem le_tabWidth_time (cw dw ct dt : Nat) (x : List Bool) :
    polyBound ct dt (x.length + certLen cw dw x) ≤ tabWidth cw dw ct dt x :=
  Nat.le_max_left _ _

theorem le_tabWidth_len (cw dw ct dt : Nat) (x : List Bool) :
    x.length + certLen cw dw x + 1 ≤ tabWidth cw dw ct dt x :=
  Nat.le_max_right _ _

/-- **The Cook-Levin reduction.**

On input `x` it emits the tableau CNF of the verifier machine `Mv`, with the
instance pinned on tape `0` and the certificate left free on tape `1`, together
with the blank-suffix clauses that make the free region range over certificates
of *every* length up to the bound.  The definition consults `Mv`'s transition
function (through `tableauCNF`) but never runs it, and never mentions the
language being reduced. -/
def cookLevinReduction (Mv : Machine) (k G cw dw ct dt : Nat) (x : List Bool) : List Bool :=
  encodeFormula
    (tableauCNF ⟨k, G, Mv.length, tabWidth cw dw ct dt x⟩ Mv
        (reductionInit (boolsToSymbols x) (certLen cw dw x)) ++
      blankSuffixClauses ⟨k, G, Mv.length, tabWidth cw dw ct dt x⟩ 1)

/-- **Correctness of the reduction.**  The emitted formula is satisfiable
exactly when the verifier accepts some certificate.  `L'` appears nowhere, and
the certificate is quantified with `≤`, as the textbook definition of NP
requires. -/
theorem cookLevinReduction_correct {Mv : Machine} {k G cw dw ct dt : Nat}
    (hwf : TuringMachine k G Mv) {V : List Bool → List Bool → Bool}
    (hdec : ∀ x w : List Bool, DecidesIn Mv k (boolsToSymbols x) (boolsToSymbols w)
      (polyBound ct dt (x.length + w.length)) (V x w))
    (hlenV : ∀ x w : List Bool, V x w = true → w.length ≤ polyBound cw dw x.length)
    (x : List Bool) :
    SAT (cookLevinReduction Mv k G cw dw ct dt x) ↔ ∃ w : List Bool, V x w = true := by
  have hM : WellFormed k G Mv := hwf.wellFormed
  have hk : 2 ≤ k := hM.two_le
  have hG : 4 ≤ G := hM.four_le
  have hxs : ∀ s ∈ boolsToSymbols x, s < G :=
    fun s hs => Nat.lt_of_lt_of_le (boolsToSymbols_lt hs) hG
  have hlenbound := le_tabWidth_len cw dw ct dt x
  have hxT : (boolsToSymbols x).length ≤ tabWidth cw dw ct dt x := by
    simp only [length_boolsToSymbols]; omega
  have hmT : certLen cw dw x ≤ tabWidth cw dw ct dt x := by omega
  have h1T : 1 ≤ tabWidth cw dw ct dt x := by omega
  have h1k : (1 : Nat) < k := by omega
  /- Every certificate short enough for the tableau is decided in time at most
     the tableau's width, so `DecidesIn` at the bound transfers to width `T`. -/
  have hshift : ∀ w : List Bool, w.length ≤ certLen cw dw x →
      DecidesIn Mv k (boolsToSymbols x) (boolsToSymbols w)
        (tabWidth cw dw ct dt x) (V x w) := by
    intro w hw
    refine decidesIn_of_le (hdec x w) (Nat.le_trans ?_ (le_tabWidth_time cw dw ct dt x))
    exact polyBound_mono (by omega)
  rw [cookLevinReduction, SAT_encodeFormula_iff,
    tableau_correct_blank (sh := ⟨k, G, Mv.length, tabWidth cw dw ct dt x⟩) hM rfl h1T h1k
      (fun j _ p _ => reductionInit_lt hG hxs j p)]
  constructor
  · rintro ⟨cfg0, hstart, hbs, hacc⟩
    refine ⟨certOf cfg0 (certLen cw dw x), ?_⟩
    have hwlen : (certOf cfg0 (certLen cw dw x)).length ≤ certLen cw dw x :=
      length_certOf_le cfg0 _
    rw [eq_startConfig2_of_startOK hk hxT hmT hstart hbs] at hacc
    have htrue : DecidesIn Mv k (boolsToSymbols x)
        (boolsToSymbols (certOf cfg0 (certLen cw dw x))) (tabWidth cw dw ct dt x) true := hacc
    exact boolSym_inj ((hshift _ hwlen).2.symm.trans htrue.2)
  · rintro ⟨w, hw⟩
    have hwlen : w.length ≤ certLen cw dw x := hlenV x w hw
    have hdec' := hshift w hwlen
    rw [hw] at hdec'
    exact ⟨startConfig2 k (boolsToSymbols x) (boolsToSymbols w),
      startOK_startConfig2 hk hG hxs hwlen hxT hmT,
      blankSuffix_startConfig2 hk _ w, hdec'⟩

/-- The one ingredient of `cook_levin_nphard` that is not proved here: the
reduction is computable in polynomial time on the machine model.  It is stated
as an explicit hypothesis, not assumed as an axiom, and it mentions neither
`SAT` nor the language being reduced.

The verifier machine is assumed well formed.  That costs `cook_levin_nphard`
nothing -- it only ever applies this to an `Mv` that `InNP` already told it is
well formed -- and it is what a construction gets to rely on: `GoodCommand`
bounds what every command can write and where it can move. -/
def ReductionIsPolyTime : Prop :=
  ∀ (Mv : Machine) (k G cw dw ct dt : Nat), TuringMachine k G Mv →
    IsPolyTimeComputable (cookLevinReduction Mv k G cw dw ct dt)

/-! ## The fixed-input tableau

Specialising `reductionInit` to a start condition that pins *both* tapes gives
the tableau of a machine on a completely determined input, and the statement of
`reduction_correctness` in its classical form. -/

/-- The start condition pinning every cell of every tape. -/
def pinnedInit (xs ws : List Symbol) : TapeIdx → Nat → List Symbol :=
  fun j p => [startTape xs ws j p]

/-- The tableau CNF of `M` on the fixed input `xs` (tape `0`) and `ws`
(tape `1`), for `T` steps. -/
def buildTableauCNF (M : Machine) (k G : Nat) (xs ws : List Symbol) (T : Nat) : Formula :=
  tableauCNF ⟨k, G, M.length, T⟩ M (pinnedInit xs ws)

theorem eq_startConfig2_of_pinned {k G Q T : Nat} {xs ws : List Symbol} {cfg : Config}
    (hk : 2 ≤ k) (hxT : xs.length ≤ T) (hwT : ws.length ≤ T)
    (h : StartOK ⟨k, G, Q, T⟩ (pinnedInit xs ws) cfg) : cfg = startConfig2 k xs ws := by
  refine config_ext (by rw [h.st]; rfl) (by rw [h.len, startConfig2_length hk]) ?_
  intro j hj
  rw [h.len] at hj
  rw [tapeAt_startConfig2 hk xs ws hj]
  refine Prod.ext (funext fun p => ?_) (by rw [← headPos_eq, h.hd j hj])
  show tapeFun cfg j p = startTape xs ws j p
  by_cases hpT : p ≤ T
  · have hc : tapeFun cfg j p ∈ [startTape xs ws j p] := h.cells j hj p hpT
    simpa using hc
  · rw [h.blank j hj p (show T < p by omega),
      startTape_of_gt j hxT hwT (show T < p by omega)]

/-- **`reduction_correctness` in its classical form.**  The tableau of `M` on a
fixed input is satisfiable exactly when `M` accepts that input within `T`
steps.

Both directions are real: left to right extracts the run from the assignment
and shows by induction on time that it is *the* run of `M`; right to left
exhibits the assignment reading the accepting run off.  (The previous version of
this theorem was proved by running `M` inside `buildTableauCNF` and emitting
`[]` or `[[]]` accordingly.) -/
theorem reduction_correctness {M : Machine} {k G : Nat} (hwf : TuringMachine k G M)
    {xs ws : List Symbol} (hxs : ∀ s ∈ xs, s < G) (hws : ∀ s ∈ ws, s < G)
    {T : Nat} (h1T : 1 ≤ T) (hxT : xs.length ≤ T) (hwT : ws.length ≤ T) :
    Satisfiable (buildTableauCNF M k G xs ws T) ↔ AcceptsIn M k xs ws T := by
  have hM : WellFormed k G M := hwf.wellFormed
  have hk : 2 ≤ k := hM.two_le
  have hG : 4 ≤ G := hM.four_le
  have hinit : ∀ j, j < k → ∀ p, p ≤ T → ∀ s ∈ pinnedInit xs ws j p, s < G := by
    intro j _ p _ s hs
    simp only [pinnedInit, List.mem_singleton] at hs
    subst hs
    unfold startTape
    split
    · exact contents_lt hG hxs p
    · split
      · exact contents_lt hG hws p
      · exact contents_lt hG (by simp) p
  rw [buildTableauCNF,
    tableau_correct (sh := ⟨k, G, M.length, T⟩) hM rfl h1T hinit]
  constructor
  · rintro ⟨cfg0, hstart, hacc⟩
    rw [eq_startConfig2_of_pinned hk hxT hwT hstart] at hacc
    exact hacc
  · intro hacc
    refine ⟨startConfig2 k xs ws, ?_, hacc⟩
    refine ⟨startConfig2_length hk xs ws, rfl,
      fun j hj => headPos_startConfig2 hk xs ws hj, ?_, ?_, ?_⟩
    · intro j hj p _
      rw [tapeFun_startConfig2 hk xs ws hj]
      exact List.mem_cons_self
    · intro j hj p hp
      rw [tapeFun_startConfig2 hk xs ws hj]
      exact startTape_of_gt j hxT hwT hp
    · intro j hj p
      rw [tapeFun_startConfig2 hk xs ws hj]
      unfold startTape
      split
      · exact contents_lt hG hxs p
      · split
        · exact contents_lt hG hws p
        · exact contents_lt hG (by simp) p


/-! ## What the two input-facing groups are

`startClauses` is the one group whose clause *width* is not fixed by the shape:
it is `(init j p).length`, chosen by the caller.  That made it look like the
hardest group to emit after `transitionClauses`.  It is not, for the path that
actually matters.

`buildTableauCNF` -- the reduction's own entry point -- instantiates `init` at
`pinnedInit`, which hands back a **singleton** at every `(j, p)`.  So on that
path every clause of `startClauses` is a unit clause, and the group needs no
width machinery at all: a numeral, a one-index loop, and a two-index loop.

The generic `startClauses sh init` still has variable width, and `reductionInit`
really does use it -- the last theorem below is the witness. -/

/-- `acceptClauses` is not a loop of any kind: two unit clauses. -/
theorem acceptClauses_shape (sh : Shape) :
    acceptClauses sh =
      [[Literal.Pos (sh.stateVar sh.T sh.Q)],
       [Literal.Pos (sh.cellVar sh.T (verdictTape sh.k) 1 (boolSym true))]] := rfl

theorem acceptClauses_widths (sh : Shape) :
    (acceptClauses sh).map List.length = [1, 1] := rfl

/-- `startClauses` in its three parts. -/
theorem startClauses_shape (sh : Shape) (init : TapeIdx → Nat → List Symbol) :
    startClauses sh init =
      [[Literal.Pos (sh.stateVar 0 0)]] ++
      ((List.range sh.k).flatMap fun j => [[Literal.Pos (sh.headVar 0 j 0)]]) ++
      ((List.range sh.k).flatMap fun j =>
        (List.range (sh.T + 1)).flatMap fun p =>
          [(init j p).map fun s => Literal.Pos (sh.cellVar 0 j p s)]) := rfl

/-- Part 1 is a pure numeral -- independent of the entire shape. -/
theorem startClauses_part1 (sh : Shape) :
    clauseN [Literal.Pos (sh.stateVar 0 0)] = [5] := rfl

/-- Part 2 is one unit clause per tape, at the constant stride `8 * P`. -/
theorem startClauses_part2_stride (sh : Shape) (j : Nat) :
    2 * sh.headVar 0 j 0 + 1 = 3 + j * (8 * sh.P) := by
  unfold Shape.headVar pack
  rw [Nat.mul_zero, Nat.zero_add, Nat.add_zero, Nat.mul_comm j (8 * sh.P), Nat.mul_assoc]
  generalize sh.P * j = X
  omega

/-- `pinnedInit` pins every cell: one symbol, never a choice. -/
theorem pinnedInit_singleton (xs ws : List Symbol) (j p : Nat) :
    (pinnedInit xs ws j p).length = 1 := rfl

/-- **Under `pinnedInit`, part 3 is one unit clause per `(j, p)`.**  This is
what `buildTableauCNF` uses, so on the reduction's own path `startClauses`
carries no init-dependent width at all. -/
theorem startClauses_part3_pinned (sh : Shape) (xs ws : List Symbol) :
    ((List.range sh.k).flatMap fun j =>
      (List.range (sh.T + 1)).flatMap fun p =>
        [(pinnedInit xs ws j p).map fun s => Literal.Pos (sh.cellVar 0 j p s)])
      = (List.range sh.k).flatMap fun j =>
          (List.range (sh.T + 1)).flatMap fun p =>
            [[Literal.Pos (sh.cellVar 0 j p (startTape xs ws j p))]] := rfl

/-- The generic case really is different: `reductionInit` leaves the
certificate tape free, so its width is 3 in the middle and 1 at the ends. -/
theorem reductionInit_width_varies (xs : List Symbol) {m : Nat} (hm : m ≠ 0) :
    (reductionInit xs m 1 0).length = 1 ∧ (reductionInit xs m 1 1).length = 3 := by
  refine ⟨rfl, ?_⟩
  show (if (1:Nat) = 0 then [startSymbol]
    else if 1 ≤ m then [zeroSymbol, oneSymbol, blankSymbol] else [blankSymbol]).length = 3
  rw [if_neg (by omega), if_pos (Nat.one_le_iff_ne_zero.mpr hm)]
  rfl

end CookLevin
Source
https://github.com/Rizvonium/cook_levin_lean_v1/blob/main/CookLevinLean/Reduction.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me