Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Boolean gates and shared wire operations

Definition
CNFEncComplexity_RobsonMemoryGatePrimitives

by bersubs · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorysatisfiability

Operations on named Boolean wires for the Robson memory circuit, with exact semantics, framing, and polynomial-time compilation from explicit gate descriptions.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonConstraints
import Definitions.Def_CNFEncComplexity_encRobsonIn
import Definitions.Def_CNFEncComplexity_encWords
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_BitString
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Iteration
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_List
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_Binary
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_BinaryDiv
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Option
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Internal_ResourceFacts
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_TapeLemmas
import Definitions.Def_Complexitylib_0ebd467_Foundations_Data_BitString_Binary
import Definitions.Def_CookLevin_Satisfiability
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.BigOperators.Finprod
import Mathlib.Algebra.BigOperators.Group.List.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Combinatorics.Hall.Finite
import Mathlib.Computability.TuringMachine.Computable
import Mathlib.Data.Fin.Basic
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Fintype.Card
import Mathlib.Data.Fintype.EquivFin
import Mathlib.Data.Fintype.Option
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.List.Basic
import Mathlib.Data.List.Chain
import Mathlib.Data.List.GetD
import Mathlib.Data.List.Nodup
import Mathlib.Data.List.OfFn
import Mathlib.Data.List.Perm.Basic
import Mathlib.Data.List.Sort
import Mathlib.Data.Nat.Bits
import Mathlib.Data.Nat.Digits.Lemmas
import Mathlib.Data.Nat.Size
import Mathlib.Data.Num.Lemmas
import Mathlib.GroupTheory.Perm.Basic
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Logic.Equiv.Prod
import Mathlib.Logic.Function.Basic
import Mathlib.Logic.Function.Iterate
import Mathlib.Tactic.DeriveFintype
import Mathlib.Tactic.FinCases
import Mathlib.Tactic.IntervalCases
import Mathlib.Tactic.Ring

set_option maxHeartbeats 4000000
set_option linter.all false

/- trace primitives -/

/- robson-trace-support -/

namespace CNFEncComplexity.RobsonCNF

open CookLevin

def pinLiteral (out : ℕ) (value : Bool) : Literal :=
  if value then .Pos out else .Neg out

/-- The defining clauses for the specified local gate. -/
def Gate.compile : Gate → Formula
  | .pin out value => [[pinLiteral out value]]
  | .copy out a => [[.Neg out,.Pos a],[.Pos out,.Neg a]]
  | .inv out a => [[.Neg out,.Neg a],[.Pos out,.Pos a]]
  | .conj out a b => [[.Neg out,.Pos a],[.Neg out,.Pos b],[.Pos out,.Neg a,.Neg b]]
  | .disj out a b => [[.Pos out,.Neg a],[.Pos out,.Neg b],[.Neg out,.Pos a,.Pos b]]
  | .parity out a b =>
      [[.Pos out,.Neg a,.Pos b],[.Pos out,.Pos a,.Neg b],
       [.Neg out,.Pos a,.Pos b],[.Neg out,.Neg a,.Neg b]]
  | .mux out s a b =>
      [[.Neg s,.Neg out,.Pos a],[.Neg s,.Pos out,.Neg a],
       [.Pos s,.Neg out,.Pos b],[.Pos s,.Pos out,.Neg b]]
  | .assert clause => [clause]

theorem Gate.compile_correct (g : Gate) (α : Assignment) :
    Satisfies α g.compile ↔ g.Holds α := by
  cases g with
  | pin out b =>
    cases b <;> cases h : α out <;>
      simp [Gate.compile, Gate.Holds, pinLiteral, Satisfies, satisfiesClause, satisfiesLiteral, h]
  | copy out a =>
    cases h : α out <;> cases ha : α a <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha]
  | inv out a =>
    cases h : α out <;> cases ha : α a <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha]
  | conj out a b =>
    cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
  | disj out a b =>
    cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
  | parity out a b =>
    cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
  | mux out s a b =>
    cases h : α out <;> cases hs : α s <;> cases ha : α a <;> cases hb : α b <;>
      simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, hs, ha, hb]
  | assert clause => simp [Gate.compile, Gate.Holds, Satisfies]

@[simp] theorem Gate.length_compile (g : Gate) : g.compile.length ≤ 4 := by cases g <;> simp [Gate.compile]

def compile (gates : List Gate) : Formula := gates.flatMap Gate.compile

theorem compile_correct (gates : List Gate) (α : Assignment) :
    Satisfies α (compile gates) ↔ ∀ g ∈ gates, g.Holds α := by
  constructor
  · intro h g hg
    apply (g.compile_correct α).mp
    intro c hc
    exact h c (List.mem_flatMap.mpr ⟨g,hg,hc⟩)
  · intro h c hc
    obtain ⟨g,hg,hc⟩ := List.mem_flatMap.mp hc
    exact (g.compile_correct α).mpr (h g hg) c hc

theorem length_compile (gates : List Gate) : (compile gates).length ≤ 4*gates.length := by
  induction gates with
  | nil => simp [compile]
  | cons g gs ih =>
    rw [show compile (g::gs) = g.compile ++ compile gs from rfl, List.length_append, List.length_cons]
    have h := g.length_compile
    omega

/-- The local relation can use arbitrary auxiliary names. Only the projection onto
the specified variables determines the encoded function. -/
theorem isEncoding_of_gates {n : ℕ} (gates : List Gate) (X : Fin n → ℕ)
    (f : (Fin n → Bool) → Bool) (hX : Function.Injective X)
    (h : ∀ τ, f τ = true ↔ ∃ α : Assignment, (∀ i, α (X i) = τ i) ∧
      ∀ g ∈ gates, g.Holds α) :
    IsEncoding (compile gates) X f := by
  refine ⟨hX, fun τ => (h τ).trans ?_⟩
  simp only [compile_correct]

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson

theorem slotWidth_pos (cost : ℕ) : 0 < slotWidth cost := by
  unfold slotWidth
  exact Nat.pow_pos (by decide)

theorem le_slotWidth (cost : ℕ) : cost ≤ slotWidth cost := by
  cases cost with
  | zero => exact Nat.zero_le _
  | succ cost =>
    simpa [slotWidth,slotLevel,Nat.succ_le_iff] using Nat.lt_size_self cost

theorem slotWidth_le_double {cost : ℕ} (hc : 0 < cost) : slotWidth cost ≤ 2*cost := by
  cases h : slotLevel cost with
  | zero => simp [slotWidth,h]; omega
  | succ j =>
    have hj : j < (cost-1).size := by unfold slotLevel at h; omega
    have hp : 2^j ≤ cost-1 := Nat.lt_size.mp hj
    rw [slotWidth,h,pow_succ]
    omega

theorem alignedStart_lower {cursor width : ℕ} (hw : 0 < width) :
    cursor ≤ alignedStart cursor width := by
  have he := Nat.mod_add_div (cursor+width-1) width
  have hm := Nat.mod_lt (cursor+width-1) hw
  unfold alignedStart
  rw [Nat.mul_comm]
  omega

theorem alignedStart_upper {cursor width : ℕ} (hw : 0 < width) :
    alignedStart cursor width < cursor+width := by
  have hw' := Nat.div_mul_le_self (cursor+width-1) width
  unfold alignedStart
  omega

theorem dvd_alignedStart (cursor width : ℕ) : width ∣ alignedStart cursor width :=
  ⟨(cursor+width-1)/width, Nat.mul_comm ..⟩

theorem Starts.length_eq {cursor : ℕ} {costs starts : List ℕ}
    (h : Starts cursor costs starts) : starts.length = costs.length := by
  induction h with
  | nil => rfl
  | cons _ _ _ ih => simp [ih]

/-- The greedy schedule rounds each start up to its next aligned slot and uses at most four
units of total time per unit of the original cost, including the idle space. -/
theorem aligned_slots (costs : List ℕ) (hcost : ∀ cost ∈ costs, 0 < cost) (cursor : ℕ) :
    ∃ starts, Starts cursor costs starts ∧
      ∀ i : Fin costs.length,
        starts[i.val]? = some (starts[i.val]?.getD 0) ∧
        (starts[i.val]?.getD 0) + slotWidth costs[i] ≤ cursor+4*costs.sum := by
  induction costs generalizing cursor with
  | nil =>
    exact ⟨[], .nil _, fun i => Fin.elim0 i⟩
  | cons cost tail ih =>
    let len := slotWidth cost
    let start := alignedStart cursor len
    have hl : 0 < len := slotWidth_pos cost
    have hc : 0 < cost := hcost _ (by simp)
    have hs : start + len ≤ cursor + 4*cost := by
      have h1 : start < cursor+len := alignedStart_upper hl
      have h2 : len ≤ 2*cost := slotWidth_le_double hc
      omega
    obtain ⟨tl, he, hb⟩ := ih (fun _ h => hcost _ (List.mem_cons_of_mem _ h)) (start+len)
    refine ⟨start::tl, .cons (alignedStart_lower hl) (dvd_alignedStart _ _) he,?_⟩
    intro i
    refine Fin.cases ?_ (fun j => ?_) i
    · simp only [Fin.val_zero, List.getElem?_cons_zero, Option.getD_some, List.getElem_cons_zero,
        List.sum_cons, true_and]
      exact hs.trans (by omega)
    · obtain ⟨hj, hk⟩ := hb j
      change tl[j.val]? = some (tl[j.val]?.getD 0) ∧
        tl[j.val]?.getD 0 + slotWidth tail[j] ≤ cursor+4*(cost+tail.sum)
      exact ⟨hj,by omega⟩

/-- One level has budget exactly two to the power of the height. -/
theorem level_capacity {level height : ℕ} (h : level ≤ height) :
    2^(height-level) * 2^level = (2:ℕ)^height := by
  rw [← pow_add, Nat.sub_add_cancel h]

theorem allocated_bit_budget (height : ℕ) :
    ((List.range (height+1)).map (fun j => 2^(height-j)*2^j)).sum =
      (height+1)*2^height := by
  calc
    _ = ((List.range (height+1)).map (fun _ => (2:ℕ)^height)).sum := by
      congr 1
      apply List.map_congr_left
      intro j hj
      exact level_capacity (by have h := List.mem_range.mp hj; omega)
    _ = _ := by simp

/-- The dyadic horizon is linear in the original time bound. All slots from the greedy
schedule can be put in this horizon at levels of at most its height. -/
theorem compact_schedule (costs : List ℕ) (hc : ∀ c ∈ costs, 0 < c)
    {t : ℕ} (ht : costs.sum ≤ t) :
    let H := slotLevel (4*(t+1))
    2^H ≤ 8*(t+1) ∧
    ∃ starts, Starts 0 costs starts ∧ ∀ i : Fin costs.length,
      slotLevel costs[i] ≤ H ∧
      ∃ j : Fin (2^(H-slotLevel costs[i])),
        starts[i.val]? = some (j.val*slotWidth costs[i]) := by
  intro H
  have hH : 2^H ≤ 8*(t+1) := by
    have h := slotWidth_le_double (cost := 4*(t+1)) (by omega)
    simpa only [H,slotWidth,← Nat.mul_assoc] using h
  refine ⟨hH,?_⟩
  obtain ⟨starts, hstarts, hg⟩ := aligned_slots costs hc 0
  refine ⟨starts,hstarts,?_⟩
  have allAlign {cursor : ℕ} {costs starts : List ℕ} (h : Starts cursor costs starts) :
      ∀ i : Fin costs.length, slotWidth costs[i] ∣ (starts[i.val]?.getD 0) := by
    induction h with
    | nil => intro i; exact Fin.elim0 i
    | @cons cursor cost start costs starts _ hdiv _ ih =>
      intro i
      refine Fin.cases ?_ (fun i => ?_) i
      · simpa using hdiv
      · simpa using ih i
  intro i
  obtain ⟨j,hj⟩ := allAlign hstarts i
  have hTime := (hg i).2
  have hHor : 4*(t+1) ≤ (2:ℕ)^H := le_slotWidth _
  have hWidth : slotWidth costs[i] ≤ (2:ℕ)^H := by omega
  have hLev : slotLevel costs[i] ≤ H :=
    (Nat.pow_le_pow_iff_right (by decide)).mp hWidth
  have hjlt : j < 2^(H-slotLevel costs[i]) := by
    by_contra! hge
    have hm := Nat.mul_le_mul_right (slotWidth costs[i]) hge
    rw [show 2^(H-slotLevel costs[i]) * slotWidth costs[i] = 2^H from level_capacity hLev,
      Nat.mul_comm j, ← hj] at hm
    omega
  refine ⟨hLev,⟨j,hjlt⟩,?_⟩
  rw [Nat.mul_comm,← hj]
  exact (hg i).1

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

private def rank (t : ℕ) (s : ℕ × ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2

theorem layout_mem {t a j : ℕ} :
    (a,j) ∈ layoutSlots t ↔ a < layoutHorizon t ∧ j ≤ layoutHeight t ∧ a % 2^j = 0 := by
  simp [layoutSlots,List.mem_flatMap,List.mem_map,List.mem_filter,List.mem_range] <;> omega

theorem layout_sorted (t : ℕ) : (layoutSlots t).Pairwise (fun s s' => rank t s < rank t s') := by
  unfold layoutSlots
  rw [List.pairwise_flatMap]
  constructor
  · intro a ha
    have hp : (List.range (layoutHeight t+1)).Pairwise (·<·) := List.pairwise_lt_range
    apply (hp.filter (fun j => a % 2^j = 0)).map (fun j => (a,j))
    intro u v hh
    exact Nat.add_lt_add_left hh _
  · apply (List.pairwise_lt_range).imp
    intro a b hab x hx y hy
    obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hx
    obtain ⟨k,hk,rfl⟩ := List.mem_map.mp hy
    have hdj := List.mem_range.mp (List.mem_filter.mp hj).1
    have hb : (a+1)*(layoutHeight t+1) ≤ b*(layoutHeight t+1) :=
      Nat.mul_le_mul_right _ hab
    simp only [rank,Prod.fst,Prod.snd]
    rw [Nat.add_mul,Nat.one_mul] at hb
    omega

theorem layout_nodup (t : ℕ) : (layoutSlots t).Nodup :=
  (layout_sorted t).imp (fun h he => (Nat.ne_of_lt h) (congrArg _ he))

/-- Dyadic starts are strictly chronological, independent of the idle gaps. -/
theorem Starts.ordered {cursor : ℕ} {costs starts : List ℕ} (h : Starts cursor costs starts) :
    starts.Pairwise (·<·) ∧ ∀ a ∈ starts, cursor ≤ a := by
  induction h with
  | nil => simp
  | @cons cursor cost start costs starts hs _ _ ih =>
    refine ⟨List.pairwise_cons.mpr ⟨?_,ih.1⟩,?_⟩
    · intro a ha
      have h := ih.2 a ha
      have h' := slotWidth_pos cost
      omega
    · intro a ha
      rcases List.mem_cons.mp ha with rfl | ha
      · exact hs
      · exact hs.trans ((Nat.le_add_right _ _).trans (ih.2 a ha))

/-- Serial bit names are the product embedding of the naturally bounded port indices. -/
def portIndex (n t : ℕ) :
    (Fin n ⊕ ((Fin (layoutHorizon t) × Fin (layoutHeight t+1)) × Fin 19) ×
      Fin (layoutHorizon t)) ≃ Fin (sharedLimit n t) :=
  (Equiv.sumCongr (Equiv.refl _)
    ((((finProdFinEquiv.prodCongr (Equiv.refl (Fin 19))).trans finProdFinEquiv).prodCongr
      (Equiv.refl (Fin (layoutHorizon t)))).trans finProdFinEquiv)).trans finSumFinEquiv

theorem portIndex_input {n t : ℕ} (i : Fin n) :
    (portIndex n t (.inl i)).val = i.val := rfl

theorem portIndex_other {n t : ℕ} (a : Fin (layoutHorizon t))
    (j : Fin (layoutHeight t+1)) (f : Fin 19) (b : Fin (layoutHorizon t)) :
    (portIndex n t (.inr (((a,j),f),b))).val = port n t (a,j) f.val b.val := by
  change n+(b.val+layoutHorizon t*(f.val+19*(j.val+(layoutHeight t+1)*a.val))) = _
  unfold port
  simp only [Prod.fst,Prod.snd]
  ring

theorem port_lt_shared {n t a j f b : ℕ} (ha : a < layoutHorizon t)
    (hj : j ≤ layoutHeight t) (hf : f < 19) (hb : b < layoutHorizon t) :
    port n t (a,j) f b < sharedLimit n t := by
  rw [← portIndex_other ⟨a,ha⟩ ⟨j,by omega⟩ ⟨f,hf⟩ ⟨b,hb⟩]
  exact Fin.isLt _

theorem ports_agree {α β : Assignment} {n t : ℕ}
    (h : ∀ r < sharedLimit n t, α r = β r) :
    readStream α n t = readStream β n t ∧ memoryStream α n t = memoryStream β n t ∧
      inputTape α n = inputTape β n := by
  have hGet {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f b : ℕ} (hf : f < 19) (hb : b < 2^s.2) :
      α (port n t s f b) = β (port n t s f b) := by
    rcases s with ⟨a,j⟩
    obtain ⟨ha,hj,_⟩ := layout_mem.mp hs
    exact h _ (port_lt_shared ha hj hf (hb.trans_le (Nat.pow_le_pow_right (by decide) hj)))
  have hW {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f : ℕ} (hf : f < 19) :
      portWord α n t s f = portWord β n t s f := by
    unfold portWord
    congr 1
    apply List.map_congr_left
    intro b hb
    rw [hGet hs hf (List.mem_range.mp hb)]
  refine ⟨?_,?_,?_⟩
  · unfold readStream
    apply List.filterMap_congr
    intro s hs
    have hP : 0 < 2^s.2 := Nat.pow_pos (by decide)
    unfold portInput
    rw [hGet hs (by decide : 0 < 19) hP,hGet hs (by decide : 1 < 19) hP,
      hGet hs (by decide : 2 < 19) hP]
  · unfold memoryStream
    apply List.flatMap_congr
    intro s hs
    apply List.filterMap_congr
    intro i hi
    have hi3 := List.mem_range.mp hi
    have hP : 0 < 2^s.2 := Nat.pow_pos (by decide)
    dsimp only [portMemory]
    rw [hGet hs (by omega : 3+5*i < 19) hP,hGet hs (by omega : 3+5*i+1 < 19) hP,
      hW hs (by omega : 3+5*i+2 < 19),hW hs (by omega : 3+5*i+3 < 19),
      hW hs (by omega : 3+5*i+4 < 19)]
  · apply congrArg List.ofFn
    funext i
    exact h _ (i.isLt.trans_le (Nat.le_add_right _ _))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

theorem gate_congr {α β : Assignment} (g : Gate) (h : ∀ r ∈ Gate.names g, α r = β r) :
    g.Holds α ↔ g.Holds β := by
  cases g with
  | pin a =>
    simp only [Gate.names,List.mem_singleton,forall_eq] at h
    simp only [Gate.Holds,h]
  | copy a b | inv a b =>
    rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names])]
  | conj a b c | disj a b c | parity a b c =>
    rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names]),
      h c (by simp [Gate.names])]
  | mux a b c d =>
    rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names]),
      h c (by simp [Gate.names]),h d (by simp [Gate.names])]
  | assert ls =>
    change ls.any (satisfiesLiteral α) = true ↔ ls.any (satisfiesLiteral β) = true
    have hx : ∀ lit ∈ ls, satisfiesLiteral α lit = satisfiesLiteral β lit := by
      intro lit hl
      have hh := h lit.var (List.mem_map.mpr ⟨lit,hl,rfl⟩)
      cases lit <;> simp_all [satisfiesLiteral,Literal.var]
    have he : List.any ls (satisfiesLiteral α) = List.any ls (satisfiesLiteral β) := by
      clear h
      induction ls with
      | nil => rfl
      | cons l ls ih =>
        simp only [List.any_cons]
        rw [hx l (by simp),ih (fun x hx' => hx x (by simp [hx']))]
    rw [he]

theorem simultaneous_extensions (base : ℕ) (gates : Fin 3 → List Gate) (α : Assignment)
    (ht : ∀ i, ∀ g ∈ gates i, ∀ r ∈ Gate.names g, owns base i r)
    (he : ∀ i, ExtendsWith base (gates i) α) :
    ExtendsWith base (gates 0 ++ gates 1 ++ gates 2) α := by
  classical
  choose β hβ hGate using he
  let f (r : ℕ) : Fin 3 := ⟨(r-base)%3,Nat.mod_lt _ (by decide)⟩
  let after (r : ℕ) := if r < base then α r else β (f r) r
  have hb (i : Fin 3) (r : ℕ) (hr : owns base i r) : after r = β i r := by
    by_cases h : r < base
    · simp [after,h,hβ i r h]
    · have hf : f r = i := Fin.ext (hr.resolve_left h)
      simp [after,h,hf]
  refine ⟨after,fun r hr => by simp [after,hr],?_⟩
  intro g hg
  simp only [List.mem_append] at hg
  rcases hg with (hg|hg)|hg
  · exact (gate_congr g (fun r hr => hb 0 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)
  · exact (gate_congr g (fun r hr => hb 1 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)
  · exact (gate_congr g (fun r hr => hb 2 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

def slotCenter (s : ℕ × ℕ) : ℕ := 2*s.1+2^s.2

private theorem alignedCenter_multiple {a j : ℕ} (ha : a % 2^j = 0) :
    slotCenter (a,j) = (2*(a / 2^j)+1)*2^j := by
  have ha' := Nat.mod_add_div a (2^j)
  rw [ha,Nat.zero_add] at ha'
  unfold slotCenter
  dsimp
  rw [Nat.add_mul,Nat.one_mul, Nat.mul_assoc,Nat.mul_comm (a/2^j),ha']

private theorem alignedCenter_val {a j : ℕ} (ha : a % 2^j = 0) :
    slotCenter (a,j) % 2^(j+1) = 2^j := by
  rw [alignedCenter_multiple ha,Nat.pow_succ,Nat.add_mul,Nat.one_mul]
  rw [show 2*(a/2^j)*2^j = (a/2^j)*(2^j*2) by ring,Nat.mul_add_mod_self_right]
  have hj : 0 < 2^j := Nat.pow_pos (by decide)
  exact Nat.mod_eq_of_lt (by omega)

private theorem alignedCenter_dvd {a j : ℕ} (ha : a % 2^j = 0) :
    2^j ∣ slotCenter (a,j) := by
  rw [alignedCenter_multiple ha]
  exact Nat.dvd_mul_left _ _

theorem slotCenter_injOn (t : ℕ) {s r : ℕ × ℕ}
    (hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (he : slotCenter s = slotCenter r) : s=r := by
  rcases s with ⟨a,j⟩
  rcases r with ⟨b,k⟩
  have ha := (layout_mem.mp hs).2.2
  have hb := (layout_mem.mp hr).2.2
  have hNoLt {a b j k : ℕ} (ha : a % 2^j = 0) (hb : b % 2^k = 0)
      (he : slotCenter (a,j) = slotCenter (b,k)) : ¬ j < k := by
    intro hLt
    have hd : 2^(j+1) ∣ 2^k := Nat.pow_dvd_pow 2 hLt
    have hh := dvd_trans hd (alignedCenter_dvd hb)
    rw [← he, Nat.dvd_iff_mod_eq_zero, alignedCenter_val ha] at hh
    exact Nat.ne_of_gt (Nat.pow_pos (by decide)) hh
  have heJ : j=k := by
    apply Nat.le_antisymm (Nat.le_of_not_gt (hNoLt hb ha he.symm))
    exact Nat.le_of_not_gt (hNoLt ha hb he)
  subst k
  unfold slotCenter at he
  dsimp at he
  have : a=b := by omega
  simp [this]

theorem slotCenter_lt (t : ℕ) {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) :
    slotCenter s < 2*layoutHorizon t := by
  rcases s with ⟨a,j⟩
  obtain ⟨ha,hj,hDiv⟩ := layout_mem.mp hs
  have hd : 2^j ∣ layoutHorizon t := Nat.pow_dvd_pow 2 hj
  obtain ⟨r,hr⟩ := hd
  have hEq := Nat.mod_add_div a (2^j)
  rw [hDiv,Nat.zero_add] at hEq
  have hQ : a/2^j < r := by
    apply Nat.lt_of_mul_lt_mul_left (a := 2^j)
    rw [hEq,← hr]
    exact ha
  have hCap : a + 2^j ≤ layoutHorizon t := by
    have hh := Nat.mul_le_mul_left (2^j) hQ
    rw [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,hEq,← hr] at hh
    exact hh
  have hP : 0 < 2^j := Nat.pow_pos (by decide)
  unfold slotCenter
  dsimp
  omega

theorem layoutSlots_length_le (t : ℕ) : (layoutSlots t).length ≤ 2*layoutHorizon t := by
  let l := (layoutSlots t).map slotCenter
  have hND : l.Nodup := by
    apply List.Nodup.map_on _ (layout_nodup t)
    exact fun _ hs _ hr he => slotCenter_injOn t hs hr he
  have hSub : l ⊆ List.range (2*layoutHorizon t) := by
    intro m hm
    obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hm
    exact List.mem_range.mpr (slotCenter_lt t hs)
  have h := hND.length_le_of_subset hSub
  simpa [l] using h

end CNFEncComplexity.Robson

namespace CNFEncComplexity.RobsonCNF

open CookLevin

/-- The current less-than and equality bits occupy the first two wires of each group.
The other two wires test the current input bit pair, if present. -/
def ltWire (base i : ℕ) := base + 4*i
def eqWire (base i : ℕ) := base + 4*i + 1
def diffWire (base i : ℕ) := base + 4*i + 2
def sameWire (base i : ℕ) := base + 4*i + 3

def compareStep (base i : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  [.parity (diffWire base i) (lhs i) (rhs i),
   .inv (sameWire base i) (diffWire base i),
   .mux (ltWire base (i+1)) (diffWire base i) (rhs i) (ltWire base i),
   .conj (eqWire base (i+1)) (sameWire base i) (eqWire base i)]

/-- Four gates per bit over a little-endian key, plus initial less-than and equal bits. -/
def compareCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  [.pin (ltWire base 0) false, .pin (eqWire base 0) true] ++
    (List.range n).flatMap (fun i => compareStep base i lhs rhs)

theorem length_compareCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) :
    (compareCircuit base n lhs rhs).length = 4*n+2 := by
  have h (xs : List ℕ) : (xs.flatMap (fun i => compareStep base i lhs rhs)).length = 4*xs.length := by
    induction xs with
    | nil => rfl
    | cons i xs ih =>
      simp only [List.flatMap_cons, List.length_append, List.length_cons, ih]
      change 4+4*xs.length = 4*(xs.length+1)
      omega
  simp only [compareCircuit, List.length_append, List.length_cons, List.length_nil, h, List.length_range]
  omega

/-- Numeric value of the indicated prefix, little-endian. -/
def wireValue (α : Assignment) (key : ℕ → ℕ) : ℕ → ℕ
  | 0 => 0
  | n+1 => wireValue α key n + (if α (key n) then 2^n else 0)

theorem wireValue_lt (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
    wireValue α key n < 2^n := by
  induction n with
  | zero => simp [wireValue]
  | succ n ih =>
    simp only [wireValue, pow_succ]
    split <;> omega

theorem wireValue_congr {α β : Assignment} {key : ℕ → ℕ} {n : ℕ}
    (h : ∀ i < n, α (key i) = β (key i)) :
    wireValue α key n = wireValue β key n := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [wireValue, wireValue, ih (fun i hi => h i (by omega)), h n (by omega)]

theorem wireValue_lt_succ (α : Assignment) (lhs rhs : ℕ → ℕ) (i : ℕ) :
    decide (wireValue α lhs (i+1) < wireValue α rhs (i+1)) =
      if α (lhs i) ^^ α (rhs i) then α (rhs i) else decide (wireValue α lhs i < wireValue α rhs i) := by
  have hL := wireValue_lt α lhs i
  have hR := wireValue_lt α rhs i
  cases hl : α (lhs i) <;> cases hr : α (rhs i)
  · simp [wireValue, hl, hr]
  · simp [wireValue, hl, hr]
    omega
  · simp [wireValue, hl, hr]
    omega
  · simp [wireValue, hl, hr]

theorem wireValue_eq_succ (α : Assignment) (lhs rhs : ℕ → ℕ) (i : ℕ) :
    decide (wireValue α lhs (i+1) = wireValue α rhs (i+1)) =
      ((!(α (lhs i) ^^ α (rhs i))) && decide (wireValue α lhs i = wireValue α rhs i)) := by
  have hL := wireValue_lt α lhs i
  have hR := wireValue_lt α rhs i
  cases hl : α (lhs i) <;> cases hr : α (rhs i)
  · simp [wireValue, hl, hr]
  · simp [wireValue, hl, hr]
    omega
  · simp [wireValue, hl, hr]
    omega
  · simp [wireValue, hl, hr]

theorem compareCircuit_outputs (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ compareCircuit base n lhs rhs, g.Holds α) :
    ∀ i ≤ n,
      α (ltWire base i) = decide (wireValue α lhs i < wireValue α rhs i) ∧
      α (eqWire base i) = decide (wireValue α lhs i = wireValue α rhs i) := by
  intro i hi
  induction i with
  | zero =>
    have hl := h (.pin (ltWire base 0) false) (by simp [compareCircuit])
    have he := h (.pin (eqWire base 0) true) (by simp [compareCircuit])
    exact ⟨hl,he⟩
  | succ i ih =>
    obtain ⟨hL,hE⟩ := ih (by omega)
    have hh : ∀ g ∈ compareStep base i lhs rhs, g.Holds α := by
      intro g hg
      exact h g (List.mem_append.mpr (Or.inr (List.mem_flatMap.mpr
        ⟨i,List.mem_range.mpr (by omega),hg⟩)))
    have hD : α (diffWire base i) = (α (lhs i) ^^ α (rhs i)) :=
      hh (.parity (diffWire base i) (lhs i) (rhs i)) (by simp [compareStep])
    have hS : α (sameWire base i) = !α (diffWire base i) :=
      hh (.inv (sameWire base i) (diffWire base i)) (by simp [compareStep])
    have hL' : α (ltWire base (i+1)) =
        if α (diffWire base i) then α (rhs i) else α (ltWire base i) :=
      hh (.mux (ltWire base (i+1)) (diffWire base i) (rhs i) (ltWire base i)) (by simp [compareStep])
    have hE' : α (eqWire base (i+1)) = (α (sameWire base i) && α (eqWire base i)) :=
      hh (.conj (eqWire base (i+1)) (sameWire base i) (eqWire base i)) (by simp [compareStep])
    exact ⟨by rw [hL',hD,hL,wireValue_lt_succ], by rw [hE',hS,hD,hE,wireValue_eq_succ]⟩

/-- Canonical extension of an assignment after introducing comparator wires. -/
def compareAssign (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (k : ℕ) : Bool :=
  if k < base then α k else
    let i := (k-base)/4
    match (k-base)%4 with
    | 0 => decide (wireValue α lhs i < wireValue α rhs i)
    | 1 => decide (wireValue α lhs i = wireValue α rhs i)
    | 2 => α (lhs i) ^^ α (rhs i)
    | _ => !(α (lhs i) ^^ α (rhs i))

theorem compareAssign_preserves {base k : ℕ} (hk : k < base)
    (lhs rhs : ℕ → ℕ) (α : Assignment) :
    compareAssign base lhs rhs α k = α k := by simp [compareAssign,hk]

private theorem wire_divMod (base i j : ℕ) (hj : j < 4) :
    ¬base+4*i+j < base ∧ (base+4*i+j-base)/4 = i ∧ (base+4*i+j-base)%4 = j := by
  omega

@[simp] theorem compareAssign_lt (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
    compareAssign base lhs rhs α (ltWire base i) =
      decide (wireValue α lhs i < wireValue α rhs i) := by
  obtain ⟨h,hD,hM⟩ := wire_divMod base i 0 (by decide)
  simp only [Nat.add_zero] at h hD hM
  simp [compareAssign,ltWire,h,hD,hM]

@[simp] theorem compareAssign_eq (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
    compareAssign base lhs rhs α (eqWire base i) =
      decide (wireValue α lhs i = wireValue α rhs i) := by
  obtain ⟨h,hD,hM⟩ := wire_divMod base i 1 (by decide)
  simp [compareAssign,eqWire,h,hD,hM]

@[simp] theorem compareAssign_diff (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
    compareAssign base lhs rhs α (diffWire base i) = (α (lhs i) ^^ α (rhs i)) := by
  obtain ⟨h,hD,hM⟩ := wire_divMod base i 2 (by decide)
  simp [compareAssign,diffWire,h,hD,hM]

@[simp] theorem compareAssign_same (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
    compareAssign base lhs rhs α (sameWire base i) = !(α (lhs i) ^^ α (rhs i)) := by
  obtain ⟨h,hD,hM⟩ := wire_divMod base i 3 (by decide)
  simp [compareAssign,sameWire,h,hD,hM]

theorem compareCircuit_extends (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∀ g ∈ compareCircuit base n lhs rhs, g.Holds (compareAssign base lhs rhs α) := by
  intro g hg
  rcases List.mem_append.mp hg with h | h
  · rcases List.mem_cons.mp h with hg | h
    · subst g
      simp [Gate.Holds,wireValue]
    · have hg : g = Gate.pin (eqWire base 0) true := by simpa using h
      subst g
      simp [Gate.Holds,wireValue]
  · obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp h
    have hi' := List.mem_range.mp hi
    simp only [compareStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl | rfl | rfl <;>
      simp [Gate.Holds, compareAssign_preserves (hL i hi'), compareAssign_preserves (hR i hi'),
        wireValue_lt_succ, wireValue_eq_succ]

/-- Correctness and realizability for one comparator in Cook–Levin's formula format. -/
theorem compareFormula_exact (base n : ℕ) (lhs rhs : ℕ → ℕ)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
    (α : Assignment) (lb eb : Bool) :
    (∃ β : Assignment, (∀ k < base, β k = α k) ∧
        Satisfies β (compile (compareCircuit base n lhs rhs)) ∧
        β (ltWire base n) = lb ∧ β (eqWire base n) = eb) ↔
      lb = decide (wireValue α lhs n < wireValue α rhs n) ∧
      eb = decide (wireValue α lhs n = wireValue α rhs n) := by
  constructor
  · rintro ⟨β,hβ,hSat,hl,he⟩
    obtain ⟨hLt,hEq⟩ := compareCircuit_outputs base n lhs rhs β ((compile_correct _ _).mp hSat) n le_rfl
    have hlv := wireValue_congr (α := β) (β := α) (fun i hi => hβ (lhs i) (hL i hi))
    have hrv := wireValue_congr (α := β) (β := α) (fun i hi => hβ (rhs i) (hR i hi))
    rw [hlv,hrv] at hLt hEq
    exact ⟨hl.symm.trans hLt, he.symm.trans hEq⟩
  · intro ⟨hl,he⟩
    refine ⟨compareAssign base lhs rhs α, fun k hk => compareAssign_preserves hk _ _ _,
      (compile_correct _ _).mpr (compareCircuit_extends base n lhs rhs α hL hR), ?_, ?_⟩
    · simpa using hl.symm
    · simpa using he.symm

/-- Join two little-endian subkeys, with the first subkey less significant. -/
def joinKey (low high : ℕ → ℕ) (n : ℕ) (i : ℕ) : ℕ :=
  if i < n then low i else high (i-n)

theorem wireValue_key_congr (α : Assignment) {lhs rhs : ℕ → ℕ} {n : ℕ}
    (h : ∀ i < n, lhs i = rhs i) :
    wireValue α lhs n = wireValue α rhs n := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [wireValue,wireValue,ih (fun i hi => h i (by omega)),h n (by omega)]

theorem wireValue_joinKey (α : Assignment) (low high : ℕ → ℕ) (n m : ℕ) :
    wireValue α (joinKey low high n) (n+m) =
      wireValue α low n + 2^n * wireValue α high m := by
  induction m with
  | zero =>
    rw [Nat.add_zero,wireValue,Nat.mul_zero,Nat.add_zero]
    apply wireValue_key_congr
    intro i hi
    rw [joinKey,if_pos hi]
  | succ m ih =>
    have hJ : joinKey low high n (n+m) = high m := by
      rw [joinKey,if_neg (by omega)]
      simp
    change wireValue α (joinKey low high n) (n+m) + (if α (joinKey low high n (n+m))
      then 2^(n+m) else 0) = wireValue α low n +
      2^n * (wireValue α high m + if α (high m) then 2^m else 0)
    rw [ih,hJ,Nat.mul_add,pow_add]
    cases h : α (high m) <;> simp [h,Nat.add_assoc]

/-- Stable memory order compares address first and preserves the chronological order
of records at a common address. The timestamp is the low block. -/
theorem wireValue_joinKey_lt (α : Assignment)
    (timeL timeR addrL addrR : ℕ → ℕ) (tW aW : ℕ) :
    wireValue α (joinKey timeL addrL tW) (tW+aW) <
      wireValue α (joinKey timeR addrR tW) (tW+aW) ↔
    wireValue α addrL aW < wireValue α addrR aW ∨
      (wireValue α addrL aW = wireValue α addrR aW ∧
        wireValue α timeL tW < wireValue α timeR tW) := by
  rw [wireValue_joinKey,wireValue_joinKey]
  let b : ℕ := 2^tW
  let al := wireValue α addrL aW
  let ar := wireValue α addrR aW
  let tl := wireValue α timeL tW
  let tr := wireValue α timeR tW
  change tl+b*al < tr+b*ar ↔ al < ar ∨ (al=ar ∧ tl < tr)
  have htL : tl < b := wireValue_lt _ _ _
  have htR : tr < b := wireValue_lt _ _ _
  have hLess (x y : ℕ) (hx : x < y) : b*x+b ≤ b*y := by
    rw [← Nat.mul_succ]
    exact Nat.mul_le_mul_left _ hx
  rcases lt_trichotomy al ar with hA | hA | hA
  · have hh := hLess al ar hA
    exact ⟨fun _ => Or.inl hA,fun _ => by omega⟩
  · rw [hA]
    simp
  · have hh := hLess ar al hA
    exact ⟨fun h => by omega,fun h => by omega⟩

/-- Names read and written by a gate. This allows independently allocated comparators
to be combined under a single assignment. -/
def Gate.names : Gate → List ℕ
  | .pin out _ => [out]
  | .copy out a => [out,a]
  | .inv out a => [out,a]
  | .conj out a b | .disj out a b | .parity out a b => [out,a,b]
  | .mux out s a b => [out,s,a,b]
  | .assert c => c.map Literal.var

theorem Gate.holds_congr (g : Gate) (α β : Assignment)
    (h : ∀ i ∈ g.names, α i = β i) :
    g.Holds α ↔ g.Holds β := by
  cases g with
  | pin out v => simp [Gate.names,Gate.Holds] at h ⊢; rw [h]
  | copy out a => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2]
  | inv out a => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2]
  | conj out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
  | disj out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
  | parity out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
  | mux out s a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2.1,h.2.2.2]
  | assert c =>
    change (satisfiesClause α c = true) ↔ (satisfiesClause β c = true)
    rw [satisfiesClause_congr (fun l hl => h l.var (List.mem_map.mpr ⟨l,hl,rfl⟩))]

theorem compareCircuit_names_lt (base n : ℕ) (lhs rhs : ℕ → ℕ)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∀ g ∈ compareCircuit base n lhs rhs, ∀ k ∈ g.names, k < base+4*n+2 := by
  intro g hg k hk
  rcases List.mem_append.mp hg with hg | hg
  · simp only [List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl <;>
      simp [Gate.names,ltWire,eqWire] at hk <;> omega
  · obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
    have hi' := List.mem_range.mp hi
    have hli := hL i hi'
    have hri := hR i hi'
    simp only [compareStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl | rfl | rfl <;>
      simp [Gate.names,ltWire,eqWire,diffWire,sameWire] at hk <;> omega

/-- A comparator assignment need only change its own interval of fresh names. -/
theorem compareCircuit_extends_interval (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∃ β : Assignment,
      (∀ k, (k < base ∨ base+4*n+2 ≤ k) → β k = α k) ∧
      (∀ g ∈ compareCircuit base n lhs rhs, g.Holds β) := by
  let β : Assignment := fun k => if k < base+4*n+2 then compareAssign base lhs rhs α k else α k
  refine ⟨β, ?_, ?_⟩
  · intro k hk
    rcases hk with hk | hk
    · simp [β, show k < base+4*n+2 by omega, compareAssign_preserves hk]
    · simp [β, Nat.not_lt_of_ge hk]
  · intro g hg
    apply (g.holds_congr (compareAssign base lhs rhs α) β (fun k hk => by
      simp [β,compareCircuit_names_lt base n lhs rhs hL hR g hg k hk])).mp
    exact compareCircuit_extends base n lhs rhs α hL hR g hg

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open CookLevin

/-- A carry or borrow takes the first wire of each eight-wire region. -/
def rippleCarryWire (base i : ℕ) := base+8*i
def rippleXorWire (base i : ℕ) := base+8*i+1
def rippleBitWire (base i : ℕ) := base+8*i+2
private def invLeftWire (base i : ℕ) := base+8*i+3
private def invXorWire (base i : ℕ) := base+8*i+4
private def firstCarryWire (base i : ℕ) := base+8*i+5
private def secondCarryWire (base i : ℕ) := base+8*i+6

/-- Successor carry for ordinary addition, or successor borrow for subtraction. -/
def rippleNext (subtract a b carry : Bool) : Bool :=
  if subtract then ((!a && b) || (!(a ^^ b) && carry))
  else ((a && b) || ((a ^^ b) && carry))

def rippleStep (subtract : Bool) (base i : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  let a := lhs i
  let b := rhs i
  let p := rippleXorWire base i
  let c := rippleCarryWire base i
  let changeA := invLeftWire base i
  let changeP := invXorWire base i
  let c₁ := firstCarryWire base i
  let c₂ := secondCarryWire base i
  [.parity p a b,
    .parity (rippleBitWire base i) p c,
    .inv changeA a,
    .inv changeP p,
    .conj c₁ (if subtract then changeA else a) b,
    .conj c₂ (if subtract then changeP else p) c,
    .disj (rippleCarryWire base (i+1)) c₁ c₂]

def rippleCircuit (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  .pin (rippleCarryWire base 0) false ::
  (List.range n).flatMap (fun i => rippleStep subtract base i lhs rhs)

theorem length_rippleCircuit (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) :
    (rippleCircuit subtract base n lhs rhs).length = 7*n+1 := by
  have h (xs : List ℕ) :
      (xs.flatMap (fun i => rippleStep subtract base i lhs rhs)).length = 7*xs.length := by
    induction xs with
    | nil => rfl
    | cons i xs ih =>
      simp only [List.flatMap_cons,List.length_append,List.length_cons,ih]
      change 7+7*xs.length = 7*(xs.length+1)
      omega
  simp only [rippleCircuit,List.length_cons,h,List.length_range]

theorem rippleStep_outputs (subtract : Bool) (base i : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (h : ∀ g ∈ rippleStep subtract base i lhs rhs, g.Holds α) :
    α (rippleBitWire base i) = ((α (lhs i) ^^ α (rhs i)) ^^ α (rippleCarryWire base i)) ∧
      α (rippleCarryWire base (i+1)) =
        rippleNext subtract (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i)) := by
  let p := rippleXorWire base i
  let c := rippleCarryWire base i
  let changeA := invLeftWire base i
  let changeP := invXorWire base i
  let c₁ := firstCarryWire base i
  let c₂ := secondCarryWire base i
  have hp : α p = (α (lhs i) ^^ α (rhs i)) :=
    h (.parity p (lhs i) (rhs i)) (by simp [rippleStep,p])
  have hbit : α (rippleBitWire base i) = (α p ^^ α c) :=
    h (.parity (rippleBitWire base i) p c) (by simp [rippleStep,p,c])
  have ha : α changeA = !α (lhs i) :=
    h (.inv changeA (lhs i)) (by simp [rippleStep,changeA])
  have hcp : α changeP = !α p :=
    h (.inv changeP p) (by simp [rippleStep,changeP,p])
  have h1 : α c₁ = (α (if subtract then changeA else lhs i) && α (rhs i)) :=
    h (.conj c₁ (if subtract then changeA else lhs i) (rhs i)) (by simp [rippleStep,c₁,changeA])
  have h2 : α c₂ = (α (if subtract then changeP else p) && α c) :=
    h (.conj c₂ (if subtract then changeP else p) c) (by simp [rippleStep,c₂,changeP,p,c])
  have hc : α (rippleCarryWire base (i+1)) = (α c₁ || α c₂) :=
    h (.disj (rippleCarryWire base (i+1)) c₁ c₂) (by simp [rippleStep,c₁,c₂])
  exact ⟨by rw [hbit,hp],by cases subtract <;> simp [rippleNext,hc,h1,h2,ha,hcp,hp,c]⟩

private theorem wireValue_succ_bit (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
    wireValue α key (n+1) = wireValue α key n + (α (key n)).toNat * 2^n := by
  cases h : α (key n) <;> simp [wireValue,h]

/-- The recursive value used by the arithmetic gadgets agrees with the weighted
sum on numeric-address ports. -/
theorem wireValue_eq_sum (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
    wireValue α key n =
      ((List.range n).map fun i => (α (key i)).toNat * 2^i).sum := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [wireValue_succ_bit,ih,List.range_succ,List.map_append,List.sum_append]
    simp

private theorem add_bit_equation (a b c : Bool) :
    a.toNat + b.toNat + c.toNat = ((a ^^ b) ^^ c).toNat + 2*(rippleNext false a b c).toNat := by
  cases a <;> cases b <;> cases c <;> decide

private theorem subtract_bit_equation (a b c : Bool) :
    a.toNat + 2*(rippleNext true a b c).toNat = b.toNat + c.toNat + ((a ^^ b) ^^ c).toNat := by
  cases a <;> cases b <;> cases c <;> decide

theorem rippleCircuit_add (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ rippleCircuit false base n lhs rhs, g.Holds α) :
    ∀ i ≤ n, wireValue α lhs i + wireValue α rhs i =
      wireValue α (rippleBitWire base) i + (α (rippleCarryWire base i)).toNat * 2^i := by
  intro i hi
  induction i with
  | zero =>
    have hc : α (rippleCarryWire base 0) = false :=
      h (.pin (rippleCarryWire base 0) false) (by simp [rippleCircuit])
    simp [wireValue,hc]
  | succ i ih =>
    have h' : ∀ g ∈ rippleStep false base i lhs rhs, g.Holds α := by
      intro g hg
      exact h g (List.mem_cons.mpr (.inr (List.mem_flatMap.mpr
        ⟨i,List.mem_range.mpr (by omega),hg⟩)))
    obtain ⟨hbit,hcarry⟩ := rippleStep_outputs false base i lhs rhs α h'
    have he := add_bit_equation (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i))
    rw [← hbit, ← hcarry] at he
    have hp := congrArg (fun z : ℕ => z*2^i) he
    simp only [Nat.add_mul,Nat.mul_assoc] at hp
    have hs := ih (by omega)
    simp only [wireValue_succ_bit,pow_succ]
    have hh : (α (rippleCarryWire base (i+1))).toNat * (2^i*2) =
        2*((α (rippleCarryWire base (i+1))).toNat * 2^i) := by ac_rfl
    rw [hh]
    omega

theorem rippleCircuit_subtract (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ rippleCircuit true base n lhs rhs, g.Holds α) :
    ∀ i ≤ n, wireValue α lhs i + (α (rippleCarryWire base i)).toNat * 2^i =
      wireValue α rhs i + wireValue α (rippleBitWire base) i := by
  intro i hi
  induction i with
  | zero =>
    have hc : α (rippleCarryWire base 0) = false :=
      h (.pin (rippleCarryWire base 0) false) (by simp [rippleCircuit])
    simp [wireValue,hc]
  | succ i ih =>
    have h' : ∀ g ∈ rippleStep true base i lhs rhs, g.Holds α := by
      intro g hg
      exact h g (List.mem_cons.mpr (.inr (List.mem_flatMap.mpr
        ⟨i,List.mem_range.mpr (by omega),hg⟩)))
    obtain ⟨hbit,hcarry⟩ := rippleStep_outputs true base i lhs rhs α h'
    have he := subtract_bit_equation (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i))
    rw [← hbit, ← hcarry] at he
    have hp := congrArg (fun z : ℕ => z*2^i) he
    simp only [Nat.add_mul,Nat.mul_assoc] at hp
    have hs := ih (by omega)
    simp only [wireValue_succ_bit,pow_succ]
    have hh : (α (rippleCarryWire base (i+1))).toNat * (2^i*2) =
        2*((α (rippleCarryWire base (i+1))).toNat * 2^i) := by ac_rfl
    rw [hh]
    omega

/-- Canonical auxiliary carry values, computed on the unchanged operands. -/
private def carryPrefix (subtract : Bool) (lhs rhs : ℕ → ℕ) (α : Assignment) : ℕ → Bool
  | 0 => false
  | i+1 => rippleNext subtract (α (lhs i)) (α (rhs i)) (carryPrefix subtract lhs rhs α i)

def rippleAssign (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (k : ℕ) : Bool :=
  if k < base then α k else
    let i := (k-base)/8
    let a := α (lhs i)
    let b := α (rhs i)
    let p := a ^^ b
    let c := carryPrefix subtract lhs rhs α i
    match (k-base)%8 with
    | 0 => c
    | 1 => p
    | 2 => p ^^ c
    | 3 => !a
    | 4 => !p
    | 5 => (if subtract then !a else a) && b
    | 6 => (if subtract then !p else p) && c
    | _ => false

theorem rippleAssign_preserves {base k : ℕ} (hk : k < base) (subtract : Bool)
    (lhs rhs : ℕ → ℕ) (α : Assignment) :
    rippleAssign subtract base lhs rhs α k = α k := by simp [rippleAssign,hk]

private theorem eq_aux (base i j : ℕ) (hj : j < 8) :
    ¬base+8*i+j < base ∧ (base+8*i+j-base)/8 = i ∧ (base+8*i+j-base)%8 = j := by
  omega

private theorem rippleAssign_carry (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (rippleCarryWire base i) =
      carryPrefix subtract lhs rhs α i := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 0 (by decide)
  simp only [Nat.add_zero] at h hD hM
  simp [rippleCarryWire,rippleAssign,h,hM]

private theorem rippleAssign_xor (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (rippleXorWire base i) = (α (lhs i) ^^ α (rhs i)) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 1 (by decide)
  simp [rippleXorWire,rippleAssign,h,hD,hM]

private theorem rippleAssign_bit (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (rippleBitWire base i) =
      ((α (lhs i) ^^ α (rhs i)) ^^ carryPrefix subtract lhs rhs α i) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 2 (by decide)
  simp [rippleBitWire,rippleAssign,h,hD,hM]

private theorem rippleAssign_invLeft (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (invLeftWire base i) = !α (lhs i) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 3 (by decide)
  simp [invLeftWire,rippleAssign,h,hD,hM]

private theorem rippleAssign_invXor (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (invXorWire base i) = !(α (lhs i) ^^ α (rhs i)) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 4 (by decide)
  simp [invXorWire,rippleAssign,h,hD,hM]

private theorem rippleAssign_first (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (firstCarryWire base i) =
      ((if subtract then !α (lhs i) else α (lhs i)) && α (rhs i)) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 5 (by decide)
  simp [firstCarryWire,rippleAssign,h,hD,hM]

private theorem rippleAssign_second (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
    (α : Assignment) (i : ℕ) :
    rippleAssign subtract base lhs rhs α (secondCarryWire base i) =
      ((if subtract then !(α (lhs i) ^^ α (rhs i)) else (α (lhs i) ^^ α (rhs i))) &&
        carryPrefix subtract lhs rhs α i) := by
  obtain ⟨h,hD,hM⟩ := eq_aux base i 6 (by decide)
  simp [secondCarryWire,rippleAssign,h,hD,hM]

theorem rippleCircuit_extends (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∀ g ∈ rippleCircuit subtract base n lhs rhs, g.Holds (rippleAssign subtract base lhs rhs α) := by
  intro g hg
  rcases List.mem_cons.mp hg with h | h
  · subst g
    simp [Gate.Holds,rippleAssign_carry,carryPrefix]
  · obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp h
    have hi' := List.mem_range.mp hi
    simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
      cases subtract <;>
      simp [Gate.Holds, rippleAssign_preserves (hL i hi'), rippleAssign_preserves (hR i hi'),
        rippleAssign_carry,rippleAssign_xor,rippleAssign_bit,rippleAssign_invLeft,rippleAssign_invXor,
        rippleAssign_first,rippleAssign_second,carryPrefix,rippleNext]

/-- An output with one additional high wire is exact natural addition. -/
def addOutputWire (base n : ℕ) (i : ℕ) :=
  if i < n then rippleBitWire base i else rippleCarryWire base n

theorem rippleCircuit_add_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ rippleCircuit false base n lhs rhs, g.Holds α) :
    wireValue α (addOutputWire base n) (n+1) =
      wireValue α lhs n + wireValue α rhs n := by
  have hs := rippleCircuit_add base n lhs rhs α h n le_rfl
  have hp : wireValue α (addOutputWire base n) n =
      wireValue α (rippleBitWire base) n := by
    apply wireValue_key_congr
    intro i hi
    simp [addOutputWire,hi]
  simp [wireValue_succ_bit,hp,addOutputWire,hs]

def monusMaskWire (base n : ℕ) := base+8*n+1
def monusOutWire (base n i : ℕ) := base+8*n+2+i

def monusMask (base n : ℕ) : List Gate :=
  .inv (monusMaskWire base n) (rippleCarryWire base n) ::
  (List.range n).map (fun i => .conj (monusOutWire base n i) (monusMaskWire base n) (rippleBitWire base i))

def monusCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  rippleCircuit true base n lhs rhs ++ monusMask base n

theorem length_monusCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) :
    (monusCircuit base n lhs rhs).length = 8*n+2 := by
  simp only [monusCircuit,List.length_append,length_rippleCircuit,monusMask,List.length_cons,
    List.length_map,List.length_range]
  omega

theorem monusCircuit_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ monusCircuit base n lhs rhs, g.Holds α) :
    wireValue α (monusOutWire base n) n = wireValue α lhs n-wireValue α rhs n := by
  have hRaw : ∀ g ∈ rippleCircuit true base n lhs rhs, g.Holds α :=
    fun g hg => h g (List.mem_append.mpr (.inl hg))
  have hSub := rippleCircuit_subtract base n lhs rhs α hRaw n le_rfl
  have hBound := wireValue_lt α (rippleBitWire base) n
  have hMask : α (monusMaskWire base n) = !α (rippleCarryWire base n) :=
    h (.inv (monusMaskWire base n) (rippleCarryWire base n))
      (by simp [monusCircuit,monusMask])
  have hOut (i : ℕ) (hi : i < n) :
      α (monusOutWire base n i) = (α (monusMaskWire base n) && α (rippleBitWire base i)) :=
    h (.conj (monusOutWire base n i) (monusMaskWire base n) (rippleBitWire base i))
      (List.mem_append.mpr (.inr (List.mem_cons.mpr (.inr (List.mem_map.mpr
        ⟨i,List.mem_range.mpr hi,rfl⟩)))))
  cases hb : α (rippleCarryWire base n) with
  | false =>
    have ha : wireValue α (monusOutWire base n) n =
        wireValue α (rippleBitWire base) n := by
      let β : Assignment := fun i => α (rippleBitWire base i)
      let γ : Assignment := fun i => α (monusOutWire base n i)
      have he : wireValue γ id n = wireValue β id n := by
        apply wireValue_congr
        intro i hi
        simp [γ,β,hOut i hi,hMask,hb]
      have hval (key : ℕ → ℕ) (i : ℕ) :
          wireValue (α ∘ key) id i = wireValue α key i := by
        induction i with
        | zero => rfl
        | succ i ih => simp [wireValue,ih]
      rw [show γ = α ∘ monusOutWire base n from rfl,show β = α ∘ rippleBitWire base from rfl,
        hval,hval] at he
      exact he
    simp only [hb,Bool.toNat_false,Nat.zero_mul,Nat.add_zero] at hSub
    omega
  | true =>
    have ha (i : ℕ) (hi : i ≤ n) : wireValue α (monusOutWire base n) i = 0 := by
      induction i with
      | zero => rfl
      | succ i ih =>
        simp [wireValue,ih (by omega),hOut i (by omega),hMask,hb]
    simp only [hb,Bool.toNat_true,Nat.one_mul] at hSub
    have hzero := ha n le_rfl
    omega

theorem rippleCircuit_names_lt (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∀ g ∈ rippleCircuit subtract base n lhs rhs, ∀ k ∈ g.names, k < base+8*n+1 := by
  intro g hg k hk
  rcases List.mem_cons.mp hg with rfl | hg
  · simp [Gate.names,rippleCarryWire] at hk
    omega
  · obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
    have hi' := List.mem_range.mp hi
    have hli := hL i hi'
    have hri := hR i hi'
    simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
      cases subtract <;>
      simp [Gate.names,rippleCarryWire,rippleXorWire,rippleBitWire,invLeftWire,invXorWire,
        firstCarryWire,secondCarryWire] at hk <;> omega

theorem rippleCircuit_extends_interval (subtract : Bool) (base n : ℕ)
    (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∃ β : Assignment,
      (∀ k, (k < base ∨ base+8*n+1 ≤ k) → β k = α k) ∧
      (∀ g ∈ rippleCircuit subtract base n lhs rhs, g.Holds β) := by
  let ρ := rippleAssign subtract base lhs rhs α
  let β : Assignment := fun k => if k < base+8*n+1 then ρ k else α k
  refine ⟨β,?_,?_⟩
  · intro k hk
    rcases hk with hk | hk
    · simp only [β,if_pos (show k < base+8*n+1 by omega),ρ,rippleAssign_preserves hk]
    · simp only [β,if_neg (Nat.not_lt_of_ge hk)]
  · intro g hg
    apply (g.holds_congr ρ β (fun k hk => by
      simp only [β,if_pos (rippleCircuit_names_lt subtract base n lhs rhs hL hR g hg k hk)])).mp
    exact rippleCircuit_extends subtract base n lhs rhs α hL hR g hg

theorem monusCircuit_extends_interval (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
    ∃ β : Assignment,
      (∀ k, (k < base ∨ base+9*n+2 ≤ k) → β k = α k) ∧
      (∀ g ∈ monusCircuit base n lhs rhs, g.Holds β) := by
  let ρ := rippleAssign true base lhs rhs α
  let c := rippleCarryWire base n
  let m := monusMaskWire base n
  let mask := !ρ c
  let β : Assignment := fun k =>
    if k < base+9*n+2 then
      if k < m then ρ k else
        if k=m then mask else mask && ρ (rippleBitWire base (k-m-1))
    else α k
  have hm : m = base+8*n+1 := rfl
  have hc : c < m := by rw [hm]; unfold c rippleCarryWire; omega
  have hPrefix (k : ℕ) (hk : k < m) : β k = ρ k := by simp [β,hk,show k < base+9*n+2 by omega]
  have hMask : β m = mask := by simp [β,show m < base+9*n+2 by omega]
  refine ⟨β,?_,?_⟩
  · intro k hk
    rcases hk with hk | hk
    · rw [hPrefix k (by omega)]
      exact rippleAssign_preserves hk true lhs rhs α
    · simp [β,Nat.not_lt_of_ge hk]
  · intro g hg
    rcases List.mem_append.mp hg with hg | hg
    · exact (g.holds_congr ρ β (fun k hk => (hPrefix k
        (rippleCircuit_names_lt true base n lhs rhs hL hR g hg k hk)).symm)).mp
        (rippleCircuit_extends true base n lhs rhs α hL hR g hg)
    · rcases List.mem_cons.mp hg with rfl | hg
      · change β m = !β c
        rw [hMask,hPrefix c hc]
      · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
        have hi' := List.mem_range.mp hi
        have hBit : rippleBitWire base i < m := by unfold rippleBitWire; omega
        have hOut : monusOutWire base n i = m+1+i := by unfold monusOutWire; omega
        change β (monusOutWire base n i) = (β m && β (rippleBitWire base i))
        rw [hMask,hPrefix _ hBit,hOut]
        have hNum : m+1+i-m-1 = i := by omega
        simp [β,show m+1+i < base+9*n+2 by omega,show ¬m+1+i < m by omega,
          show m+1+i ≠ m by omega,hNum]

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open CookLevin

private def hasHighBit (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) : Prop :=
  ∃ j : Fin n, i ≤ j.val ∧ α (key j.val) = true

private instance (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) :
    Decidable (hasHighBit α key n i) := by unfold hasHighBit; infer_instance

private theorem hasHighBit_succ (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) (hi : i < n) :
    hasHighBit α key n i ↔ α (key i) = true ∨ hasHighBit α key n (i+1) := by
  constructor
  · rintro ⟨j,hij,hj⟩
    by_cases h : j.val=i
    · exact Or.inl (by simpa [h] using hj)
    · exact Or.inr ⟨j,by omega,hj⟩
  · rintro (h | ⟨j,hij,hj⟩)
    · exact ⟨⟨i,hi⟩,le_rfl,h⟩
    · exact ⟨j,by omega,hj⟩

private theorem hasHighBit_le (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
    (h : hasHighBit α key n i) : 2^i ≤ wireValue α key n := by
  obtain ⟨j,hij,hj⟩ := h
  have hw (u : ℕ) (hu : j.val < u) : 2^j.val ≤ wireValue α key u := by
    induction u with
    | zero => omega
    | succ u ih =>
      by_cases hU : j.val=u
      · have hBit : α (key u) = true := hU ▸ hj
        simp [wireValue,hU,hBit]
      · have hle := ih (by have := j.isLt; omega)
        rw [wireValue]
        omega
  exact (Nat.pow_le_pow_right (by decide) hij).trans (hw n j.isLt)

private theorem wireValue_eq_prefix (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
    (hi : i ≤ n) (h : ¬hasHighBit α key n i) :
    wireValue α key n = wireValue α key i := by
  induction n with
  | zero => exact congrArg (wireValue α key) (Nat.eq_zero_of_le_zero hi).symm
  | succ n ih =>
    by_cases hEq : i=n+1
    · rw [hEq]
    have hBit : α (key n) = false := by
      by_contra hh
      exact h ⟨⟨n,Nat.lt_succ_self _⟩,by change i ≤ n; omega,by simpa using hh⟩
    have hn : ¬hasHighBit α key n i := by
      rintro ⟨j,hj,hOn⟩
      exact h ⟨j.castSucc,hj,hOn⟩
    simp [wireValue,hBit,ih (by omega) hn]

private theorem highBit_iff_size (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) :
    hasHighBit α key n i ↔ i < (wireValue α key n).size := by
  rw [← not_le, Nat.size_le]
  constructor
  · exact fun h => not_lt.mpr (hasHighBit_le α key n i h)
  · intro h
    by_contra hn
    by_cases hi : i ≤ n
    · exact h ((wireValue_eq_prefix α key n i hi hn) ▸ wireValue_lt α key i)
    · exact h ((wireValue_lt α key n).trans_le (Nat.pow_le_pow_right (by decide) (by omega)))

def widthFlagWire (base i : ℕ) := base+i

/-- The output at index i is true exactly when the length of the binary word
is greater than i. The final sentinel flag is false. -/
def widthCircuit (base n : ℕ) (key : ℕ → ℕ) : List Gate :=
  .pin (widthFlagWire base n) false ::
    (List.range n).map (fun i => .disj (widthFlagWire base i) (key i) (widthFlagWire base (i+1)))

theorem length_widthCircuit (base n : ℕ) (key : ℕ → ℕ) :
    (widthCircuit base n key).length = n+1 := by simp [widthCircuit]

private theorem decide_hasHighBit_succ (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
    (hi : i < n) :
    decide (hasHighBit α key n i) =
      (α (key i) || decide (hasHighBit α key n (i+1))) := by
  have he := hasHighBit_succ α key n i hi
  by_cases h : hasHighBit α key n i
  · rcases he.mp h with h0 | h1 <;> simp_all
  · have h1 : α (key i) = false := by
      cases hi : α (key i)
      · rfl
      · exact False.elim (h (he.mpr (.inl hi)))
    have h2 : ¬ hasHighBit α key n (i+1) := fun h' => h (he.mpr (.inr h'))
    simp [h,h1,h2]

theorem widthCircuit_exact (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ widthCircuit base n key, g.Holds α) {i : ℕ} (hi : i ≤ n) :
    α (widthFlagWire base i) = decide (i < (wireValue α key n).size) := by
  have hF (k : ℕ) (hk : k ≤ n) :
      α (widthFlagWire base (n-k)) = decide (hasHighBit α key n (n-k)) := by
    induction k with
    | zero =>
      have hx : α (widthFlagWire base n) = false :=
        h (.pin (widthFlagWire base n) false) (by simp [widthCircuit])
      have hNo : ¬hasHighBit α key n n := by
        rintro ⟨j,hj,_⟩
        have := j.isLt
        omega
      simp [hx,hNo]
    | succ k ih =>
      let j := n-(k+1)
      have hj : j < n := by unfold j; omega
      have hp : α (widthFlagWire base j) = (α (key j) || α (widthFlagWire base (j+1))) :=
        h (.disj (widthFlagWire base j) (key j) (widthFlagWire base (j+1)))
          (List.mem_cons.mpr (.inr (List.mem_map.mpr ⟨j,List.mem_range.mpr hj,rfl⟩)))
      have hc : j+1=n-k := by unfold j; omega
      change α (widthFlagWire base j) = decide (hasHighBit α key n j)
      rw [hp,hc,ih (by omega),decide_hasHighBit_succ α key n j hj,hc]
  have hE := hF (n-i) (Nat.sub_le _ _)
  rw [Nat.sub_sub_self hi] at hE
  rw [hE]
  have hiff := highBit_iff_size α key n i
  by_cases h : hasHighBit α key n i
  · simp [h,hiff.mp h]
  · have hh : ¬i < (wireValue α key n).size := fun hn => h (hiff.mpr hn)
    simp only [h,hh,decide_false]

theorem widthCircuit_extends_interval (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
    (hKey : ∀ i < n, key i < base) :
    ∃ β : Assignment, (∀ k, k < base ∨ base+n+1 ≤ k → β k = α k) ∧
      (∀ g ∈ widthCircuit base n key, g.Holds β) := by
  let β : Assignment := fun k =>
    if base ≤ k ∧ k ≤ base+n then decide (hasHighBit α key n (k-base)) else α k
  have hFlag (i : ℕ) (hi : i ≤ n) :
      β (widthFlagWire base i) = decide (hasHighBit α key n i) := by
    have h : base ≤ base+i ∧ base+i ≤ base+n := by omega
    simp [β,widthFlagWire,h]
  have hLow (k : ℕ) (hk : k < base) : β k = α k := by simp [β,show ¬base ≤ k by omega]
  refine ⟨β,?_,?_⟩
  · intro k hk
    rcases hk with hk | hk
    · exact hLow k hk
    · simp [β,show ¬k ≤ base+n by omega]
  · intro g hg
    rcases List.mem_cons.mp hg with rfl | hg
    · change β (widthFlagWire base n) = false
      have hNil : ¬hasHighBit α key n n := by
        rintro ⟨j,hj,_⟩
        have := j.isLt
        omega
      rw [hFlag n le_rfl]
      simp [hNil]
    · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
      have hI := List.mem_range.mp hi
      change β (widthFlagWire base i) = (β (key i) || β (widthFlagWire base (i+1)))
      rw [hFlag i hI.le, hFlag (i+1) hI, hLow _ (hKey i hI)]
      exact decide_hasHighBit_succ α key n i hI

open scoped BigOperators in
/-- Charging one unit for each active width flag recovers the ordinary binary length. -/
theorem widthCircuit_sum (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ widthCircuit base n key, g.Holds α) :
    ∑ i ∈ Finset.range n, (α (widthFlagWire base i)).toNat = (wireValue α key n).size := by
  let k := (wireValue α key n).size
  have hRange : k ≤ n := Nat.size_le.mpr (wireValue_lt α key n)
  have hfilter : (Finset.range n).filter (·<k) = Finset.range k := by
    ext i
    simp only [Finset.mem_filter,Finset.mem_range]
    omega
  change ∑ i ∈ Finset.range n, (α (widthFlagWire base i)).toNat = k
  calc
    _ = ∑ i ∈ Finset.range n, (if i < k then 1 else 0) := by
      apply Finset.sum_congr rfl
      intro i hi
      rw [widthCircuit_exact base n key α h (Finset.mem_range.mp hi).le]
      change (decide (i < k)).toNat = _
      by_cases hh : i < k <;> simp [hh]
    _ = ∑ i ∈ (Finset.range n).filter (·<k), (1:ℕ) := by rw [Finset.sum_filter]
    _ = k := by rw [hfilter]; simp

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open CookLevin

/-- Guard a local gate block by a literal. No auxiliary wire is needed. -/
def guarded (enable : Literal) (body : List Gate) : List Gate :=
  (compile body).map fun c => Gate.assert (enable.negate :: c)

theorem length_guarded (enable : Literal) (body : List Gate) :
    (guarded enable body).length ≤ 4*body.length := by
  rw [guarded,List.length_map]
  exact length_compile body

theorem guarded_exact (enable : Literal) (body : List Gate) (α : Assignment) :
    (∀ g ∈ guarded enable body, g.Holds α) ↔
      (satisfiesLiteral α enable = true → ∀ g ∈ body, g.Holds α) := by
  rw [← compile_correct body α]
  constructor
  · intro h enabled c hc
    have hg := h (Gate.assert (enable.negate::c)) (List.mem_map.mpr ⟨c,hc,rfl⟩)
    change satisfiesClause α (enable.negate::c) = true at hg
    rwa [satisfiesClause_cons,satisfiesLiteral_negate,enabled] at hg
  · intro h g hg
    obtain ⟨c,hc,rfl⟩ := List.mem_map.mp hg
    change satisfiesClause α (enable.negate::c) = true
    rw [satisfiesClause_cons,satisfiesLiteral_negate]
    cases he : satisfiesLiteral α enable
    · rfl
    · simpa using h he c hc

/-- Renaming all wires commutes with literal evaluation. -/
def Literal.rename (name : ℕ → ℕ) : Literal → Literal
  | .Neg r => .Neg (name r)
  | .Pos r => .Pos (name r)

theorem literal_rename_correct (name : ℕ → ℕ) (α : Assignment) (value : Literal) :
    satisfiesLiteral α (Literal.rename name value) = satisfiesLiteral (α ∘ name) value := by
  cases value <;> rfl

def Gate.rename (name : ℕ → ℕ) : Gate → Gate
  | .pin o v => .pin (name o) v
  | .copy o x => .copy (name o) (name x)
  | .inv o x => .inv (name o) (name x)
  | .conj o x y => .conj (name o) (name x) (name y)
  | .disj o x y => .disj (name o) (name x) (name y)
  | .parity o x y => .parity (name o) (name x) (name y)
  | .mux o s x y => .mux (name o) (name s) (name x) (name y)
  | .assert c => .assert (c.map (Literal.rename name))

theorem renamedNames (name : ℕ → ℕ) (g : Gate) :
    (g.rename name).names = g.names.map name := by
  cases g with
  | assert c =>
    simp only [Gate.rename,Gate.names,List.map_map]
    congr 1
    funext lit
    cases lit <;> rfl
  | _ => rfl

theorem renamedGate_correct (name : ℕ → ℕ) (α : Assignment) (g : Gate) :
    (g.rename name).Holds α ↔ g.Holds (α ∘ name) := by
  cases g with
  | assert c =>
    have hl : satisfiesLiteral α ∘ Literal.rename name = satisfiesLiteral (α ∘ name) := by
      funext l
      exact literal_rename_correct name α l
    simp only [Gate.rename,Gate.Holds,satisfiesClause,List.any_map,hl]
  | _ => rfl

theorem renamedCircuit_correct (name : ℕ → ℕ) (α : Assignment) (body : List Gate) :
    (∀ g ∈ body.map (Gate.rename name), g.Holds α) ↔ ∀ g ∈ body, g.Holds (α ∘ name) := by
  simp only [List.mem_map]
  constructor
  · intro h g hg
    exact (renamedGate_correct name α g).mp (h _ ⟨g,hg,rfl⟩)
  · rintro h _ ⟨g,hg,rfl⟩
    exact (renamedGate_correct name α g).mpr (h g hg)

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime

section Build
variable {α : Type} {input : α ↪ List Bool}

/-- The finite gate record consists of the corresponding named wires in unary. -/
theorem gate_of_fields {g : α → Gate} {code : α → List ℕ}
    (hCode : ComputableTidilyInPolyTime code input (encList encUnary))
    (he : ∀ a, (g a).code = code a) :
    ComputableTidilyInPolyTime g input gateEnc :=
  hCode.of_enc_eq (fun a => congrArg (encList encUnary) (he a))

theorem gate_pin (value : Bool) {out : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.pin (out a) value) input gateEnc := by
  cases value <;>
  first
  | exact gate_of_fields (cons' (const 0) (cons' ho (const []))) (fun _ => rfl)
  | exact gate_of_fields (cons' (const 1) (cons' ho (const []))) (fun _ => rfl)

theorem gate_copy {out src : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hx : ComputableTidilyInPolyTime src input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.copy (out a) (src a)) input gateEnc :=
  gate_of_fields (cons' (const 2) (cons' ho (cons' hx (const [])))) (fun _ => rfl)

theorem gate_inv {out src : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hx : ComputableTidilyInPolyTime src input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.inv (out a) (src a)) input gateEnc :=
  gate_of_fields (cons' (const 3) (cons' ho (cons' hx (const [])))) (fun _ => rfl)

theorem gate_conj {out x y : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hx : ComputableTidilyInPolyTime x input encUnary)
    (hy : ComputableTidilyInPolyTime y input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.conj (out a) (x a) (y a)) input gateEnc :=
  gate_of_fields (cons' (const 4) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)

theorem gate_disj {out x y : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hx : ComputableTidilyInPolyTime x input encUnary)
    (hy : ComputableTidilyInPolyTime y input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.disj (out a) (x a) (y a)) input gateEnc :=
  gate_of_fields (cons' (const 5) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)

theorem gate_parity {out x y : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hx : ComputableTidilyInPolyTime x input encUnary)
    (hy : ComputableTidilyInPolyTime y input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.parity (out a) (x a) (y a)) input gateEnc :=
  gate_of_fields (cons' (const 6) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)

theorem gate_mux {out s x y : α → ℕ}
    (ho : ComputableTidilyInPolyTime out input encUnary)
    (hs : ComputableTidilyInPolyTime s input encUnary)
    (hx : ComputableTidilyInPolyTime x input encUnary)
    (hy : ComputableTidilyInPolyTime y input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.mux (out a) (s a) (x a) (y a)) input gateEnc :=
  gate_of_fields (cons' (const 7) (cons' ho (cons' hs (cons' hx (cons' hy (const [])))))) (fun _ => rfl)

theorem gate_assert {c : α → CookLevin.Clause}
    (hc : ComputableTidilyInPolyTime (CookLevin.clauseN ∘ c) input (encList encUnary)) :
    ComputableTidilyInPolyTime (fun a => Gate.assert (c a)) input gateEnc :=
  gate_of_fields (cons' (const 8) hc) (fun _ => rfl)

private theorem cmp_index {base i : α → ℕ} (hb : ComputableTidilyInPolyTime base input encUnary)
    (hi : ComputableTidilyInPolyTime i input encUnary) (t : ℕ) :
    ComputableTidilyInPolyTime (fun a => base a+4*i a+t) input encUnary :=
  unary_add.comp ((unary_add.comp (hb.prod (unary_mul.comp ((const 4).prod hi)))).prod (const t))

private theorem compareStep_poly {base i lhs rhs : α → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hi : ComputableTidilyInPolyTime i input encUnary)
    (hl : ComputableTidilyInPolyTime lhs input encUnary)
    (hr : ComputableTidilyInPolyTime rhs input encUnary) :
    ComputableTidilyInPolyTime (fun a => compareStep (base a) (i a)
      (fun _ => lhs a) (fun _ => rhs a)) input (encList gateEnc) := by
  have hLt := cmp_index hb hi 0
  have hEq := cmp_index hb hi 1
  have hDiff := cmp_index hb hi 2
  have hSame := cmp_index hb hi 3
  have hSucc := unary_add.comp (hi.prod (const 1))
  have hLtSucc := cmp_index hb hSucc 0
  have hEqSucc := cmp_index hb hSucc 1
  have result := cons' (gate_parity hDiff hl hr)
    (cons' (gate_inv hSame hDiff) (cons' (gate_mux hLtSucc hDiff hr hLt)
      (cons' (gate_conj hEqSucc hSame hEq) (const []))))
  simpa only [compareStep,ltWire,eqWire,diffWire,sameWire,Function.comp_apply,Nat.add_zero] using result

/-- Uniformly generate the comparator given a polynomial-time address calculation
for both operand wires at a unary coordinate. -/
theorem compareCircuit_polytime {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hn : ComputableTidilyInPolyTime n input encUnary)
    (hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
      (encPair input encUnary) encUnary)
    (hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
      (encPair input encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => compareCircuit (base a) (n a) (lhs a) (rhs a))
      input (encList gateEnc) := by
  have hs := compareStep_poly (hb.comp (fst input encUnary)) (snd input encUnary) hl hr
  have hs' : ComputableTidilyInPolyTime
      (fun a : α × ℕ => compareStep (base a.1) a.2 (lhs a.1) (rhs a.1))
      (encPair input encUnary) (encList gateEnc) := hs
  have hBody := flatMapWithInput (f := fun a i => compareStep (base a) i (lhs a) (rhs a))
    (range.comp hn) hs'
  have hLt := cmp_index hb (const 0) 0
  have hEq := cmp_index hb (const 0) 1
  exact cons' (gate_pin false hLt) (cons' (gate_pin true hEq) hBody)

private theorem arith_index {base i : α → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hi : ComputableTidilyInPolyTime i input encUnary) (t : ℕ) :
    ComputableTidilyInPolyTime (fun a => base a+8*i a+t) input encUnary :=
  unary_add.comp ((unary_add.comp (hb.prod (unary_mul.comp ((const 8).prod hi)))).prod (const t))

private theorem rippleStep_poly (subtract : Bool) {base i lhs rhs : α → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hi : ComputableTidilyInPolyTime i input encUnary)
    (hl : ComputableTidilyInPolyTime lhs input encUnary)
    (hr : ComputableTidilyInPolyTime rhs input encUnary) :
    ComputableTidilyInPolyTime (fun a => rippleStep subtract (base a) (i a)
      (fun _ => lhs a) (fun _ => rhs a)) input (encList gateEnc) := by
  have hC := arith_index hb hi 0
  have hP := arith_index hb hi 1
  have hO := arith_index hb hi 2
  have hNotA := arith_index hb hi 3
  have hNotP := arith_index hb hi 4
  have hS := arith_index hb hi 5
  have hT := arith_index hb hi 6
  have hNext := arith_index hb (unary_add.comp (hi.prod (const 1))) 0
  have hFin := cons' (gate_disj hNext hS hT) (const [])
  cases subtract
  · have hCarr := cons' (gate_conj hS hl hr) (cons' (gate_conj hT hP hC) hFin)
    exact cons' (gate_parity hP hl hr) (cons' (gate_parity hO hP hC)
      (cons' (gate_inv hNotA hl) (cons' (gate_inv hNotP hP) hCarr)))
  · have hCarr := cons' (gate_conj hS hNotA hr) (cons' (gate_conj hT hNotP hC) hFin)
    exact cons' (gate_parity hP hl hr) (cons' (gate_parity hO hP hC)
      (cons' (gate_inv hNotA hl) (cons' (gate_inv hNotP hP) hCarr)))

theorem rippleCircuit_polytime (subtract : Bool) {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hn : ComputableTidilyInPolyTime n input encUnary)
    (hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
      (encPair input encUnary) encUnary)
    (hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
      (encPair input encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => rippleCircuit subtract (base a) (n a) (lhs a) (rhs a))
      input (encList gateEnc) := by
  have hs := rippleStep_poly subtract (hb.comp (fst input encUnary)) (snd input encUnary) hl hr
  have hs' : ComputableTidilyInPolyTime
      (fun a : α × ℕ => rippleStep subtract (base a.1) a.2 (lhs a.1) (rhs a.1))
      (encPair input encUnary) (encList gateEnc) := hs
  exact cons' (gate_pin false (arith_index hb (const 0) 0))
    (flatMapWithInput (f := fun a i => rippleStep subtract (base a) i (lhs a) (rhs a))
      (range.comp hn) hs')

theorem monusCircuit_polytime {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hn : ComputableTidilyInPolyTime n input encUnary)
    (hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
      (encPair input encUnary) encUnary)
    (hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
      (encPair input encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => monusCircuit (base a) (n a) (lhs a) (rhs a))
      input (encList gateEnc) := by
  have hFirst := rippleCircuit_polytime true hb hn hl hr
  have hKill := arith_index hb hn 1
  have hBorrow := arith_index hb hn 0
  have hOld := arith_index (hb.comp (fst input encUnary)) (snd input encUnary) 2
  have hNew := unary_add.comp ((arith_index hb hn 2).comp (fst input encUnary) |>.prod (snd input encUnary))
  have hGate := gate_conj hNew (hKill.comp (fst input encUnary)) hOld
  have hm := mapWithInput (f := fun a i => Gate.conj (monusOutWire (base a) (n a) i)
      (monusMaskWire (base a) (n a)) (rippleBitWire (base a) i)) (range.comp hn) hGate
  exact listAppend' hFirst (cons' (gate_inv hKill hBorrow) hm)

theorem widthCircuit_polytime {base n : α → ℕ} {key : α → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hn : ComputableTidilyInPolyTime n input encUnary)
    (hk : ComputableTidilyInPolyTime (fun a : α × ℕ => key a.1 a.2)
      (encPair input encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => widthCircuit (base a) (n a) (key a))
      input (encList gateEnc) := by
  have hEnd := unary_add.comp (hb.prod hn)
  have ho := fst input encUnary
  have hi := snd input encUnary
  have hWire := unary_add.comp ((hb.comp ho).prod hi)
  have hNext := unary_add.comp ((hb.comp ho).prod (unary_add.comp (hi.prod (const 1))))
  have hGate := gate_disj hWire hk hNext
  exact cons' (gate_pin false hEnd)
    (mapWithInput (f := fun a i => Gate.disj (widthFlagWire (base a) i)
      (key a i) (widthFlagWire (base a) (i+1))) (range.comp hn) hGate)

end Build

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime

private theorem filter_range_lt (m n : ℕ) (h : m ≤ n) :
    (List.range n).filter (fun i => decide (i < m)) = List.range m := by
  induction n with
  | zero =>
    have h0 : m=0 := by omega
    subst m
    rfl
  | succ n ih =>
    by_cases hr : m ≤ n
    · rw [List.range_succ,List.filter_append,ih hr]
      simp [show ¬ n < m by omega]
    · have e : m=n+1 := by omega
      subst m
      apply List.filter_eq_self.mpr
      intro i hi
      exact decide_eq_true (List.mem_range.mp hi)

theorem unary_div_poly :
    ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 / p.2)
      (encPair encUnary encUnary) encUnary := by
  let encP := encPair encUnary encUnary
  have hX := fst encUnary encUnary
  have hY := snd encUnary encUnary
  have hP := fst encP encUnary
  have hI := snd encP encUnary
  have hProd := unary_mul.comp ((unary_add.comp (hI.prod (const 1))).prod (hY.comp hP))
  have hPred : ComputableTidilyInPolyTime
      (fun p : (ℕ × ℕ) × ℕ => decide ((p.2+1)*p.1.2 ≤ p.1.1))
      (encPair encP encUnary) encBool := unary_le' hProd (hX.comp hP)
  have hData := filterWithInput (test := fun p i => decide ((i+1)*p.2 ≤ p.1)) (range.comp hX) hPred
  have hLen := (length encUnary).comp hData
  have h := (unary_lt' (const 0) hY).ite' hLen (const 0)
  convert h using 1
  funext p
  simp only [Function.comp_apply,decide_eq_true_eq]
  by_cases hz : 0 < p.2
  · rw [if_pos hz]
    have hEq : (fun i => decide ((i+1)*p.2 ≤ p.1)) = (fun i => decide (i < p.1/p.2)) := by
      funext i
      have he : (i+1)*p.2 ≤ p.1 ↔ i < p.1/p.2 := by
        rw [← Nat.le_div_iff_mul_le hz]
        omega
      simp [he]
    rw [hEq,filter_range_lt _ _ (Nat.div_le_self _ _),List.length_range]
  · have hzero : p.2 = 0 := by omega
    simp [hzero]

theorem unary_mod_poly :
    ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 % p.2)
      (encPair encUnary encUnary) encUnary := by
  have hX := fst encUnary encUnary
  have hY := snd encUnary encUnary
  have hProd := unary_mul.comp (hY.prod unary_div_poly)
  have h := unary_sub.comp (hX.prod hProd)
  simpa only [Function.comp_def,Nat.mod_eq_sub_mul_div] using h


theorem unary_size_poly : ComputableTidilyInPolyTime Nat.size encUnary encUnary := by
  rw [show Nat.size = (fun a : ℕ => a.bits.length) from (funext Nat.size_eq_bits_len).symm]
  exact length_bits_comp (natBits.comp unary_to_binary)

theorem unary_pow2_of_bound {α : Type} {input : α ↪ List Bool} {k bound : α → ℕ}
    (hk : ComputableTidilyInPolyTime k input encUnary)
    (hb : ComputableTidilyInPolyTime bound input encUnary)
    (hle : ∀ a, 2^(k a) ≤ bound a) :
    ComputableTidilyInPolyTime (fun a => 2^(k a)) input encUnary := by
  have h := ComputableInPolyTime.binary_min_unary' hb.computableInPolyTime
    (binary_two_pow.comp hk).computableInPolyTime
  simpa [min_eq_right (hle _)] using h.tidy

theorem pow2_size_le (a : ℕ) : 2^(a.size) ≤ 2*a+1 := by
  by_cases h0 : a=0
  · simp [h0]
  · have hp : 0 < a.size := Nat.size_pos.mpr (Nat.pos_of_ne_zero h0)
    have hd : a.size-1 < a.size := by omega
    have hL := Nat.lt_size.mp hd
    calc
      2^a.size = 2^(a.size-1)*2 := by conv_lhs => rw [show a.size=(a.size-1)+1 by omega]; rw [Nat.pow_succ]
      _ ≤ 2*a+1 := by omega

theorem unary_pow2_size_poly :
    ComputableTidilyInPolyTime (fun a : ℕ => 2^(a.size)) encUnary encUnary := by
  have hBound := unary_add.comp
    ((unary_mul.comp ((const 2).prod (id' (encIn := encUnary)))).prod (const 1))
  exact unary_pow2_of_bound unary_size_poly hBound pow2_size_le

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson
open Turing.MultiTapeTM ComputableTidilyInPolyTime

private abbrev wordsEnc : List (List Bool) ↪ List Bool := encList encBits

/-- Read the construction dimensions from its two unary header words. -/
def inputParam (i : ℕ) (ws : List (List Bool)) : ℕ := (ws.getD i []).length

theorem inputParam_poly (i : ℕ) :
    ComputableTidilyInPolyTime (inputParam i) wordsEnc encUnary := by
  exact (length_bits).comp ((listGetD (encA := encBits) []).comp
    ((id' (encIn := wordsEnc)).prod (const i)))

@[simp] theorem inputParam_zero (prog : List Instr) (n t : ℕ) :
    inputParam 0 (RobsonCNF.robsonWords (prog,n,t)) = n := by
  simp [inputParam,RobsonCNF.robsonWords,unaryWord]

@[simp] theorem inputParam_one (prog : List Instr) (n t : ℕ) :
    inputParam 1 (RobsonCNF.robsonWords (prog,n,t)) = t := by
  simp [inputParam,RobsonCNF.robsonWords,unaryWord]

theorem layoutHeight_poly : ComputableTidilyInPolyTime layoutHeight encUnary encUnary := by
  have hNat : ComputableTidilyInPolyTime (fun t : ℕ => 4*(9*t+1)-1) encUnary encUnary := by
    fun_prop
  exact ComputableInPolyTime.binary_size.tidy.comp (unary_to_binary.comp hNat)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson
open Turing.MultiTapeTM ComputableTidilyInPolyTime

private theorem twoPow_cap_poly {α : Type} {e : α ↪ List Bool} {f g : α → ℕ}
    (hf : ComputableTidilyInPolyTime f e encUnary)
    (hg : ComputableTidilyInPolyTime g e encUnary) :
    ComputableTidilyInPolyTime (fun x => min (g x) (2^(f x))) e encUnary :=
  (ComputableInPolyTime.binary_min_unary' hg.computableInPolyTime
    (binary_two_pow.comp hf).computableInPolyTime).tidy

private theorem layoutHorizon_bound (t : ℕ) : layoutHorizon t ≤ 8*(9*t+1) := by
  have hc : 0 < 4*(9*t+1) := by omega
  change 2^(4*(9*t+1)-1).size ≤ 8*(9*t+1)
  generalize hcost : 4*(9*t+1) = c at hc ⊢
  have hb : 2^(c-1).size ≤ 2*c := by
    cases h : (c-1).size with
    | zero => simp; omega
    | succ j =>
      have hj : j < (c-1).size := by omega
      have hlt := Nat.lt_size.mp hj
      rw [pow_succ]
      omega
  omega

theorem layoutHorizon_poly : ComputableTidilyInPolyTime layoutHorizon encUnary encUnary := by
  have hb : ComputableTidilyInPolyTime (fun t : ℕ => 8*(9*t+1)) encUnary encUnary := by fun_prop
  have h := twoPow_cap_poly layoutHeight_poly hb
  have he : (fun t => min (8*(9*t+1)) (2^layoutHeight t)) = layoutHorizon := by
    funext t; exact min_eq_right (layoutHorizon_bound t)
  rwa [he] at h

private theorem period_poly :
    ComputableTidilyInPolyTime (fun p : ℕ × ℕ => 2^(min p.2 (layoutHeight p.1)))
      (encPair encUnary encUnary) encUnary := by
  have hp : ComputableTidilyInPolyTime (fun p : ℕ × ℕ => min p.2 (layoutHeight p.1))
      (encPair encUnary encUnary) encUnary := unary_min.comp
    ((snd encUnary encUnary).prod (layoutHeight_poly.comp (fst encUnary encUnary)))
  have hh := layoutHorizon_poly.comp (fst encUnary encUnary)
  have h := twoPow_cap_poly hp hh
  have he : ∀ p : ℕ × ℕ, 2^(min p.2 (layoutHeight p.1)) ≤ layoutHorizon p.1 := by
    intro p
    exact Nat.pow_le_pow_right (by decide) (min_le_right _ _)
  simpa [min_eq_right (he _)] using h

private theorem unaryMod_poly :
    ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 % p.2)
      (encPair encUnary encUnary) encUnary := by
  have ha := fst encUnary encUnary
  have hb := snd encUnary encUnary
  have h := ComputableInPolyTime.binary_min_unary' ha.computableInPolyTime
    (binary_mod' (unary_to_binary.comp ha) (unary_to_binary.comp hb)).computableInPolyTime
  simpa [min_eq_right (Nat.mod_le _ _)] using h.tidy

private def rowEnc : (ℕ × ℕ) ↪ List Bool := encPair encUnary encUnary

private def slotsAt (p : ℕ × ℕ) : List (ℕ × ℕ) :=
  (((List.range (layoutHeight p.1+1)).filter fun j => p.2 % 2^j = 0).map (p.2,·))

private theorem slotsAt_poly : ComputableTidilyInPolyTime slotsAt rowEnc (encList rowEnc) := by
  have ht : ComputableTidilyInPolyTime Prod.fst rowEnc encUnary := fst encUnary encUnary
  have ha : ComputableTidilyInPolyTime Prod.snd rowEnc encUnary := snd encUnary encUnary
  have hP := fst rowEnc encUnary
  have hJ := snd rowEnc encUnary
  have hR := range.comp (unary_add.comp ((layoutHeight_poly.comp ht).prod (const 1)))
  have hPer := period_poly.comp ((ht.comp hP).prod hJ)
  have hTest := unary_beq (unaryMod_poly.comp ((ha.comp hP).prod hPer)) (const 0)
  have hF := filterWithInput
    (test := fun (p : ℕ × ℕ) j => p.2 % 2^(min j (layoutHeight p.1)) == 0) hR hTest
  have hOut := mapWithInput (f := fun (p : ℕ × ℕ) j => (p.2,j)) hF
    ((ha.comp hP).prod hJ)
  convert hOut using 1
  · funext p
    unfold slotsAt
    congr 1
    apply List.filter_congr
    intro j hj
    have hle : j ≤ layoutHeight p.1 := Nat.lt_succ_iff.mp (List.mem_range.mp hj)
    rw [min_eq_left hle]
    exact Bool.eq_iff_iff.mpr (by simp only [decide_eq_true_eq,beq_iff_eq])
  · rfl

theorem layoutSlots_poly : ComputableTidilyInPolyTime layoutSlots encUnary (encList rowEnc) := by
  exact flatMapWithInput (range.comp layoutHorizon_poly) slotsAt_poly

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- A raw operand word taken from a physical packet input lane. Empty lanes
supply zero here and are still checked by the full row-list equality. -/
def Packet.operand (p : Packet) (i : ℕ) : ℕ :=
  (p.accesses[i]?.map MemoryAccess.value).getD 0

/-- Check a packet against one fixed decoded instruction. The displayed row equalities
check all presence and write flags, addresses, input symbols, and value words. -/
def InstrPacket (op : Instr) (pc next : ℕ) (p : Packet) : Prop :=
  let a := p.operand 0
  let b := p.operand 1
  match op with
  | .loadc v =>
      next = pc+1 ∧ p = ⟨none,[.write 0 v],1+bitLen v⟩
  | .load j =>
      next = pc+1 ∧ p = ⟨none,[.read j a,.write 0 a],1+bitLen j+bitLen a⟩
  | .loadi j =>
      next = pc+1 ∧ p = ⟨none,[.read j a,.read a b,.write 0 b],1+bitLen j+bitLen a+bitLen b⟩
  | .store j =>
      next = pc+1 ∧ p = ⟨none,[.read 0 a,.write j a],1+bitLen j+bitLen a⟩
  | .storei j =>
      next = pc+1 ∧ p = ⟨none,[.read j a,.read 0 b,.write a b],1+bitLen j+bitLen a+bitLen b⟩
  | .add j =>
      next = pc+1 ∧ p = ⟨none,[.read 0 a,.read j b,.write 0 (a+b)],1+bitLen j+bitLen a+bitLen b⟩
  | .sub j =>
      next = pc+1 ∧ p = ⟨none,[.read 0 a,.read j b,.write 0 (a-b)],1+bitLen j+bitLen a+bitLen b⟩
  | .read =>
      let v := p.input.getD 0
      next = pc+1 ∧ p = ⟨some v,[.write 0 v],1+bitLen v⟩
  | .jump l =>
      next = l ∧ p = ⟨none,[],1+bitLen l⟩
  | .jzero l =>
      if a=0 then next = l ∧ p = ⟨none,[.read 0 0],1+bitLen l+bitLen 0⟩
      else next = pc+1 ∧ p = ⟨none,[.read 0 a],1+bitLen l+bitLen a⟩
  | .njump l r =>
      (next = l ∨ next = r) ∧ p = ⟨none,[],1+bitLen l+bitLen r⟩
  | .halt => False

theorem PacketStep.localInstr {prog : List Instr} {pc next : ℕ} {p : Packet}
    (s : PacketStep prog pc next p) :
    ∃ op, prog[pc]? = some op ∧ InstrPacket op pc next p := by
  cases s
  all_goals refine ⟨_,‹_›,?_⟩
  all_goals simp [InstrPacket,Packet.operand,MemoryAccess.read,MemoryAccess.write, *]

theorem InstrPacket.packetStep {prog : List Instr} {pc next : ℕ} {p : Packet} {op : Instr}
    (hAt : prog[pc]? = some op) (h : InstrPacket op pc next p) :
    PacketStep prog pc next p := by
  cases op with
  | loadc v =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .loadc hAt
  | load j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .load hAt
  | loadi j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .loadi hAt
  | store j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .store hAt
  | storei j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .storei hAt
  | add j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .add hAt
  | sub j =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .sub hAt
  | read =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .read hAt
  | jump l =>
    obtain ⟨hN,hP⟩ := h
    rw [hN,hP]
    exact .jump hAt
  | jzero l =>
    by_cases ha : p.operand 0 = 0
    · obtain ⟨hN,hP⟩ := by simpa only [InstrPacket,ha,if_true] using h
      rw [hN,hP]
      exact .jzeroTaken hAt
    · obtain ⟨hN,hP⟩ := by simpa only [InstrPacket,ha,if_false] using h
      rw [hN,hP]
      exact .jzeroNotTaken hAt ha
  | njump l r =>
    obtain ⟨hN,hP⟩ := h
    rcases hN with hN|hN
    · rw [hN,hP]
      exact .njumpLeft hAt
    · rw [hN,hP]
      exact .njumpRight hAt
  | halt => contradiction

theorem packetStep_iff_instrPacket {prog : List Instr} {pc next : ℕ} {p : Packet} {op : Instr}
    (hAt : prog[pc]? = some op) :
    PacketStep prog pc next p ↔ InstrPacket op pc next p := by
  constructor
  · intro h
    obtain ⟨op',hp,hs⟩ := h.localInstr
    have he := Option.some.inj (hp.symm.trans hAt)
    exact he ▸ hs
  · exact InstrPacket.packetStep hAt

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

abbrev PortView := Option ℕ × List MemoryAccess

/-- Missing tokens are the idle fixed slots. The extra control value `none`
denotes a halted run, and can only be followed by idle entries. -/
inductive SlotMove (prog : List Instr) :
    Option PortView → Option ℕ → Option ℕ → ℕ → Prop
  | idle (pc : Option ℕ) : SlotMove prog none pc pc 0
  | execute {pc next : ℕ} {p : Packet} :
      PacketStep prog pc next p → SlotMove prog (some p.ports) (some pc) (some next) p.cost
  | halt {pc : ℕ} : prog[pc]? = some .halt →
      SlotMove prog (some finalPacket.ports) (some pc) none (1+bitLen 1)

inductive SlotScan (prog : List Instr) :
    List (Option PortView) → Option ℕ → Option ℕ → ℕ → Prop
  | nil (pc : Option ℕ) : SlotScan prog [] pc pc 0
  | cons {v : Option PortView} {vs : List (Option PortView)} {pc next last : Option ℕ} {c k : ℕ} :
      SlotMove prog v pc next c → SlotScan prog vs next last k →
      SlotScan prog (v::vs) pc last (c+k)

theorem SlotMove.finished {prog : List Instr} {v : Option PortView} {pc : Option ℕ} {k : ℕ}
    (h : SlotMove prog v none pc k) : v = none ∧ pc = none ∧ k = 0 := by
  cases h
  exact ⟨rfl,rfl,rfl⟩

theorem SlotScan.finished {prog : List Instr} {vs : List (Option PortView)} {pc : Option ℕ} {k : ℕ}
    (h : SlotScan prog vs none pc k) :
    vs.filterMap id = [] ∧ pc = none ∧ k = 0 := by
  have aux (start : Option ℕ) (h' : SlotScan prog vs start pc k) :
      start = none → vs.filterMap id = [] ∧ pc = none ∧ k = 0 := by
    clear h
    induction h' with
    | nil start => simp
    | @cons v vs st next last c rem hMove hTail ih =>
      intro hStart
      subst st
      obtain ⟨rfl,rfl,rfl⟩ := hMove.finished
      simpa using ih rfl
  exact aux none h rfl

theorem SlotScan.toPackets {prog : List Instr} {vs : List (Option PortView)} {pc k : ℕ}
    (h : SlotScan prog vs (some pc) none k) :
    ∃ fin elapsed ps, PacketPath prog pc fin ps elapsed ∧ prog[fin]? = some .halt ∧
      k = elapsed+(1+bitLen 1) ∧ vs.filterMap id = (ps++[finalPacket]).map Packet.ports := by
  have aux (start finish : Option ℕ) (h' : SlotScan prog vs start finish k) :
      ∀ st, start = some st → finish = none →
        ∃ fin elapsed ps, PacketPath prog st fin ps elapsed ∧ prog[fin]? = some .halt ∧
          k = elapsed+(1+bitLen 1) ∧ vs.filterMap id = (ps++[finalPacket]).map Packet.ports := by
    clear h
    induction h' with
    | nil start =>
      intro st h1 h2
      have hbad : none = some st := h2.symm.trans h1
      contradiction
    | @cons v vs start next finish c k hMove hTail ih =>
      intro st hStart hFinish
      subst start finish
      cases hMove with
      | idle =>
        simpa using ih st rfl rfl
      | @execute _ nx p hStep =>
        obtain ⟨fin,elapsed,ps,hP,hH,hk,hW⟩ := ih nx rfl rfl
        exact ⟨fin,p.cost+elapsed,p::ps,.cons hStep hP,hH,by omega,
          by exact congrArg (List.cons p.ports) hW⟩
      | halt hH =>
        obtain ⟨hv,_,hk⟩ := hTail.finished
        refine ⟨st,0,[],.nil st,hH,by omega,?_⟩
        change finalPacket.ports :: vs.filterMap id = [finalPacket.ports]
        rw [hv]
  exact aux _ _ h pc rfl rfl

theorem SlotScan.insertIdle {prog : List Instr} {vs : List (Option PortView)} {pc pc' : Option ℕ}
    {k : ℕ} (h : SlotScan prog ((vs.filterMap id).map some) pc pc' k) :
    SlotScan prog vs pc pc' k := by
  induction vs generalizing pc pc' k with
  | nil => exact h
  | cons v vs ih =>
    cases v with
    | none =>
      have hh : SlotScan prog ((vs.filterMap id).map some) pc pc' k := h
      simpa only [Nat.zero_add] using
        (SlotScan.cons (v:=none) (.idle pc) (ih hh))
    | some a =>
      change SlotScan prog (some a::(vs.filterMap id).map some) pc pc' k at h
      cases h
      rename_i hm ht
      exact .cons hm (ih ht)

theorem PacketPath.toLiveScan {prog : List Instr} {pc fin k : ℕ} {ps : List Packet}
    (h : PacketPath prog pc fin ps k) (hh : prog[fin]? = some .halt) :
    SlotScan prog ((ps++[finalPacket]).map (some ∘ Packet.ports)) (some pc) none (k+(1+bitLen 1)) := by
  induction h with
  | nil => simpa using SlotScan.cons (.halt hh) (.nil none)
  | @cons pc nx fin elapsed p ps hMove hPath ih =>
    have hs := SlotScan.cons (.execute hMove) (ih hh)
    simpa only [List.cons_append,List.map_cons,Function.comp_apply,Nat.add_assoc] using hs

theorem SlottedPath.tokens_live (α : Assignment) (n t : ℕ) :
    let tokens := (layoutSlots t).map (fun s => if slotLive α n t s then some (slotView α n t s) else none)
    tokens.filterMap id = (liveSlots α n t).map (slotView α n t) := by
  unfold liveSlots
  generalize layoutSlots t = xs
  induction xs with
  | nil => rfl
  | cons s xs ih =>
    dsimp only at ih
    cases h : slotLive α n t s <;>
      simp only [List.map_cons,List.filterMap_cons,List.filter_cons,h,Bool.false_eq_true,ite_false,ite_true,ih] <;> rfl

def slotTokens (α : Assignment) (n t : ℕ) : List (Option PortView) :=
  (layoutSlots t).map fun s => if slotLive α n t s then some (slotView α n t s) else none

theorem hasSlottedPath_iff_scan (prog : List Instr) (n t : ℕ) (α : Assignment) :
    HasSlottedPath prog n t α ↔
      ∃ k ≤ t, SlotScan prog (slotTokens α n t) (some 0) none k := by
  constructor
  · rintro ⟨fin,k,ps,hPath,hH,hk,hPorts⟩
    refine ⟨_,hk,SlotScan.insertIdle ?_⟩
    have hTok : (slotTokens α n t).filterMap id = (liveSlots α n t).map (slotView α n t) :=
      SlottedPath.tokens_live α n t
    rw [hTok,← hPorts,List.map_map]
    exact hPath.toLiveScan hH
  · rintro ⟨k,hk,hScan⟩
    obtain ⟨fin,elapsed,ps,hp,hh,he,hs⟩ := hScan.toPackets
    refine ⟨fin,elapsed,ps,hp,hh,by omega,?_⟩
    exact hs.symm.trans (SlottedPath.tokens_live α n t)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

structure ScanState where
  control : Option ℕ
  clock : ℕ

/-- One pair of neighboring control and clock words on the fixed slot array. -/
def SlotAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) : Prop :=
  ∃ c, SlotMove prog v u.control w.control c ∧ w.clock = u.clock+c

def ScanState.inControlRange (prog : List Instr) (s : ScanState) : Prop :=
  ∀ j, s.control = some j → j < prog.length

theorem SlotMove.controlRange {prog : List Instr} {v : Option PortView} {pc next : Option ℕ}
    {c : ℕ} (h : SlotMove prog v pc next c)
    (hNext : ∀ j, next = some j → j < prog.length) :
    ∀ j, pc = some j → j < prog.length := by
  cases h with
  | idle => exact hNext
  | execute hStep =>
    obtain ⟨op,hi,_⟩ := hStep.localInstr
    intro j hj
    obtain rfl := Option.some.inj hj
    exact (List.getElem?_eq_some_iff.mp hi).choose
  | halt hH =>
    intro j hj
    obtain rfl := Option.some.inj hj
    exact (List.getElem?_eq_some_iff.mp hH).choose

theorem SlotScan.toIndexed {prog : List Instr} {tokens : List (Option PortView)}
    {pc finish : Option ℕ} {k : ℕ}
    (h : SlotScan prog tokens pc finish k) (m t : ℕ) (hb : m+k ≤ t)
    (hFin : ∀ j, finish = some j → j < prog.length) :
    ∃ states : Fin (tokens.length+1) → ScanState,
      states 0 = ⟨pc,m⟩ ∧ states (Fin.last tokens.length) = ⟨finish,m+k⟩ ∧
      (∀ i, (states i).clock ≤ t ∧ (states i).inControlRange prog) ∧
      ∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ) := by
  induction h generalizing m with
  | nil pc =>
    refine ⟨fun _ => ⟨pc,m⟩,rfl,?_,fun _ => ⟨by omega,hFin⟩,fun i => Fin.elim0 i⟩
    simp
  | @cons v vs pc next finish c k hv hs ih =>
    obtain ⟨states,hFirst,hLast,hBound,hMove⟩ := ih (m+c) (by omega) hFin
    let ss : Fin ((v::vs).length+1) → ScanState := Fin.cons ⟨pc,m⟩ states
    have hF : ss 0 = ⟨pc,m⟩ := Fin.cons_zero ..
    have hSucc (i : Fin (vs.length+1)) : ss i.succ = states i := Fin.cons_succ ..
    refine ⟨ss,hF,?_,?_,?_⟩
    · rw [show Fin.last (v::vs).length = (Fin.last vs.length).succ from rfl,hSucc,hLast]
      simp only [Nat.add_assoc]
    · intro i
      refine Fin.cases ?_ (fun j => ?_) i
      · rw [hF]
        have hm : m ≤ t := by omega
        refine ⟨hm, hv.controlRange ?_⟩
        have hn := (hBound 0).2
        rw [hFirst] at hn
        exact hn
      · rw [hSucc]
        exact hBound j
    · intro i
      refine Fin.cases ?_ (fun j => ?_) i
      · change SlotAdvance prog v (ss 0) (ss (Fin.succ (0 : Fin (vs.length+1))))
        rw [hF,hSucc,hFirst]
        exact ⟨c,hv,rfl⟩
      · change SlotAdvance prog vs[j] (ss (Fin.succ j.castSucc)) (ss (Fin.succ j.succ))
        rw [hSucc,hSucc]
        exact hMove j

theorem SlotScan.ofIndexed {prog : List Instr} (tokens : List (Option PortView))
    (states : Fin (tokens.length+1) → ScanState)
    (h : ∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ)) :
    ∃ k, SlotScan prog tokens (states 0).control (states (Fin.last tokens.length)).control k ∧
      (states (Fin.last tokens.length)).clock = (states 0).clock+k := by
  induction tokens with
  | nil =>
    refine ⟨0,?_,by rfl⟩
    exact .nil _
  | cons v vs ih =>
    let tail : Fin (vs.length+1) → ScanState := Fin.tail states
    have hTail (i : Fin vs.length) : SlotAdvance prog vs[i] (tail i.castSucc) (tail i.succ) :=
      h i.succ
    obtain ⟨k,hs,hclock⟩ := ih tail hTail
    obtain ⟨c,hv,he⟩ := h 0
    refine ⟨c+k, .cons hv hs,?_⟩
    change (states (Fin.last (v::vs).length)).clock = (states (Fin.succ (0 : Fin (vs.length+1)))).clock+k at hclock
    change (states (Fin.succ (0 : Fin (vs.length+1)))).clock = (states 0).clock+c at he
    omega

/-- The whole control/clock checker is a fixed adjacent-state relation. Every accepting
control word ranges over the program indices plus the unique halted sentinel. -/
theorem hasSlottedPath_iff_indexed (prog : List Instr) (n t : ℕ) (α : Assignment) :
    HasSlottedPath prog n t α ↔
      let tokens := slotTokens α n t
      ∃ states : Fin (tokens.length+1) → ScanState,
        states 0 = ⟨some 0,0⟩ ∧ (states (Fin.last tokens.length)).control = none ∧
        (∀ i, (states i).clock ≤ t ∧ (states i).inControlRange prog) ∧
        ∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ) := by
  rw [hasSlottedPath_iff_scan]
  dsimp only
  constructor
  · rintro ⟨k,hk,hs⟩
    obtain ⟨states,hStart,hEnd,hBounds,hSteps⟩ := hs.toIndexed 0 t (by omega)
      (fun _ h => by contradiction)
    exact ⟨states,hStart,congrArg ScanState.control hEnd,hBounds,hSteps⟩
  · rintro ⟨states,hStart,hEnd,hBounds,hSteps⟩
    obtain ⟨k,hs,hClock⟩ := SlotScan.ofIndexed _ _ hSteps
    refine ⟨k,?_,?_⟩
    · have hTop := (hBounds (Fin.last _)).1
      rw [hStart] at hClock
      change (states (Fin.last (slotTokens α n t).length)).clock = 0+k at hClock
      omega
    · rw [hStart,hEnd] at hs
      exact hs

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- The transition at one scheduled slot can be checked directly on its raw
ports and neighboring state words, without quantifying over machine packets. -/
def LocalAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) : Prop :=
  match v,u.control,w.control with
  | none,_,_ => u = w
  | some x,some pc,some next =>
    u.clock ≤ w.clock ∧ ∃ op, prog[pc]? = some op ∧
      InstrPacket op pc next ⟨x.1,x.2,w.clock-u.clock⟩
  | some x,some pc,none =>
    prog[pc]? = some .halt ∧ x = finalPacket.ports ∧ w.clock = u.clock+(1+bitLen 1)
  | some _,none,_ => False

theorem slotAdvance_iff_localAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) :
    SlotAdvance prog v u w ↔ LocalAdvance prog v u w := by
  rcases u with ⟨pc,m⟩
  rcases w with ⟨next,k⟩
  constructor
  · rintro ⟨c,h,hClock⟩
    change k = m+c at hClock
    subst k
    cases h with
    | idle => rfl
    | @execute pc next p hStep =>
      have hPacket : (⟨p.ports.1,p.ports.2,m+p.cost-m⟩ : Packet) = p := by
        simp only [Nat.add_sub_cancel_left]
        cases p
        rfl
      change m ≤ m+p.cost ∧ ∃ op, prog[pc]? = some op ∧ InstrPacket op pc next
        ⟨p.ports.1,p.ports.2,m+p.cost-m⟩
      rw [hPacket]
      exact ⟨Nat.le_add_right _ _,hStep.localInstr⟩
    | halt hh => exact ⟨hh,rfl,rfl⟩
  · intro h
    cases v with
    | none =>
      have he : (⟨pc,m⟩ : ScanState) = ⟨next,k⟩ := h
      cases he
      exact ⟨0,.idle pc,rfl⟩
    | some x =>
      cases pc with
      | none => contradiction
      | some pc =>
        cases next with
        | none =>
          obtain ⟨hh,hv,hc⟩ := h
          subst x
          exact ⟨_,.halt hh,hc⟩
        | some next =>
          obtain ⟨hmon,op,hOp,hRule⟩ := h
          have hStep : PacketStep prog pc next ⟨x.1,x.2,k-m⟩ := hRule.packetStep hOp
          exact ⟨k-m,.execute hStep,by exact (Nat.add_sub_of_le (show m ≤ k from hmon)).symm⟩

end CNFEncComplexity.Robson

namespace CNFEncComplexity.RobsonCNF

open CookLevin

def widthChainCount (h j : ℕ) : ℕ := 2^(h-j)
def widthChainSample (j k : ℕ) : ℕ := (k+1)*2^j-1
def widthChainWire (base h j k : ℕ) : ℕ := base+j*(2^h+1)+k

def widthChain (base h j : ℕ) (flags : ℕ → ℕ) : List Gate :=
  .pin (widthChainWire base h j 0) false ::
    (List.range (widthChainCount h j)).map (fun k => .parity
      (widthChainWire base h j (k+1)) (widthChainWire base h j k) (flags (widthChainSample j k)))

/-- Convert unary high-bit flags into the binary bit length by parity of every
second, fourth, and subsequent power-of-two spaced flag. -/
def binaryWidthCircuit (base h : ℕ) (flags : ℕ → ℕ) : List Gate :=
  (List.range (h+1)).flatMap fun j => widthChain base h j flags

def binaryWidthWire (base h j : ℕ) : ℕ :=
  widthChainWire base h j (widthChainCount h j)

theorem widthChain_sample_iff {j k len : ℕ} :
    widthChainSample j k < len ↔ k < len / 2^j := by
  have hp : 0 < (k+1)*2^j := Nat.mul_pos (by omega) (Nat.two_pow_pos _)
  unfold widthChainSample
  calc
    _ ↔ (k+1)*2^j ≤ len := by omega
    _ ↔ k+1 ≤ len/2^j := (Nat.le_div_iff_mul_le (Nat.two_pow_pos _)).symm
    _ ↔ _ := Nat.succ_le_iff

private theorem widthChain_decide_eq (j k len : ℕ) :
    decide (widthChainSample j k < len) = decide (k < len / 2^j) := by
  by_cases h : widthChainSample j k < len
  · simp [h,widthChain_sample_iff.mp h]
  · have hh : ¬ k < len / 2^j := fun h' => h (widthChain_sample_iff.mpr h')
    simp [h,hh]

private theorem widthChain_sample_lt {h j k : ℕ} (hj : j ≤ h) (hk : k < widthChainCount h j) :
    widthChainSample j k < 2^h := by
  have hDiv : (2:ℕ)^h / 2^j = widthChainCount h j := by
    rw [show (2:ℕ)^h = 2^(h-j)*2^j from (Nat.pow_sub_mul_pow 2 hj).symm,
      Nat.mul_div_cancel _ (Nat.two_pow_pos _)]
    rfl
  exact widthChain_sample_iff.mpr (hDiv.symm ▸ hk)

private theorem widthChain_parity (k q : ℕ) :
    Bool.xor ((min k q).testBit 0) (decide (k < q)) = (min (k+1) q).testBit 0 := by
  by_cases h : k < q
  · rw [min_eq_left h.le,min_eq_left (by omega),show decide (k < q) = true from by simp [h],
      Nat.testBit_zero,Nat.testBit_zero]
    simp only [Bool.xor_true]
    have hh : (k+1)%2=1 ↔ ¬k%2=1 := by omega
    by_cases ho : k%2=1
    · simp [ho,show ¬(k+1)%2=1 from fun hx => hh.mp hx ho]
    · simp [ho,hh.mpr ho]
  · rw [min_eq_right (by omega),min_eq_right (by omega),show decide (k < q) = false from by simp [h]]
    cases (q.testBit 0) <;> rfl

theorem binaryWidthCircuit_exact (base h : ℕ) (flags : ℕ → ℕ) (α : Assignment)
    {len : ℕ} (hl : len ≤ 2^h)
    (hf : ∀ i < 2^h, α (flags i) = decide (i < len))
    (hc : ∀ g ∈ binaryWidthCircuit base h flags, g.Holds α)
    {j : ℕ} (hj : j ≤ h) :
    α (binaryWidthWire base h j) = len.testBit j := by
  have hChain : ∀ g ∈ widthChain base h j flags, g.Holds α := by
    intro g hg
    apply hc
    exact List.mem_flatMap.mpr ⟨j,List.mem_range.mpr (by omega),hg⟩
  let count := widthChainCount h j
  let q := len / 2^j
  have hValue (k : ℕ) (hk : k ≤ count) :
      α (widthChainWire base h j k) = (min k q).testBit 0 := by
    induction k with
    | zero =>
      have hp := hChain (.pin (widthChainWire base h j 0) false) (by simp [widthChain])
      change α (widthChainWire base h j 0) = false at hp
      simpa only [Nat.zero_min,Nat.testBit_zero,Nat.zero_mod,zero_ne_one,decide_false] using hp
    | succ k ih =>
      have hk' : k < widthChainCount h j := by exact hk
      have hp := hChain (.parity (widthChainWire base h j (k+1))
        (widthChainWire base h j k) (flags (widthChainSample j k)))
        (List.mem_cons.mpr (.inr (List.mem_map.mpr ⟨k,List.mem_range.mpr hk',rfl⟩)))
      change α (widthChainWire base h j (k+1)) =
        Bool.xor (α (widthChainWire base h j k)) (α (flags (widthChainSample j k))) at hp
      rw [hp,ih hk'.le,hf _ (widthChain_sample_lt hj hk')]
      have hs : decide (widthChainSample j k < len) = decide (k < q) :=
        widthChain_decide_eq _ _ _
      rw [hs,widthChain_parity]
  have hQ : q ≤ count := by
    have hProd : count*2^j = 2^h := Nat.pow_sub_mul_pow 2 hj
    have hlt : len < (count+1)*2^j := by
      rw [Nat.add_mul,Nat.one_mul,hProd]
      have hp := Nat.two_pow_pos j
      omega
    exact Nat.le_of_lt_succ ((Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).2 hlt)
  unfold binaryWidthWire
  rw [hValue count le_rfl,min_eq_right hQ,Nat.testBit_zero,Nat.testBit_eq_decide_div_mod_eq]

private theorem widthChain_count_sum (h : ℕ) :
    ((List.range (h+1)).map (widthChainCount h)).sum + 1 = 2*2^h := by
  induction h with
  | zero => rfl
  | succ h ih =>
    rw [List.range_succ_eq_map,List.map_cons,List.map_map,List.sum_cons]
    have hf : widthChainCount (h+1) ∘ Nat.succ = widthChainCount h := by
      funext j
      simp [widthChainCount,Function.comp_apply]
    rw [hf]
    have hp : widthChainCount (h+1) 0 = 2^h*2 := by simp [widthChainCount,pow_succ]
    rw [hp,pow_succ]
    omega

theorem length_binaryWidthCircuit (base h : ℕ) (flags : ℕ → ℕ) :
    (binaryWidthCircuit base h flags).length ≤ 3*2^h := by
  have hlen (js : List ℕ) : (js.flatMap (fun j => widthChain base h j flags)).length =
      js.length+(js.map (widthChainCount h)).sum := by
    induction js with
    | nil => rfl
    | cons j js ih => simp [widthChain]; omega
  unfold binaryWidthCircuit
  rw [hlen,List.length_range]
  have hs := widthChain_count_sum h
  have hh (x : ℕ) : x+1 ≤ (2:ℕ)^x := by
    induction x with
    | zero => decide
    | succ x ih => rw [pow_succ]; omega
  have hBound := hh h
  omega


/-- Set the running parities from the prescribed domain length, preserving all
wires outside the rectangular scratch region. -/
theorem binaryWidthCircuit_extends (base h : ℕ) (flags : ℕ → ℕ) (α : Assignment)
    {len : ℕ} (hf : ∀ i < 2^h, flags i < base ∧ α (flags i) = decide (i < len)) :
    ∃ β : Assignment,
      (∀ r, r < base ∨ base+(h+1)*(2^h+1) ≤ r → β r = α r) ∧
      ∀ g ∈ binaryWidthCircuit base h flags, g.Holds β := by
  let stride := 2^h+1
  let β : Assignment := fun r =>
    if base ≤ r ∧ r < base+(h+1)*stride then
      (min ((r-base)%stride) (len / 2^((r-base)/stride))).testBit 0
    else α r
  have hBlock {j k : ℕ} (hj : j ≤ h) (hk : k < stride) :
      β (widthChainWire base h j k) = (min k (len/2^j)).testBit 0 := by
    have hLo : j*stride ≤ j*stride+k := Nat.le_add_right _ _
    have hHi : j*stride+k < (j+1)*stride := by rw [Nat.add_mul,Nat.one_mul]; omega
    have hBound := hHi.trans_le (Nat.mul_le_mul_right stride (show j+1 ≤ h+1 from by omega))
    have he : base ≤ base+j*stride+k ∧ base+j*stride+k < base+(h+1)*stride := by omega
    have hSub : base+j*stride+k-base = j*stride+k := by omega
    have hDiv : (j*stride+k)/stride=j := Nat.div_eq_of_lt_le hLo hHi
    have hMod : (j*stride+k)%stride=k := by
      rw [Nat.add_mod,Nat.mul_mod_left,Nat.zero_add,Nat.mod_mod,Nat.mod_eq_of_lt hk]
    unfold β widthChainWire
    change (if base ≤ base+j*stride+k ∧ base+j*stride+k < base+(h+1)*stride then _ else _) = _
    rw [if_pos he,hSub,hDiv,hMod]
  have hKeep (r : ℕ) (hr : r < base ∨ base+(h+1)*stride ≤ r) : β r = α r := by
    unfold β
    exact if_neg (by omega)
  refine ⟨β,hKeep,?_⟩
  intro g hg
  obtain ⟨j,hj,hg⟩ := List.mem_flatMap.mp hg
  have jLe : j ≤ h := Nat.le_of_lt_succ (List.mem_range.mp hj)
  have hCount : widthChainCount h j ≤ 2^h := Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _)
  have hPos : 0 < stride := Nat.succ_pos _
  rcases List.mem_cons.mp hg with rfl | hg
  · change β (widthChainWire base h j 0) = false
    rw [hBlock jLe hPos]
    simp
  · obtain ⟨k,hk,rfl⟩ := List.mem_map.mp hg
    have hk' := List.mem_range.mp hk
    have hk₁ : k+1 < stride := by unfold stride; omega
    have hF := hf _ (widthChain_sample_lt jLe hk')
    change β (widthChainWire base h j (k+1)) =
      Bool.xor (β (widthChainWire base h j k)) (β (flags (widthChainSample j k)))
    rw [hBlock jLe hk₁,hBlock jLe (by omega),hKeep _ (.inl hF.1),hF.2]
    rw [widthChain_decide_eq,widthChain_parity]

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime

private theorem binaryWidthWire_poly {δ : Type} {input : δ ↪ List Bool}
    {base h j k : δ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hw : ComputableTidilyInPolyTime (fun a => 2^(h a)) input encUnary)
    (hj : ComputableTidilyInPolyTime j input encUnary)
    (hk : ComputableTidilyInPolyTime k input encUnary) :
    ComputableTidilyInPolyTime (fun a => widthChainWire (base a) (h a) (j a) (k a)) input encUnary :=
  unary_add.comp ((unary_add.comp (hb.prod
    (unary_mul.comp (hj.prod (unary_add.comp (hw.prod (const 1))))))).prod hk)

/-- Uniformly list the parity gates given a unary bound for the dyadic word width. -/
theorem binaryWidthCircuit_polytime {δ : Type} {input : δ ↪ List Bool}
    {base h : δ → ℕ} {flags : δ → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base input encUnary)
    (hh : ComputableTidilyInPolyTime h input encUnary)
    (hw : ComputableTidilyInPolyTime (fun a => 2^(h a)) input encUnary)
    (hFlags : ComputableTidilyInPolyTime (fun p : δ × ℕ => flags p.1 p.2)
      (encPair input encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => binaryWidthCircuit (base a) (h a) (flags a))
      input (encList gateEnc) := by
  let encJ := encPair input encUnary
  have hX := fst input encUnary
  have hJ := snd input encUnary
  have hH := hh.comp hX
  have hW := hw.comp hX
  have hBase := hb.comp hX
  have hDiff := unary_sub.comp (hH.prod hJ)
  have hCount : ComputableTidilyInPolyTime (fun p : δ × ℕ => widthChainCount (h p.1) p.2)
      encJ encUnary :=
    unary_pow2_of_bound hDiff hW (fun _ => Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _))
  have hMin : ComputableTidilyInPolyTime (fun p : δ × ℕ => min p.2 (h p.1)) encJ encUnary := by
    have hMin := (unary_le' hJ hH).ite' hJ hH
    refine hMin.of_enc_eq ?_
    intro p
    simp [Function.comp_apply,min_def]
  have hPow : ComputableTidilyInPolyTime (fun p : δ × ℕ => 2^(min p.2 (h p.1))) encJ encUnary :=
    unary_pow2_of_bound hMin hW (fun _ => Nat.pow_le_pow_right (by decide) (min_le_right _ _))
  have hY := fst encJ encUnary
  have hK := snd encJ encUnary
  have hKNext := unary_add.comp (hK.prod (const 1))
  have hDist := hPow.comp hY
  have hIdx := unary_sub.comp ((unary_mul.comp (hKNext.prod hDist)).prod (const 1))
  have hInp := hFlags.comp ((hX.comp hY).prod hIdx)
  have hWStart := binaryWidthWire_poly hBase hW hJ (const 0)
  have hAux := binaryWidthWire_poly (hBase.comp hY) (hW.comp hY) (hJ.comp hY) hK
  have hAuxNext := binaryWidthWire_poly (hBase.comp hY) (hW.comp hY) (hJ.comp hY) hKNext
  let step (p : δ × ℕ) (k : ℕ) := Gate.parity
    (widthChainWire (base p.1) (h p.1) p.2 (k+1)) (widthChainWire (base p.1) (h p.1) p.2 k)
    (flags p.1 (widthChainSample (min p.2 (h p.1)) k))
  have hStep : ComputableTidilyInPolyTime (fun p : (δ × ℕ) × ℕ => step p.1 p.2)
      (encPair encJ encUnary) gateEnc := gate_parity hAuxNext hAux hInp
  let chain (a : δ) (j : ℕ) := .pin (widthChainWire (base a) (h a) j 0) false ::
      (List.range (widthChainCount (h a) j)).map (step (a,j))
  have hChain : ComputableTidilyInPolyTime (fun p : δ × ℕ => chain p.1 p.2) encJ (encList gateEnc) :=
    cons' (gate_pin false hWStart) (mapWithInput (range.comp hCount) hStep)
  have hRange := range.comp (unary_add.comp (hh.prod (const 1)))
  have hAll := flatMapWithInput (f := chain) hRange hChain
  refine hAll.of_enc_eq ?_
  intro a
  apply congrArg (encList gateEnc)
  unfold binaryWidthCircuit
  apply List.flatMap_congr
  intro j hj
  have hj' : j ≤ h a := Nat.le_of_lt_succ (List.mem_range.mp hj)
  unfold chain widthChain
  congr 1
  unfold step
  simp [min_eq_left hj']

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson

open CookLevin

def ancestorAt (s : ℕ × ℕ) (j : ℕ) : ℕ × ℕ := (s.1 / 2^j * 2^j,j)

theorem ancestorAt_mem {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t)
    {j : ℕ} (hj : j ≤ layoutHeight t) : ancestorAt s j ∈ layoutSlots t := by
  rw [layout_mem]
  exact ⟨(Nat.div_mul_le_self ..).trans_lt (layout_mem.mp hs).1,hj,Nat.mul_mod_left ..⟩

private theorem aligned_floor_eq {a b j : ℕ} (hb : b % 2^j = 0) :
    a / 2^j * 2^j = b ↔ b ≤ a ∧ a < b + 2^j := by
  have hB := Nat.mod_add_div b (2^j)
  rw [hb,Nat.zero_add,Nat.mul_comm] at hB
  constructor
  · intro he
    have hA := Nat.mod_add_div a (2^j)
    rw [Nat.mul_comm,he] at hA
    have hMod := Nat.mod_lt a (Nat.two_pow_pos j)
    omega
  · rintro ⟨h₁,h₂⟩
    have hDiv : a / 2^j = b / 2^j := by
      apply Nat.div_eq_of_lt_le
      · rwa [hB]
      · rwa [Nat.add_mul,Nat.one_mul,hB]
    rwa [hDiv]

private theorem aligned_separation {a b j k : ℕ} (ha : a % 2^j = 0) (hb : b % 2^k = 0)
    (hj : j ≤ k) (hab : a < b) : a+2^j ≤ b := by
  have hB : b % 2^j = 0 :=
    Nat.dvd_iff_mod_eq_zero.mp ((Nat.pow_dvd_pow 2 hj).trans (Nat.dvd_iff_mod_eq_zero.mpr hb))
  have heA := Nat.mod_add_div a (2^j)
  have heB := Nat.mod_add_div b (2^j)
  rw [ha,Nat.zero_add] at heA
  rw [hB,Nat.zero_add] at heB
  have hIndex : a/2^j < b/2^j := Nat.lt_of_mul_lt_mul_left (by rwa [heA,heB])
  have hh := Nat.mul_le_mul_left (2^j) hIndex
  rwa [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,heA,heB] at hh

private theorem nested_aligned {t : ℕ} {s r : ℕ × ℕ}
    (hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (he : s ≠ r) (hle : s.2 ≤ r.2)
    (ho : ¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1)) :
    s.2 < r.2 ∧ r = ancestorAt s r.2 := by
  rcases s with ⟨a,j⟩
  rcases r with ⟨b,k⟩
  have hA := (layout_mem.mp hs).2.2
  have hB := (layout_mem.mp hr).2.2
  dsimp at ho hle ⊢
  have hBA : b ≤ a := by
    by_contra! h
    exact ho (.inl (aligned_separation hA hB hle h))
  have hJK : j < k := by
    by_contra! hjk
    have hEq : j=k := by omega
    subst k
    have hab : a=b := by
      by_contra! he
      have hAB : b < a := by omega
      exact ho (.inr (aligned_separation hB hA le_rfl hAB))
    exact he (by simp [hab])
  have hAB : a < b+2^k := by omega
  refine ⟨hJK,?_⟩
  exact congrArg (fun a => (a,k)) ((aligned_floor_eq hB).mpr ⟨hBA,hAB⟩).symm

theorem overlap_iff_ancestor {t : ℕ} {s r : ℕ × ℕ}
    (hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (hn : s ≠ r) :
    ¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1) ↔
      (s.2 < r.2 ∧ r = ancestorAt s r.2) ∨ (r.2 < s.2 ∧ s = ancestorAt r s.2) := by
  constructor
  · intro ho
    rcases le_total s.2 r.2 with h | h
    · exact .inl (nested_aligned hs hr hn h ho)
    · exact .inr (nested_aligned hr hs (Ne.symm hn) h (fun h' => ho h'.symm))
  · have aux {s r : ℕ × ℕ} (hr : r ∈ layoutSlots t) (he : r = ancestorAt s r.2) :
        ¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1) := by
      have hEq := (congrArg Prod.fst he).symm
      have hBounds := (aligned_floor_eq (layout_mem.mp hr).2.2).mp hEq
      have hP : 0 < 2^s.2 := Nat.two_pow_pos _
      omega
    rintro (⟨_,ho⟩|⟨_,ho⟩)
    · exact aux hr ho
    · exact fun hh => aux hs ho hh.symm

private theorem pairwise_either {δ : Type} {R : δ → δ → Prop} {xs : List δ}
    (h : xs.Pairwise R) {a b : δ} (ha : a ∈ xs) (hb : b ∈ xs) (hne : a ≠ b) :
    R a b ∨ R b a := by
  induction xs with
  | nil => contradiction
  | cons x xs ih =>
    obtain ⟨hrel,htail⟩ := List.pairwise_cons.mp h
    rcases List.mem_cons.mp ha with hA|hA <;> rcases List.mem_cons.mp hb with hB|hB
    · exact False.elim (hne (hA.trans hB.symm))
    · exact .inl (hA.symm ▸ hrel b hB)
    · exact .inr (hB.symm ▸ hrel a hA)
    · exact ih htail hA hB

private def slotOrderKey (t : ℕ) (s : ℕ × ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2

/-- In the existing start-time slot order, disjointness is equivalent to saying
that no both-active pair consists of a slot and a strict aligned ancestor. -/
theorem liveSlots_disjoint_iff (α : Assignment) (n t : ℕ) :
    (liveSlots α n t).Pairwise (fun s r => s.1+2^s.2 ≤ r.1) ↔
    ∀ s ∈ layoutSlots t, ∀ j, s.2 < j → j ≤ layoutHeight t →
      ¬(slotLive α n t s = true ∧ slotLive α n t (ancestorAt s j) = true) := by
  have hOrd : (layoutSlots t).Pairwise (fun s r => slotOrderKey t s < slotOrderKey t r) :=
    layout_sorted t
  have hOrdLive := hOrd.filter (slotLive α n t)
  have hIn (s : ℕ × ℕ) : s ∈ liveSlots α n t ↔ s ∈ layoutSlots t ∧ slotLive α n t s = true :=
    List.mem_filter
  constructor
  · intro hp s hs j hj hJ hl
    let r := ancestorAt s j
    have hr : r ∈ layoutSlots t := ancestorAt_mem hs hJ
    have hn : s ≠ r := by
      intro he
      have hSnd : s.2=j := congrArg Prod.snd he
      omega
    have h₁ := (hIn _).mpr ⟨hs,hl.1⟩
    have h₂ := (hIn _).mpr ⟨hr,hl.2⟩
    have hOv := (overlap_iff_ancestor hs hr hn).mpr (.inl ⟨hj,rfl⟩)
    exact hOv (pairwise_either hp h₁ h₂ hn)
  · intro h
    apply hOrdLive.imp_of_mem
    intro s r hs hr ho
    obtain ⟨hs,ha⟩ := (hIn _).mp hs
    obtain ⟨hr,hb⟩ := (hIn _).mp hr
    have hNot : s ≠ r := fun he => (Nat.ne_of_lt ho) (congrArg _ he)
    have hl : s.1 ≤ r.1 := by
      by_contra! hc
      have hd : (r.1+1)*(layoutHeight t+1) ≤ s.1*(layoutHeight t+1) :=
        Nat.mul_le_mul_right (layoutHeight t+1) hc
      rw [Nat.add_mul,Nat.one_mul] at hd
      have hLvl := (layout_mem.mp hr).2.1
      unfold slotOrderKey at ho
      omega
    have hDisj : s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1 := by
      by_contra hOverlap
      rcases (overlap_iff_ancestor hs hr hNot).mp hOverlap with ⟨hJ,he⟩|⟨hJ,he⟩
      · exact h _ hs _ hJ (layout_mem.mp hr).2.1 ⟨ha,he ▸ hb⟩
      · exact h _ hr _ hJ (layout_mem.mp hs).2.1 ⟨hb,he ▸ ha⟩
    rcases hDisj with hA|hB
    · exact hA
    · have hP : 0 < 2^r.2 := Nat.two_pow_pos _
      omega

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def slotGuardGates (n t : ℕ) (s : ℕ × ℕ) : List Gate :=
  ([0,3,8,13].map fun f => .assert [.Pos (port n t s 18 0),.Neg (port n t s f 0)]) ++
  (((List.range (layoutHeight t+1)).filter fun j => s.2 < j).map fun j =>
    .assert [.Neg (port n t s 18 0),.Neg (port n t (ancestorAt s j) 18 0)])

def slotShapeGates (n t : ℕ) : List Gate :=
  (layoutSlots t).flatMap (slotGuardGates n t)

theorem no_portInput_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
    portInput α n t s = none ↔ α (port n t s 0 0) = false := by
  cases he : α (port n t s 0 0) <;> simp [portInput,he]

theorem no_portMemory_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) :
    portMemory α n t s i = none ↔ α (port n t s (3+5*i) 0) = false := by
  cases he : α (port n t s (3+5*i) 0) <;> simp [portMemory,he]

theorem no_slotRows_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
    slotRows α n t s = [] ↔ ∀ i < 3, α (port n t s (3+5*i) 0) = false := by
  simp [slotRows,List.filterMap_eq_nil_iff,no_portMemory_iff]

private theorem assert_pn (α : Assignment) (p q : ℕ) :
    (Gate.assert [.Pos p,.Neg q]).Holds α ↔ (α p = false → α q = false) := by
  cases hp : α p <;> cases hq : α q <;> simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hp,hq]

private theorem assert_nn (α : Assignment) (p q : ℕ) :
    (Gate.assert [.Neg p,.Neg q]).Holds α ↔ ¬(α p = true ∧ α q = true) := by
  cases hp : α p <;> cases hq : α q <;> simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hp,hq]

private theorem slotPresence_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
    (∀ f ∈ [0,3,8,13], α (port n t s f 0) = false) ↔
      portInput α n t s = none ∧ slotRows α n t s = [] := by
  rw [no_portInput_iff,no_slotRows_iff]
  constructor
  · intro h
    refine ⟨h 0 (by simp),?_⟩
    intro i hi
    rcases (show i = 0 ∨ i = 1 ∨ i = 2 by omega) with rfl|rfl|rfl
    all_goals apply h; decide
  · rintro ⟨hInput,hRows⟩ f hf
    simp only [List.mem_cons,List.not_mem_nil,or_false] at hf
    rcases hf with rfl|rfl|rfl|rfl
    · exact hInput
    · exact hRows 0 (by decide)
    · exact hRows 1 (by decide)
    · exact hRows 2 (by decide)

theorem slotShapeGates_exact (α : Assignment) (n t : ℕ) :
    (∀ g ∈ slotShapeGates n t, g.Holds α) ↔ SlotsWellFormed α n t := by
  simp only [slotShapeGates,slotGuardGates,List.forall_mem_flatMap,List.forall_mem_append,
    List.forall_mem_map,assert_pn,assert_nn,List.mem_filter,List.mem_range,decide_eq_true_eq]
  rw [SlotsWellFormed,liveSlots_disjoint_iff]
  constructor
  · intro h
    refine ⟨?_,?_⟩
    · intro s hs j hSmall hLarge
      exact (h s hs).2 j ⟨Nat.lt_succ_of_le hLarge,hSmall⟩
    · intro s hs hOff
      exact (slotPresence_iff α n t s).mp (fun f hf => (h s hs).1 f hf hOff)
  · rintro ⟨hDisj,hOff⟩ s hs
    refine ⟨?_,?_⟩
    · intro f hf he
      exact (slotPresence_iff α n t s).mpr (hOff s hs he) f hf
    · intro j hj
      exact hDisj s hs j hj.2 (Nat.le_of_lt_succ hj.1)

theorem slotShapeGates_shared {n t : ℕ} {g : Gate} (hg : g ∈ slotShapeGates n t)
    {r : ℕ} (hr : r ∈ Gate.names g) : r < sharedLimit n t := by
  have hPort {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f : ℕ} (hf : f < 19) :
      port n t s f 0 < sharedLimit n t := by
    obtain ⟨ha,hj,_⟩ := layout_mem.mp hs
    exact port_lt_shared ha hj hf (Nat.two_pow_pos _)
  obtain ⟨s,hs,hg⟩ := List.mem_flatMap.mp hg
  rcases List.mem_append.mp hg with hg|hg
  · obtain ⟨f,hf,rfl⟩ := List.mem_map.mp hg
    have hF : f < 19 := by simp at hf; omega
    simp only [Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,or_false] at hr
    rcases hr with rfl|rfl
    · exact hPort hs (by decide)
    · exact hPort hs hF
  · obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
    have hj' : j ≤ layoutHeight t := Nat.le_of_lt_succ (List.mem_range.mp (List.mem_filter.mp hj).1)
    simp only [Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,or_false] at hr
    rcases hr with rfl|rfl
    · exact hPort hs (by decide)
    · exact hPort (ancestorAt_mem hs hj') (by decide)

theorem length_slotShapeGates (n t : ℕ) :
    (slotShapeGates n t).length ≤ 2*layoutHorizon t*(layoutHeight t+5) := by
  have hlen (slots : List (ℕ × ℕ)) : (slots.flatMap (slotGuardGates n t)).length ≤
      slots.length * (layoutHeight t+5) := by
    induction slots with
    | nil => simp
    | cons s slots ih =>
      have heg := List.length_filter_le (fun j => decide (s.2 < j)) (List.range (layoutHeight t+1))
      simp only [List.length_range] at heg
      simp only [List.flatMap_cons,List.length_append, List.length_cons,Nat.add_mul,Nat.one_mul]
      refine Nat.add_le_add ?_ ih |>.trans_eq (Nat.add_comm _ _)
      simp only [slotGuardGates,List.length_append,List.length_map,List.length_cons,List.length_nil]
      omega
  exact (hlen _).trans (Nat.mul_le_mul_right _ (layoutSlots_length_le t))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

open scoped BigOperators

private def slotPairEnc : (ℕ × ℕ) ↪ List Bool := encPair encUnary encUnary

theorem slotPort_poly {A : Type} {e : A ↪ List Bool} {n t a j f b : A → ℕ}
    (hN : ComputableTidilyInPolyTime n e encUnary) (hT : ComputableTidilyInPolyTime t e encUnary)
    (ha : ComputableTidilyInPolyTime a e encUnary) (hj : ComputableTidilyInPolyTime j e encUnary)
    (hf : ComputableTidilyInPolyTime f e encUnary) (hb : ComputableTidilyInPolyTime b e encUnary) :
    ComputableTidilyInPolyTime (fun x => port (n x) (t x) (a x,j x) (f x) (b x)) e encUnary := by
  have hH := layoutHeight_poly.comp hT
  have hW := layoutHorizon_poly.comp hT
  unfold port
  dsimp
  fun_prop

private theorem slotGuardClause_poly {A : Type} {e : A ↪ List Bool} {r s : A → ℕ} (b : Bool)
    (hr : ComputableTidilyInPolyTime r e encUnary)
    (hs : ComputableTidilyInPolyTime s e encUnary) :
    ComputableTidilyInPolyTime
      (fun a => Gate.assert [if b then .Pos (r a) else .Neg (r a),.Neg (s a)]) e gateEnc := by
  have hR := unary_mul.comp ((const 2).prod hr)
  have hS := unary_mul.comp ((const 2).prod hs)
  apply gate_assert
  cases b
  · exact cons' hR (cons' hS (const []))
  · exact cons' (unary_add.comp (hR.prod (const 1))) (cons' hS (const []))

/-- Uniformly list the local shared-port checks. Ancestor powers are capped outside
the enumerated range, which keeps auxiliary unary computations polynomial. -/
theorem slotShapeGates_poly {A : Type} {e : A ↪ List Bool} {n t : A → ℕ}
    (hN : ComputableTidilyInPolyTime n e encUnary) (hT : ComputableTidilyInPolyTime t e encUnary) :
    ComputableTidilyInPolyTime (fun a => slotShapeGates (n a) (t a)) e (encList gateEnc) := by
  let ep := encPair e slotPairEnc
  let ef := encPair ep encUnary
  have hX := fst e slotPairEnc
  have hStart := (fst encUnary encUnary).comp (snd e slotPairEnc)
  have hLevel := (snd encUnary encUnary).comp (snd e slotPairEnc)
  have hN' := hN.comp hX
  have hT' := hT.comp hX
  have hHt := layoutHeight_poly.comp hT'
  have hD := fst ep encUnary
  have hI := snd ep encUnary
  have hNt := hN'.comp hD
  have hTt := hT'.comp hD
  have hAt := hStart.comp hD
  have hJt := hLevel.comp hD
  have hLive := slotPort_poly hNt hTt hAt hJt (const 18) (const 0)
  have hUse := slotPort_poly hNt hTt hAt hJt hI (const 0)
  have hPresence := slotGuardClause_poly true hLive hUse
  have hInactive := mapWithInput (f := fun (p : A × (ℕ × ℕ)) f =>
      Gate.assert [.Pos (port (n p.1) (t p.1) p.2 18 0),.Neg (port (n p.1) (t p.1) p.2 f 0)])
      (const [0,3,8,13]) hPresence
  have hCap := unary_min.comp (hI.prod (hHt.comp hD))
  have hw : ComputableTidilyInPolyTime (fun p : (A × (ℕ × ℕ)) × ℕ =>
      2^(min p.2 (layoutHeight (t p.1.1)))) ef encUnary :=
    unary_pow2_of_bound hCap (layoutHorizon_poly.comp hTt)
      (fun p => Nat.pow_le_pow_right (by decide) (min_le_right _ _))
  have hA' := unary_mul.comp ((unary_div_poly.comp (hAt.prod hw)).prod hw)
  have hAncestor := slotPort_poly hNt hTt hA' hI (const 18) (const 0)
  have hNoOverlap := slotGuardClause_poly false hLive hAncestor
  have hCandidates := filterWithInput
    (test := fun (p : A × (ℕ × ℕ)) j => decide (p.2.2 < j))
    (range.comp (unary_add.comp (hHt.prod (const 1)))) (unary_lt' hJt hI)
  let guard (p : A × (ℕ × ℕ)) (j : ℕ) := Gate.assert
    [.Neg (port (n p.1) (t p.1) p.2 18 0),
      .Neg (port (n p.1) (t p.1) (p.2.1 / 2^(min j (layoutHeight (t p.1))) *
        2^(min j (layoutHeight (t p.1))),j) 18 0)]
  have hSafe : ComputableTidilyInPolyTime (fun p : (A × (ℕ × ℕ)) × ℕ => guard p.1 p.2)
      ef gateEnc := hNoOverlap
  have hDisjoint := mapWithInput (f := guard) hCandidates hSafe
  have hs := listAppend' hInactive hDisjoint
  have hs' : ComputableTidilyInPolyTime (fun p : A × (ℕ × ℕ) => slotGuardGates (n p.1) (t p.1) p.2)
      ep (encList gateEnc) := by
    refine hs.of_enc_eq ?_
    intro p
    apply congrArg (encList gateEnc)
    unfold slotGuardGates
    congr 1
    apply List.map_congr_left
    intro j hj
    have hJ : j ≤ layoutHeight (t p.1) := Nat.le_of_lt_succ (List.mem_range.mp (List.mem_filter.mp hj).1)
    simp only [guard,ancestorAt,min_eq_left hJ]
  exact flatMapWithInput (f := fun a s => slotGuardGates (n a) (t a) s)
    (layoutSlots_poly.comp hT) hs'

theorem slotShapeGates_extends (n t : ℕ) (α : Assignment) :
    ExtendsWith (sharedLimit n t) (slotShapeGates n t) α ↔ SlotsWellFormed α n t := by
  rw [← slotShapeGates_exact]
  constructor
  · rintro ⟨β,h,hG⟩ g hg
    exact (gate_congr g fun r hr => h r (slotShapeGates_shared hg hr)).1 (hG g hg)
  · intro h
    exact ⟨α,fun _ _ => rfl,h⟩

theorem layoutHeight_le_size (t : ℕ) : layoutHeight t ≤ t.size+6 := by
  change (4*(9*t+1)-1).size ≤ t.size+6
  apply Nat.size_le.mpr
  have h := Nat.lt_size_self t
  rw [pow_add]
  norm_num
  omega

theorem length_slotShapeGates_log (n t : ℕ) :
    (slotShapeGates n t).length ≤ 1584*(t+1)*(t.size+1) := by
  have hHor : layoutHorizon t ≤ 8*(9*t+1) := by
    change slotWidth (4*(9*t+1)) ≤ 8*(9*t+1)
    have h := slotWidth_le_double (cost := 4*(9*t+1)) (by omega)
    omega
  have hA : 2*layoutHorizon t ≤ 144*(t+1) := by omega
  have hH := layoutHeight_le_size t
  have hB : layoutHeight t+5 ≤ 11*(t.size+1) := by omega
  exact (length_slotShapeGates n t).trans (calc
    _ ≤ (144*(t+1))*(11*(t.size+1)) := Nat.mul_le_mul hA hB
    _ = 1584*(t+1)*(t.size+1) := by ring)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

private theorem slotCenter_mod {t j : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t)
    (hj : j ≤ s.2) : slotCenter s % 2^j = 0 := by
  have hsDiv : 2^s.2 ∣ s.1 := Nat.dvd_iff_mod_eq_zero.mpr (layout_mem.mp hs).2.2
  have hPow : 2^j ∣ 2^s.2 := Nat.pow_dvd_pow 2 hj
  have hDiv := hPow.trans hsDiv
  unfold slotCenter
  exact Nat.dvd_iff_mod_eq_zero.mp (Nat.dvd_add (hDiv.mul_left 2) hPow)

private theorem div_eq_iff_of_mod_zero {a b w : ℕ} (ha : a%w=0) (hb : b%w=0) :
    a / w = b / w ↔ a=b := by
  have h₁ := Nat.mod_add_div a w
  have h₂ := Nat.mod_add_div b w
  rw [ha,Nat.zero_add] at h₁
  rw [hb,Nat.zero_add] at h₂
  constructor
  · intro h
    rw [h] at h₁
    exact h₁.symm.trans h₂
  · intro h
    subst b
    rfl

/-- A tier of width `2^j` can only receive rows from the slots at least that wide.
Their number is bounded simultaneously for every level. -/
theorem slotsAtLeast_bound (t j : ℕ) :
    ((layoutSlots t).filter fun s => j ≤ s.2).length ≤ (2*layoutHorizon t)/2^j := by
  let xs := (layoutSlots t).filter fun s => j ≤ s.2
  by_cases hj : j ≤ layoutHeight t
  · have hMod : (2*layoutHorizon t) % 2^j = 0 :=
      Nat.dvd_iff_mod_eq_zero.mp ((Nat.pow_dvd_pow 2 hj).mul_left 2)
    let key (s : ℕ × ℕ) := slotCenter s/2^j
    have keyND : (xs.map key).Nodup := by
      apply ((layout_nodup t).filter _).map_on
      intro a ha b hb he
      obtain ⟨ha,hjA⟩ := List.mem_filter.mp ha
      obtain ⟨hb,hjB⟩ := List.mem_filter.mp hb
      exact slotCenter_injOn t ha hb
        ((div_eq_iff_of_mod_zero (slotCenter_mod ha (of_decide_eq_true hjA))
          (slotCenter_mod hb (of_decide_eq_true hjB))).mp he)
    have hSub : xs.map key ⊆ List.range ((2*layoutHorizon t)/2^j) := by
      intro y hy
      obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hy
      have hLt := slotCenter_lt t (List.mem_filter.mp hs).1
      have hExact := Nat.mod_add_div (2*layoutHorizon t) (2^j)
      rw [hMod,Nat.zero_add] at hExact
      apply List.mem_range.mpr
      apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos j)).mpr
      rwa [Nat.mul_comm,hExact]
    simpa [xs] using keyND.length_le_of_subset hSub
  · have hE : xs = [] := by
      apply List.filter_eq_nil_iff.mpr
      intro s hs
      have hL := (layout_mem.mp hs).2.1
      have hO : ¬ j ≤ s.2 := by omega
      simp [hO]
    change xs.length ≤ _
    rw [hE]
    simp

private theorem aligned_slot_end {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) :
    s.1+2^s.2 ≤ layoutHorizon t := by
  obtain ⟨ha,hl,hdiv⟩ := layout_mem.mp hs
  have hMod : layoutHorizon t % 2^s.2 = 0 :=
    Nat.dvd_iff_mod_eq_zero.mp (Nat.pow_dvd_pow 2 hl)
  have hA := Nat.mod_add_div s.1 (2^s.2)
  have hB := Nat.mod_add_div (layoutHorizon t) (2^s.2)
  rw [hdiv,Nat.zero_add] at hA
  rw [hMod,Nat.zero_add] at hB
  have hQ : s.1/2^s.2 < layoutHorizon t/2^s.2 :=
    Nat.lt_of_mul_lt_mul_left (by rwa [hA,hB])
  have h := Nat.mul_le_mul_left (2^s.2) hQ
  rwa [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,hA,hB] at h

private def slotCells (t : ℕ) (s : ℕ × ℕ) : List ℕ :=
  (List.range (2^s.2)).map (fun i => s.2*layoutHorizon t+(s.1+i))

private theorem cells_div {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {i : ℕ} (hi : i < 2^s.2) :
    (s.2*layoutHorizon t+(s.1+i))/layoutHorizon t = s.2 := by
  have hEnd := aligned_slot_end hs
  apply Nat.div_eq_of_lt_le
  · exact Nat.le_add_right _ _
  · rw [Nat.add_mul,Nat.one_mul]
    omega

private theorem slotCells_disjoint {t : ℕ} {s r : ℕ × ℕ}
    (hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (hNe : s≠r)
    {k : ℕ} (hk : k ∈ slotCells t s) : k ∉ slotCells t r := by
  intro hk'
  obtain ⟨i,hi,he⟩ := List.mem_map.mp hk
  obtain ⟨j,hj,he'⟩ := List.mem_map.mp hk'
  have hi' := List.mem_range.mp hi
  have hj' := List.mem_range.mp hj
  have hEq := he.trans he'.symm
  have hLev : s.2=r.2 := by
    rw [← cells_div hs hi', ← cells_div hr hj',hEq]
  have hEqual : s.1+i = r.1+j := by rw [hLev] at hEq; omega
  have ha := (layout_mem.mp hs).2.2
  have hb := (layout_mem.mp hr).2.2
  rw [← hLev] at hb hj'
  have hs' : (s.1+i)/2^s.2 = s.1/2^s.2 := by
    have hA := Nat.mod_add_div s.1 (2^s.2)
    rw [ha,Nat.zero_add,Nat.mul_comm] at hA
    apply Nat.div_eq_of_lt_le
    · rw [hA]; omega
    · rw [Nat.add_mul,Nat.one_mul,hA]; omega
  have hr' : (r.1+j)/2^s.2 = r.1/2^s.2 := by
    have hA := Nat.mod_add_div r.1 (2^s.2)
    rw [hb,Nat.zero_add,Nat.mul_comm] at hA
    apply Nat.div_eq_of_lt_le
    · rw [hA]; omega
    · rw [Nat.add_mul,Nat.one_mul,hA]; omega
  have hAdd : s.1=r.1 := (div_eq_iff_of_mod_zero ha hb).mp (by rw [← hs',← hr',hEqual])
  exact hNe (Prod.ext hAdd hLev)

/-- Counting all allocated columns, one horizon per width level suffices. -/
theorem layoutSlotBits_bound (t : ℕ) :
    ((layoutSlots t).map (fun s => 2^s.2)).sum ≤ (layoutHeight t+1)*layoutHorizon t := by
  let cells := (layoutSlots t).flatMap (slotCells t)
  have hLen (xs : List (ℕ × ℕ)) :
      (xs.flatMap (slotCells t)).length = (xs.map (fun s => 2^s.2)).sum := by
    induction xs with
    | nil => rfl
    | cons s xs ih => simp [slotCells,ih]
  have hSub : cells ⊆ List.range ((layoutHeight t+1)*layoutHorizon t) := by
    intro k hk
    obtain ⟨s,hs,hk⟩ := List.mem_flatMap.mp hk
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hk
    apply List.mem_range.mpr
    have hEnd := aligned_slot_end hs
    have hI := List.mem_range.mp hi
    have hL := (layout_mem.mp hs).2.1
    have hTop : (s.2+1)*layoutHorizon t ≤ (layoutHeight t+1)*layoutHorizon t :=
      Nat.mul_le_mul_right _ (Nat.succ_le_succ hL)
    rw [Nat.add_mul,Nat.one_mul] at hTop
    omega
  have hND : cells.Nodup := by
    unfold cells List.Nodup
    rw [List.pairwise_flatMap]
    refine ⟨?_,?_⟩
    · intro s _
      unfold slotCells
      apply List.Nodup.map
      · intro a b h
        dsimp only at h
        omega
      · exact List.nodup_range
    · apply (layout_nodup t).imp_of_mem
      intro s r hs hr hn a ha b hb he
      subst b
      exact slotCells_disjoint hs hr hn ha hb
  have hBound := hND.length_le_of_subset hSub
  simpa only [cells,hLen,List.length_range] using hBound

end CNFEncComplexity.Robson

namespace CNFEncComplexity.RobsonCNF

open CookLevin

/-- Select at least one guarded set of gate obligations. A satisfying branch
can use any auxiliary assignment while disabled branches impose no conditions. -/
def choiceGates (branches : List (ℕ × List Gate)) : List Gate :=
  .assert (branches.map (fun b => Literal.Pos b.1)) ::
    branches.flatMap (fun b => guarded (.Pos b.1) b.2)

theorem choiceGates_exact (branches : List (ℕ × List Gate)) (a : Assignment) :
    (∀ g ∈ choiceGates branches, g.Holds a) ↔
      (∃ b ∈ branches, a b.1=true) ∧
      ∀ b ∈ branches, a b.1=true → ∀ g ∈ b.2, g.Holds a := by
  constructor
  · intro h
    have hHead := h (.assert (branches.map (fun b => Literal.Pos b.1))) List.mem_cons_self
    change satisfiesClause a _ = true at hHead
    obtain ⟨l,lMem,lSat⟩ := (satisfiesClause_iff a _).mp hHead
    obtain ⟨b,bMem,rfl⟩ := List.mem_map.mp lMem
    refine ⟨⟨b,bMem,lSat⟩,?_⟩
    intro br hr he
    apply (guarded_exact (.Pos br.1) br.2 a).mp _ he
    intro g hg
    exact h g (List.mem_cons_of_mem _ (List.mem_flatMap.mpr ⟨br,hr,hg⟩))
  · rintro ⟨⟨b,hb,he⟩,h⟩ g hg
    rcases List.mem_cons.mp hg with rfl | hg
    · exact (satisfiesClause_iff a _).mpr ⟨.Pos b.1,List.mem_map.mpr ⟨b,hb,rfl⟩,he⟩
    · obtain ⟨br,hbr,hg⟩ := List.mem_flatMap.mp hg
      exact (guarded_exact (.Pos br.1) br.2 a).mpr (h br hbr) g hg

theorem choiceGates_sound (branches : List (ℕ × List Gate)) (a : Assignment)
    (h : ∀ g ∈ choiceGates branches, g.Holds a) :
    ∃ b ∈ branches, ∀ g ∈ b.2, g.Holds a := by
  obtain ⟨⟨b,hb,he⟩,hBody⟩ := (choiceGates_exact branches a).mp h
  exact ⟨b,hb,hBody b hb he⟩

theorem choiceGates_complete (branches : List (ℕ × List Gate)) (a : Assignment)
    (hDistinct : ∀ u ∈ branches, ∀ v ∈ branches, u.1=v.1 → u=v)
    (b : ℕ × List Gate) (hb : b ∈ branches)
    (hNoSelectors : ∀ g ∈ b.2, ∀ k ∈ g.names, k ∉ branches.map Prod.fst)
    (hBody : ∀ g ∈ b.2, g.Holds a) :
    ∃ a' : Assignment, (∀ k ∉ branches.map Prod.fst, a' k = a k) ∧
      ∀ g ∈ choiceGates branches, g.Holds a' := by
  let a' : Assignment := fun k =>
    if k ∈ branches.map Prod.fst then decide (k=b.1) else a k
  have keep (k : ℕ) (hk : k ∉ branches.map Prod.fst) : a' k = a k := by
    simp [a',hk]
  refine ⟨a',keep,(choiceGates_exact branches a').mpr ⟨?_,?_⟩⟩
  · have hm : b.1 ∈ branches.map Prod.fst := List.mem_map_of_mem hb
    exact ⟨b,hb,by simp only [a',if_pos hm,decide_true]⟩
  · intro br hbr enable g hg
    have hm : br.1 ∈ branches.map Prod.fst := List.mem_map_of_mem hbr
    have hf : br.1=b.1 := by simpa only [a',if_pos hm,decide_eq_true_eq] using enable
    have he : br=b := hDistinct br hbr b hb hf
    subst br
    exact (g.holds_congr a' a (fun k hk => keep k (hNoSelectors g hg k hk))).mpr (hBody g hg)

theorem choiceGates_length_le (branches : List (ℕ × List Gate)) :
    (choiceGates branches).length ≤ 1+4*(branches.map fun b => b.2.length).sum := by
  change (branches.flatMap (fun b => guarded (.Pos b.1) b.2)).length + 1 ≤ _
  have aux (xs : List (ℕ × List Gate)) :
      (xs.flatMap (fun b => guarded (.Pos b.1) b.2)).length ≤
        4*(xs.map fun b => b.2.length).sum := by
    induction xs with
    | nil => simp
    | cons b bs ih =>
      simp only [List.flatMap_cons,List.length_append,List.map_cons,List.sum_cons,Nat.mul_add]
      exact Nat.add_le_add (length_guarded (.Pos b.1) b.2) ih
  have h := aux branches
  omega

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF
open CookLevin

theorem wireValue_eq_bitString (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
    wireValue α key n = (Cslib.BitString.equivFin n (fun i => α (key i.val))).val := by
  rw [wireValue_eq_sum,Cslib.BitString.val_equivFin_eq_sum]
  rw [← List.sum_toFinset _ List.nodup_range,List.toFinset_range,Finset.sum_range]

theorem wireValue_eq_iff (α : Assignment) (lhs rhs : ℕ → ℕ) (n : ℕ) :
    wireValue α lhs n = wireValue α rhs n ↔ ∀ i < n, α (lhs i) = α (rhs i) := by
  rw [wireValue_eq_bitString,wireValue_eq_bitString]
  constructor
  · intro h i hi
    have hh := (Cslib.BitString.equivFin n).injective (Fin.ext h)
    exact congrFun hh ⟨i,hi⟩
  · intro h
    have hh : (fun i : Fin n => α (lhs i.val)) = (fun i : Fin n => α (rhs i.val)) :=
      funext (fun i => h _ i.isLt)
    rw [hh]

/-- Require two little-endian words to be equal without introducing auxiliary wires. -/
def wordCopy (n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  (List.range n).map (fun i => .copy (lhs i) (rhs i))

@[simp] theorem length_wordCopy (n : ℕ) (lhs rhs : ℕ → ℕ) :
    (wordCopy n lhs rhs).length = n := by simp [wordCopy]

theorem wordCopy_exact (n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) :
    (∀ g ∈ wordCopy n lhs rhs, g.Holds α) ↔ wireValue α lhs n = wireValue α rhs n := by
  rw [wireValue_eq_iff]
  constructor
  · intro h i hi
    exact h (.copy (lhs i) (rhs i)) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
  · intro h g hg
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
    exact h i (List.mem_range.mp hi)

/-- Pin a binary word to a known natural value. -/
def wordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) : List Gate :=
  (List.range n).map (fun i => .pin (key i) (value.testBit i))

@[simp] theorem length_wordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) :
    (wordConst n key value).length = n := by simp [wordConst]

theorem wordConst_exact (n : ℕ) (key : ℕ → ℕ) (value : ℕ) (hv : value < 2^n)
    (α : Assignment) :
    (∀ g ∈ wordConst n key value, g.Holds α) ↔ wireValue α key n = value := by
  let b : Fin (2^n) := ⟨value,hv⟩
  let e := Cslib.BitString.equivFin n
  rw [wireValue_eq_bitString]
  change (∀ g ∈ wordConst n key value,g.Holds α) ↔ (e (fun i => α (key i.val))).val = b.val
  constructor
  · intro h
    have he : (fun i : Fin n => α (key i.val)) = e.symm b := by
      funext i
      change α (key i.val) = (Cslib.BitString.equivFin n).symm b i
      rw [Cslib.BitString.equivFin_symm_apply]
      exact h (.pin (key i.val) (b.val.testBit i.val)) (List.mem_map.mpr ⟨_,List.mem_range.mpr i.isLt,rfl⟩)
    rw [he,e.apply_symm_apply]
  · intro h g hg
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
    have hf := congrArg e.symm (Fin.ext h)
    rw [e.symm_apply_apply] at hf
    have hs := congrFun hf ⟨i,List.mem_range.mp hi⟩
    change α (key i) = value.testBit i
    change α (key i) = (Cslib.BitString.equivFin n).symm b ⟨i,List.mem_range.mp hi⟩ at hs
    rw [Cslib.BitString.equivFin_symm_apply] at hs
    exact hs

def mismatchWire (base i : ℕ) := base+i

/-- To witness disequality, compute each difference bit and assert their disjunction. -/
def wordMismatch (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  (List.range n).map (fun i => .parity (mismatchWire base i) (lhs i) (rhs i)) ++
    [.assert ((List.range n).map (fun i => .Pos (mismatchWire base i)))]

@[simp] theorem length_wordMismatch (base n : ℕ) (lhs rhs : ℕ → ℕ) :
    (wordMismatch base n lhs rhs).length = n+1 := by simp [wordMismatch]

theorem wordMismatch_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ wordMismatch base n lhs rhs, g.Holds α) :
    wireValue α lhs n ≠ wireValue α rhs n := by
  intro he
  have hSame := (wireValue_eq_iff α lhs rhs n).mp he
  have hg := h (.assert ((List.range n).map (fun i => .Pos (mismatchWire base i))))
    (List.mem_append.mpr (.inr List.mem_cons_self))
  change satisfiesClause α _ = true at hg
  obtain ⟨lit,hlit,ht⟩ := (satisfiesClause_iff α _).mp hg
  obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hlit
  have hb : α (mismatchWire base i) = (α (lhs i) ^^ α (rhs i)) :=
    h (.parity (mismatchWire base i) (lhs i) (rhs i))
      (List.mem_append.mpr (.inl (List.mem_map.mpr ⟨i,hi,rfl⟩)))
  change α (mismatchWire base i) = true at ht
  rw [hb,hSame i (List.mem_range.mp hi)] at ht
  cases heq : α (rhs i) <;> simp [heq] at ht

theorem wordMismatch_extends (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
    (h : wireValue α lhs n ≠ wireValue α rhs n) :
    ∃ β : Assignment, (∀ k, (k < base ∨ base+n ≤ k) → β k = α k) ∧
      (∀ g ∈ wordMismatch base n lhs rhs,g.Holds β) := by
  let β : Assignment := fun k =>
    if base ≤ k ∧ k < base+n then α (lhs (k-base)) ^^ α (rhs (k-base)) else α k
  have hSmall (k : ℕ) (hk : k < base) : β k = α k := by
    have hx : ¬(base ≤ k ∧ k < base+n) := fun hp => (Nat.not_le_of_gt hk) hp.1
    simp [β,hx]
  have hBit (i : ℕ) (hi : i < n) : β (mismatchWire base i) = (α (lhs i) ^^ α (rhs i)) := by
    have hh : base ≤ base+i ∧ base+i < base+n := by omega
    simp [β,mismatchWire,hh]
  have hWitness : ∃ i < n, α (lhs i) ≠ α (rhs i) := by
    by_contra hn
    apply h
    apply (wireValue_eq_iff α lhs rhs n).mpr
    intro i hi
    by_contra hh
    exact hn ⟨i,hi,hh⟩
  refine ⟨β,?_,?_⟩
  · intro k hk
    rcases hk with hk | hk
    · exact hSmall k hk
    · have hx : ¬(base ≤ k ∧ k < base+n) := fun hp => (Nat.not_lt_of_ge hk) hp.2
      simp [β,hx]
  · intro g hg
    rcases List.mem_append.mp hg with hg | hg
    · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
      have hI := List.mem_range.mp hi
      change β (mismatchWire base i) = (β (lhs i) ^^ β (rhs i))
      rw [hBit i hI,hSmall _ (hL i hI),hSmall _ (hR i hI)]
    · rw [List.mem_singleton] at hg
      subst g
      apply (satisfiesClause_iff β _).mpr
      obtain ⟨i,hi,hdiff⟩ := hWitness
      refine ⟨.Pos (mismatchWire base i),List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩,?_⟩
      change β (mismatchWire base i) = true
      rw [hBit i hi]
      cases ha : α (lhs i) <;> cases hb : α (rhs i) <;> simp_all

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson

inductive PacketExpr where
  | constant (n : ℕ)
  | operand (i : ℕ)
  | symbol
  | add (a b : PacketExpr)
  | sub (a b : PacketExpr)
  | width (a : PacketExpr)

def PacketExpr.eval (p : Packet) : PacketExpr → ℕ
  | .constant n => n
  | .operand i => p.operand i
  | .symbol => p.input.getD 0
  | .add a b => a.eval p + b.eval p
  | .sub a b => a.eval p - b.eval p
  | .width a => bitLen (a.eval p)

structure PacketAccessPattern where
  writes : Bool
  address : PacketExpr
  value : PacketExpr

def PacketAccessPattern.eval (p : Packet) (a : PacketAccessPattern) : MemoryAccess :=
  ⟨a.address.eval p,a.value.eval p,a.writes⟩

structure PacketPattern where
  next : ℕ
  readsInput : Bool
  accesses : List PacketAccessPattern
  cost : PacketExpr
  zero : Option Bool := none

def PacketPattern.matches (m : PacketPattern) (next : ℕ) (p : Packet) : Prop :=
  next=m.next ∧ p =
    ⟨if m.readsInput then some (PacketExpr.eval p .symbol) else none,
      m.accesses.map (PacketAccessPattern.eval p),m.cost.eval p⟩ ∧
  ∀ flag, m.zero = some flag → (p.operand 0=0 ↔ flag=true)

private def a : PacketExpr := .operand 0
private def b : PacketExpr := .operand 1
private def sym : PacketExpr := .symbol
private def k : ℕ → PacketExpr := PacketExpr.constant
private def c1 (x : PacketExpr) : PacketExpr := .add (.constant 1) (.width x)
private def c2 (x y : PacketExpr) : PacketExpr := .add (c1 x) (.width y)
private def c3 (x y z : PacketExpr) : PacketExpr := .add (c2 x y) (.width z)
private def rd (i v : PacketExpr) : PacketAccessPattern := ⟨false,i,v⟩
private def wr (i v : PacketExpr) : PacketAccessPattern := ⟨true,i,v⟩

/-- Every instruction has one or two conjunctions of fixed packet tests.
Reading an input checks that its symbol exists and copies the two raw bits. -/
def instrPatterns (pc : ℕ) : Instr → List PacketPattern
  | .loadc v => [⟨pc+1,false,[wr (k 0) (k v)],c1 (k v),none⟩]
  | .load j => [⟨pc+1,false,[rd (k j) a,wr (k 0) a],c2 (k j) a,none⟩]
  | .loadi j => [⟨pc+1,false,[rd (k j) a,rd a b,wr (k 0) b],c3 (k j) a b,none⟩]
  | .store j => [⟨pc+1,false,[rd (k 0) a,wr (k j) a],c2 (k j) a,none⟩]
  | .storei j => [⟨pc+1,false,[rd (k j) a,rd (k 0) b,wr a b],c3 (k j) a b,none⟩]
  | .add j => [⟨pc+1,false,[rd (k 0) a,rd (k j) b,wr (k 0) (.add a b)],c3 (k j) a b,none⟩]
  | .sub j => [⟨pc+1,false,[rd (k 0) a,rd (k j) b,wr (k 0) (.sub a b)],c3 (k j) a b,none⟩]
  | .read => [⟨pc+1,true,[wr (k 0) sym],c1 sym,none⟩]
  | .jump j => [⟨j,false,[],c1 (k j),none⟩]
  | .jzero j =>
      [⟨j,false,[rd (k 0) (k 0)],c2 (k j) (k 0),some true⟩,
       ⟨pc+1,false,[rd (k 0) a],c2 (k j) a,some false⟩]
  | .njump l r => [⟨l,false,[],c2 (k l) (k r),none⟩,⟨r,false,[],c2 (k l) (k r),none⟩]
  | .halt => []

theorem instrPatterns_length (pc : ℕ) (op : Instr) : (instrPatterns pc op).length ≤ 2 := by
  cases op <;> simp [instrPatterns]

theorem instrPatterns_exact (op : Instr) (pc next : ℕ) (p : Packet) :
    InstrPacket op pc next p ↔ ∃ m ∈ instrPatterns pc op, m.matches next p := by
  cases op <;> simp [InstrPacket,instrPatterns,PacketPattern.matches,PacketExpr.eval,
    PacketAccessPattern.eval,a,b,sym,k,c1,c2,c3,rd,wr,MemoryAccess.read,MemoryAccess.write]
  · by_cases h : p.operand 0=0 <;> simp [h]
  · tauto


inductive AdvancePattern where
  | idle
  | stop (pc : ℕ)
  | step (pc : ℕ) (p : PacketPattern)

def AdvancePattern.matches (v : Option PortView) (u w : ScanState) : AdvancePattern → Prop
  | .idle => v=none ∧ u=w
  | .stop pc => v=some finalPacket.ports ∧ u.control=some pc ∧ w.control=none ∧
      w.clock=u.clock+(1+bitLen 1)
  | .step pc p => ∃ x next, v=some x ∧ u.control=some pc ∧ w.control=some next ∧
      u.clock ≤ w.clock ∧ p.matches next ⟨x.1,x.2,w.clock-u.clock⟩

def opcodePatterns (pc : ℕ) (op : Instr) : List AdvancePattern :=
  match op with
  | .halt => [.stop pc]
  | _ => (instrPatterns pc op).map (.step pc)

def advancePatterns (prog : List Instr) : List AdvancePattern :=
  .idle :: (List.finRange prog.length).flatMap
    (fun i => opcodePatterns i.val prog[i.val])

private theorem opcodePatterns_step {pc : ℕ} {op : Instr} {pat : PacketPattern} :
    AdvancePattern.step pc pat ∈ opcodePatterns pc op ↔ pat ∈ instrPatterns pc op := by
  cases op <;> simp [opcodePatterns,instrPatterns]

private theorem opcodePatterns_cases {pc : ℕ} {op : Instr} {pat : AdvancePattern}
    (h : pat ∈ opcodePatterns pc op) :
    (op = .halt ∧ pat = .stop pc) ∨ ∃ m ∈ instrPatterns pc op, pat = .step pc m := by
  cases op <;> simp_all [opcodePatterns,List.mem_map] <;> aesop

theorem advancePatterns_length (prog : List Instr) : (advancePatterns prog).length ≤ 1+2*prog.length := by
  have hOp (pc : ℕ) (op : Instr) : (opcodePatterns pc op).length ≤ 2 := by
    cases op <;> simp [opcodePatterns,instrPatterns]
  have hRows (xs : List (Fin prog.length)) :
      (xs.flatMap (fun i => opcodePatterns i.val prog[i.val])).length ≤ 2*xs.length := by
    induction xs with
    | nil => simp
    | cons i xs ih =>
      simp only [List.flatMap_cons,List.length_append,List.length_cons,Nat.mul_add,Nat.mul_one]
      have h := hOp i.val prog[i.val]
      omega
  have h := hRows (List.finRange prog.length)
  simp only [advancePatterns,List.length_cons,List.length_finRange] at *
  omega

theorem advancePatterns_exact (prog : List Instr) (v : Option PortView) (u w : ScanState) :
    LocalAdvance prog v u w ↔ ∃ pat ∈ advancePatterns prog, pat.matches v u w := by
  have atOp {pc : ℕ} {op : Instr} (h : prog[pc]? = some op) :
      ∃ i : Fin prog.length, i.val=pc ∧ prog[i.val]=op := by
    obtain ⟨hi,he⟩ := List.getElem?_eq_some_iff.mp h
    exact ⟨⟨pc,hi⟩,rfl,he⟩
  have emit {pc : ℕ} {op : Instr} {pat : AdvancePattern}
      (hOp : prog[pc]? = some op) (hPat : pat ∈ opcodePatterns pc op) :
      pat ∈ advancePatterns prog := by
    obtain ⟨i,hi,he⟩ := atOp hOp
    apply List.mem_cons_of_mem
    apply List.mem_flatMap.mpr
    refine ⟨i,List.mem_finRange i,?_⟩
    rwa [he,hi]
  constructor
  · intro h
    cases v with
    | none =>
      exact ⟨.idle,List.mem_cons_self,rfl,h⟩
    | some x =>
      cases hu : u.control with
      | none => simp [LocalAdvance,hu] at h
      | some pc =>
        cases hw : w.control with
        | none =>
          have hh : prog[pc]? = some .halt ∧ x = finalPacket.ports ∧
              w.clock = u.clock+(1+bitLen 1) := by simpa [LocalAdvance,hu,hw] using h
          exact ⟨.stop pc,emit hh.1 (by simp [opcodePatterns]),congrArg some hh.2.1,hu,hw,hh.2.2⟩
        | some next =>
          have hh : u.clock ≤ w.clock ∧ ∃ op, prog[pc]? = some op ∧
              InstrPacket op pc next ⟨x.1,x.2,w.clock-u.clock⟩ := by
            simpa [LocalAdvance,hu,hw] using h
          obtain ⟨op,hOp,hStep⟩ := hh.2
          obtain ⟨m,hm,hRule⟩ := (instrPatterns_exact op pc next _).mp hStep
          exact ⟨.step pc m,emit hOp (opcodePatterns_step.mpr hm),x,next,rfl,hu,hw,hh.1,hRule⟩
  · rintro ⟨pat,hPat,hMatch⟩
    rcases List.mem_cons.mp hPat with rfl | hPat
    · obtain ⟨rfl,he⟩ := hMatch
      simp [LocalAdvance,he]
    · obtain ⟨i,_,hOpPat⟩ := List.mem_flatMap.mp hPat
      have hOp : prog[i.val]? = some prog[i.val] :=
        List.getElem?_eq_getElem i.isLt
      rcases opcodePatterns_cases hOpPat with ⟨he,rfl⟩ | ⟨m,hm,rfl⟩
      · obtain ⟨rfl,hu,hw,hClock⟩ := hMatch
        simp [LocalAdvance,hu,hw,hOp,he,hClock]
      · obtain ⟨x,next,rfl,hu,hw,hClock,hRule⟩ := hMatch
        have hStep := (instrPatterns_exact _ _ _ _).mpr ⟨m,hm,hRule⟩
        simpa only [LocalAdvance,hu,hw] using
          And.intro hClock ⟨prog[i.val],hOp,hStep⟩

end CNFEncComplexity.Robson

namespace CNFEncComplexity.RobsonCNF
open CookLevin

/-- A too-wide constant makes only this branch impossible. -/
def boundedWordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) : List Gate :=
  if value < 2^n then wordConst n key value else [.assert []]

theorem boundedWordConst_exact (n : ℕ) (key : ℕ → ℕ) (c : ℕ) (a : Assignment) :
    (∀ g ∈ boundedWordConst n key c, g.Holds a) ↔ wireValue a key n = c := by
  by_cases h : c < 2^n
  · simpa only [boundedWordConst,h,if_true] using wordConst_exact n key c h a
  · have hnot : ¬ wireValue a key n = c := by
      intro he
      exact h (he ▸ wireValue_lt a key n)
    simp [boundedWordConst,h,hnot,Gate.Holds,satisfiesClause]

theorem boundedWordConst_length (n : ℕ) (key : ℕ → ℕ) (c : ℕ) :
    (boundedWordConst n key c).length ≤ n+1 := by
  unfold boundedWordConst
  split <;> simp

def paddedKey (n z : ℕ) (key : ℕ → ℕ) (i : ℕ) : ℕ := if i < n then key i else z

theorem wireValue_pad (a : Assignment) (n z : ℕ) (key : ℕ → ℕ)
    (hz : a z=false) (m : ℕ) (hm : n ≤ m) :
    wireValue a (paddedKey n z key) m = wireValue a key n := by
  induction m,hm using Nat.le_induction with
  | base =>
    apply wireValue_key_congr
    intro i hi
    simp [paddedKey,hi]
  | succ m hm ih =>
    simpa [wireValue,paddedKey,show ¬ m < n by omega,hz] using ih

def paddedWordCopy (width leftWidth rightWidth z : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
  wordCopy width (paddedKey leftWidth z lhs) (paddedKey rightWidth z rhs)

theorem paddedWordCopy_exact (width n m z : ℕ) (lhs rhs : ℕ → ℕ) (a : Assignment)
    (hn : n ≤ width) (hm : m ≤ width) (hz : a z=false) :
    (∀ g ∈ paddedWordCopy width n m z lhs rhs,g.Holds a) ↔
      wireValue a lhs n = wireValue a rhs m := by
  rw [paddedWordCopy,wordCopy_exact,wireValue_pad a n z lhs hz width hn,
    wireValue_pad a m z rhs hz width hm]

/-- The low sum bits match the supplied output word, and overflow is forbidden. -/
def exactSumGates (base n : ℕ) (lhs rhs out : ℕ → ℕ) : List Gate :=
  rippleCircuit false base n lhs rhs ++
    (.pin (rippleCarryWire base n) false :: wordCopy n out (rippleBitWire base))

theorem exactSumGates_length (base n : ℕ) (lhs rhs out : ℕ → ℕ) :
    (exactSumGates base n lhs rhs out).length ≤ 8*n+2 := by
  simp [exactSumGates,length_rippleCircuit]
  omega

private theorem expandedSum (base n : ℕ) (lhs rhs : ℕ → ℕ) (a : Assignment)
    (h : ∀ g ∈ rippleCircuit false base n lhs rhs,g.Holds a) :
    wireValue a (rippleBitWire base) n +
      (if a (rippleCarryWire base n) then 2^n else 0) =
        wireValue a lhs n + wireValue a rhs n := by
  have he := rippleCircuit_add_exact base n lhs rhs a h
  have he' : wireValue a (addOutputWire base n) n = wireValue a (rippleBitWire base) n := by
    apply wireValue_key_congr
    intro i hi
    simp [addOutputWire,hi]
  simpa only [wireValue,he',addOutputWire,lt_irrefl,if_false] using he

theorem exactSumGates_sound (base n : ℕ) (lhs rhs out : ℕ → ℕ) (a : Assignment)
    (h : ∀ g ∈ exactSumGates base n lhs rhs out,g.Holds a) :
    wireValue a out n = wireValue a lhs n + wireValue a rhs n := by
  rw [exactSumGates,List.forall_mem_append,List.forall_mem_cons] at h
  obtain ⟨hr,hNo,hCopy⟩ := h
  have hBits := (wordCopy_exact n out (rippleBitWire base) a).mp hCopy
  have hSum := expandedSum base n lhs rhs a hr
  change a (rippleCarryWire base n)=false at hNo
  simpa [← hBits,hNo] using hSum

theorem exactSumGates_complete (base n : ℕ) (lhs rhs out : ℕ → ℕ) (a : Assignment)
    (hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
    (hO : ∀ i < n, out i < base)
    (hSum : wireValue a out n = wireValue a lhs n + wireValue a rhs n) :
    ∃ b : Assignment, (∀ k, (k < base ∨ base+8*n+1 ≤ k) → b k=a k) ∧
      ∀ g ∈ exactSumGates base n lhs rhs out,g.Holds b := by
  obtain ⟨b,hKeep,hRipple⟩ := rippleCircuit_extends_interval false base n lhs rhs a hL hR
  have hL' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hL i hi)))
  have hR' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hR i hi)))
  have hO' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hO i hi)))
  have hE := expandedSum base n lhs rhs b hRipple
  rw [hL',hR',← hSum,← hO'] at hE
  have hLt := wireValue_lt b out n
  have hCarry : b (rippleCarryWire base n)=false := by
    cases hb : b (rippleCarryWire base n)
    · rfl
    · simp [hb] at hE
      omega
  have hCopy : wireValue b out n = wireValue b (rippleBitWire base) n := by
    simpa [hCarry] using hE.symm
  exact ⟨b,hKeep,(List.forall_mem_append.mpr ⟨hRipple,List.forall_mem_cons.mpr
    ⟨hCarry,(wordCopy_exact n out (rippleBitWire base) b).mpr hCopy⟩⟩)⟩

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- The three action lanes of a slot each carry a presence bit, a write flag,
and two words. The old value is supplied independently by the memory checker. -/
def slotRowPresent (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : ℕ := port n t s (3+5*i) 0

def slotRowWrite (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : ℕ := port n t s (3+5*i+1) 0

def slotRowAddress (n t : ℕ) (s : ℕ × ℕ) (i bit : ℕ) : ℕ := port n t s (3+5*i+2) bit

def slotRowValue (n t : ℕ) (s : ℕ × ℕ) (i bit : ℕ) : ℕ := port n t s (3+5*i+3) bit

def slotRawAction (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : MemoryAccess :=
  ⟨wireValue a (slotRowAddress n t s i) (2^s.2),
    wireValue a (slotRowValue n t s i) (2^s.2), a (slotRowWrite n t s i)⟩

theorem slotView_rawActions (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
    (slotView a n t s).2 =
      ((List.range 3).filter fun i => a (slotRowPresent n t s i)).map (slotRawAction a n t s) := by
  have hAction (i : ℕ) : (portMemory a n t s i).map ObservedAccess.action =
      if a (slotRowPresent n t s i) then some (slotRawAction a n t s i) else none := by
    unfold portMemory slotRowPresent
    split <;> simp_all [slotRawAction,slotRowAddress,slotRowValue,slotRowWrite,
      portWord,wireValue_eq_sum]
  unfold slotView slotRows
  rw [List.map_filterMap]
  change (List.range 3).filterMap (fun i => (portMemory a n t s i).map ObservedAccess.action) = _
  simp_rw [hAction]
  induction List.range 3 with
  | nil => rfl
  | cons i is ih =>
    cases hp : a (slotRowPresent n t s i) <;>
      simp [hp,ih]

def physicalMask (key : ℕ) (i : ℕ) : Bool := key.testBit i

def maskLanes (key : ℕ) : List ℕ := (List.range 3).filter (physicalMask key)

theorem mask_exists (flags : ℕ → Bool) :
    ∃ k < 8, ∀ i < 3, flags i = physicalMask k i := by
  have hEq (i : ℕ) (hi : i < 3) : i=0 ∨ i=1 ∨ i=2 := by omega
  cases h0 : flags 0 <;> cases h1 : flags 1 <;> cases h2 : flags 2
  · refine ⟨0,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp [h0,h1,h2,physicalMask]
  · refine ⟨4,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨2,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨6,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨1,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨5,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨3,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
  · refine ⟨7,by decide,?_⟩
    intro i hi
    rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide

/-- Four literal pins read guard availability and the static mask of physical lanes. -/
def slotPacketShape (n t : ℕ) (s : ℕ × ℕ) (readsInput : Bool) (mask : ℕ) : List Gate :=
  .pin (port n t s 0 0) readsInput ::
    (List.range 3).map (fun i => .pin (slotRowPresent n t s i) (physicalMask mask i))

theorem slotPacketShape_exact (a : Assignment) (n t : ℕ) (s : ℕ × ℕ)
    (readsInput : Bool) (mask : ℕ) :
    (∀ g ∈ slotPacketShape n t s readsInput mask,g.Holds a) ↔
      a (port n t s 0 0) = readsInput ∧
      ∀ i < 3, a (slotRowPresent n t s i) = physicalMask mask i := by
  rw [slotPacketShape,List.forall_mem_cons]
  simp only [List.forall_mem_map,List.mem_range,Gate.Holds]

theorem slotPacketShape_view (a : Assignment) (n t : ℕ) (s : ℕ × ℕ)
    (readsInput : Bool) (mask : ℕ) (h : ∀ g ∈ slotPacketShape n t s readsInput mask,g.Holds a) :
    slotView a n t s =
      (if readsInput then some ((a (port n t s 1 0)).toNat+2*(a (port n t s 2 0)).toNat)
        else none,(maskLanes mask).map (slotRawAction a n t s)) := by
  have hs := (slotPacketShape_exact a n t s readsInput mask).mp h
  apply Prod.ext
  · simp [slotView,portInput,hs.1]
  · rw [slotView_rawActions,maskLanes]
    congr 1
    apply List.filter_congr
    intro i hi
    exact hs.2 i (List.mem_range.mp hi)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

def programField (w : List (List Bool)) (pc field : ℕ) : List Bool :=
  w.getD (2+3*pc+field) []

private theorem progWords_field (prog : List Instr) {pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) (f : ℕ) (hf : f < 3) :
    (progWords prog).getD (3*pc+f) [] = (instrWords op).getD f [] := by
  induction prog generalizing pc with
  | nil => simp at hp
  | cons p prog ih =>
    cases pc with
    | zero =>
      have hEq : p=op := Option.some.inj hp
      subst p
      simpa only [progWords,List.flatMap_cons,Nat.mul_zero,Nat.zero_add] using
        List.getD_append (instrWords op) (progWords prog) [] f (by simpa [instrWords] using hf)
    | succ pc =>
      rw [progWords,List.flatMap_cons,List.getD_eq_getElem?_getD,
        List.getElem?_append_right (by simp [instrWords]; omega)]
      have hNat : 3*(pc+1)+f-(instrWords p).length = 3*pc+f := by simp [instrWords]; omega
      rw [hNat,← List.getD_eq_getElem?_getD]
      exact ih hp

theorem programField_exact {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) {f : ℕ} (hf : f < 3) :
    programField ([unaryWord n,unaryWord t] ++ progWords prog) pc f = (instrWords op).getD f [] := by
  unfold programField
  rw [List.getD_eq_getElem?_getD,List.getElem?_append_right (by simp; omega),List.length_cons,
    List.length_cons,List.length_nil]
  have h : 2+3*pc+f-(0+1+1) = 3*pc+f := by omega
  rw [h,← List.getD_eq_getElem?_getD,progWords_field prog hp f hf]

theorem programField_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc field : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary)
    (hf : ComputableTidilyInPolyTime field e encUnary) :
    ComputableTidilyInPolyTime (fun a => programField (ws a) (pc a) (field a)) e encBits := by
  have hx : ComputableTidilyInPolyTime (fun a => 2+3*pc a+field a) e encUnary := by fun_prop
  exact (listGetD (encA := encBits) []).comp (hw.prod hx)

theorem program_opcode {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) :
    (programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 0).length = instrTag op := by
  rw [programField_exact hp (by decide)]
  simp [instrWords,unaryWord,List.getD]

private theorem encodeNum_bits_aux (b : Bool) (n : Num) (h : n=0 → b=true) :
    Computability.encodeNum (cond b Num.bit1 Num.bit0 n) = b :: Computability.encodeNum n := by
  cases n with
  | zero => have hB := h rfl; subst b; rfl
  | pos v => cases b <;> rfl

theorem binWord_bits (n : ℕ) : binWord n = n.bits := by
  induction n using Nat.binaryRec' with
  | zero => rfl
  | bit b n hBN ih =>
    have hb : (Num.ofNat' n)=0 → b=true := by
      intro h0
      apply hBN
      have hComp := congrArg (fun a : Num => (a : ℕ)) h0
      simpa [Num.ofNat'_eq] using hComp
    change Computability.encodeNum (↑(Nat.bit b n)) = (Nat.bit b n).bits
    rw [← Num.ofNat'_eq,Num.ofNat'_bit,encodeNum_bits_aux b _ hb]
    rw [Num.ofNat'_eq]
    change b::binWord n = (Nat.bit b n).bits
    rw [ih]
    unfold Nat.bits
    rw [Nat.binaryRec_eq]
    exact Or.inr hBN

theorem program_first_arg {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) :
    programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 1 = (instrArgs op).1.bits := by
  rw [programField_exact hp (by decide)]
  exact binWord_bits _

theorem program_second_arg {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) :
    programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 2 = (instrArgs op).2.bits := by
  rw [programField_exact hp (by decide)]
  exact binWord_bits _

theorem program_opcode_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary) :
    ComputableTidilyInPolyTime (fun a => (programField (ws a) (pc a) 0).length) e encUnary :=
  length_bits.comp (programField_poly hw hp (const 0))

theorem program_arg_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc field : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary)
    (hf : ComputableTidilyInPolyTime field e encUnary) :
    ComputableTidilyInPolyTime (fun a => ofBits (programField (ws a) (pc a) (field a))) e encNat :=
  bitsToNat.comp (programField_poly hw hp hf)

theorem program_first_arg_nat {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) :
    ofBits (programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 1) = (instrArgs op).1 := by
  rw [program_first_arg hp]
  exact Nat.foldr_bit_bits _

theorem program_second_arg_nat {prog : List Instr} {n t pc : ℕ} {op : Instr}
    (hp : prog[pc]? = some op) :
    ofBits (programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 2) = (instrArgs op).2 := by
  rw [program_second_arg hp]
  exact Nat.foldr_bit_bits _

def programLength (w : List (List Bool)) : ℕ := (w.length-2)/3

theorem programLength_exact (prog : List Instr) (n t : ℕ) :
    programLength ([unaryWord n,unaryWord t] ++ progWords prog) = prog.length := by
  have hLength : (progWords prog).length = prog.length*3 := by
    induction prog with
    | nil => rfl
    | cons p ps ih =>
      simp only [progWords,List.flatMap_cons,List.length_append,instrWords,
        List.length_cons,List.length_nil] at *
      omega
  unfold programLength
  rw [List.length_append, hLength]
  simp

theorem programLength_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits)) :
    ComputableTidilyInPolyTime (fun a => programLength (ws a)) e encUnary := by
  exact unary_div_poly.comp ((unary_sub.comp (((length encBits).comp hw).prod (const 2))).prod (const 3))

theorem programArgSize_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc field : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary)
    (hf : ComputableTidilyInPolyTime field e encUnary) :
    ComputableTidilyInPolyTime (fun a => (programField (ws a) (pc a) (field a)).length) e encUnary :=
  length_bits.comp (programField_poly hw hp hf)

theorem programArgBit_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc field bit : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary)
    (hf : ComputableTidilyInPolyTime field e encUnary)
    (hb : ComputableTidilyInPolyTime bit e encUnary) :
    ComputableTidilyInPolyTime (fun a =>
      (ofBits (programField (ws a) (pc a) (field a))).testBit (bit a)) e encBool :=
  binary_testBit (program_arg_poly hw hp hf) hb

/-- Static operands have unbounded numerical value. Returning unary is safe only
after capping at an independently polynomially bounded positive parameter. -/
theorem programArgCapped_poly {A : Type} {e : A ↪ List Bool}
    {ws : A → List (List Bool)} {pc field cap : A → ℕ}
    (hw : ComputableTidilyInPolyTime ws e (encList encBits))
    (hp : ComputableTidilyInPolyTime pc e encUnary)
    (hf : ComputableTidilyInPolyTime field e encUnary)
    (hc : ComputableTidilyInPolyTime cap e encUnary) :
    ComputableTidilyInPolyTime (fun a =>
      min (cap a) (ofBits (programField (ws a) (pc a) (field a)))) e encUnary :=
  (ComputableInPolyTime.binary_min_unary' hc.computableInPolyTime
    (program_arg_poly hw hp hf).computableInPolyTime).tidy

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

structure BinaryPort where
  width : ℕ
  bit : ℕ → ℕ

def BinaryPort.value (a : Assignment) (w : BinaryPort) : ℕ := wireValue a w.bit w.width

def BinaryPort.equalGates (z : ℕ) (x y : BinaryPort) : List Gate :=
  paddedWordCopy (max x.width y.width) x.width y.width z x.bit y.bit

theorem BinaryPort.equalGates_exact (z : ℕ) (x y : BinaryPort) (a : Assignment) (hz : a z=false) :
    (∀ g ∈ x.equalGates z y,g.Holds a) ↔ x.value a = y.value a :=
  paddedWordCopy_exact _ _ _ z x.bit y.bit a (Nat.le_max_left _ _) (Nat.le_max_right _ _) hz

def BinaryPort.nonzeroGates (w : BinaryPort) : List Gate :=
  [.assert ((List.range w.width).map (fun i => .Pos (w.bit i)))]

theorem BinaryPort.nonzeroGates_exact (w : BinaryPort) (a : Assignment) :
    (∀ g ∈ w.nonzeroGates,g.Holds a) ↔ w.value a ≠ 0 := by
  have hZero : w.value a = 0 ↔ ∀ i < w.width, a (w.bit i)=false := by
    unfold BinaryPort.value
    rw [← wordConst_exact w.width w.bit 0 (Nat.pow_pos (by decide)) a]
    simp [wordConst,Gate.Holds]
  simp only [BinaryPort.nonzeroGates,List.forall_mem_singleton,Gate.Holds,satisfiesClause_iff]
  constructor
  · rintro ⟨lit,hlit,hs⟩ he
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hlit
    change a (w.bit i)=true at hs
    rw [(hZero.mp he) i (List.mem_range.mp hi)] at hs
    contradiction
  · intro hn
    classical
    have hE : ∃ i < w.width, a (w.bit i)=true := by
      by_contra! ha
      exact hn (hZero.mpr (fun i hi => Bool.eq_false_iff.mpr (ha i hi)))
    obtain ⟨i,hi,hs⟩ := hE
    exact ⟨.Pos (w.bit i),List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩,hs⟩

def accessPatternGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (i : ℕ) (p : PacketAccessPattern) : List Gate :=
  .pin (slotRowWrite n t s i) p.writes ::
    (BinaryPort.mk (2^s.2) (slotRowAddress n t s i)).equalGates z (words p.address) ++
    (BinaryPort.mk (2^s.2) (slotRowValue n t s i)).equalGates z (words p.value)

theorem accessPatternGates_exact (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (i : ℕ) (p : PacketAccessPattern) (a : Assignment) (packet : Packet)
    (hz : a z=false) (ha : (words p.address).value a = p.address.eval packet)
    (hv : (words p.value).value a = p.value.eval packet) :
    (∀ g ∈ accessPatternGates n t z s words i p,g.Holds a) ↔
      slotRawAction a n t s i = p.eval packet := by
  rw [accessPatternGates,List.forall_mem_append,List.forall_mem_cons,
    BinaryPort.equalGates_exact _ _ _ _ hz,BinaryPort.equalGates_exact _ _ _ _ hz,
    ha,hv,and_assoc]
  simp only [Gate.Holds]
  change
    (a (slotRowWrite n t s i) = p.writes ∧
      wireValue a (slotRowAddress n t s i) (2^s.2) = p.address.eval packet ∧
      wireValue a (slotRowValue n t s i) (2^s.2) = p.value.eval packet) ↔ _
  simp only [slotRawAction,PacketAccessPattern.eval,MemoryAccess.mk.injEq]
  tauto

/-- A presence mask fixes the order of used physical lanes. A branch with a
different expected lane count is impossible. -/
def accessListGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort) :
    List ℕ → List PacketAccessPattern → List Gate
  | [],[] => []
  | i::is,p::ps => accessPatternGates n t z s words i p ++ accessListGates n t z s words is ps
  | _,_ => [.assert []]

theorem accessListGates_exact (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (is : List ℕ) (ps : List PacketAccessPattern) (a : Assignment) (packet : Packet)
    (hz : a z=false) (hw : ∀ p ∈ ps, (words p.address).value a = p.address.eval packet ∧
      (words p.value).value a = p.value.eval packet) :
    (∀ g ∈ accessListGates n t z s words is ps,g.Holds a) ↔
      is.map (slotRawAction a n t s) = ps.map (PacketAccessPattern.eval packet) := by
  induction is generalizing ps with
  | nil =>
    cases ps <;> simp [accessListGates,Gate.Holds,satisfiesClause]
  | cons i is ih =>
    cases ps with
    | nil => simp [accessListGates,Gate.Holds,satisfiesClause]
    | cons p ps =>
      have hd := hw p List.mem_cons_self
      rw [accessListGates,List.forall_mem_append,
        accessPatternGates_exact _ _ _ _ _ _ _ _ _ hz hd.1 hd.2,
        ih ps (fun q hq => hw q (List.mem_cons_of_mem _ hq))]
      simp

def slotPacket (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (cost : ℕ) : Packet :=
  let p := slotView a n t s
  ⟨p.1,p.2,cost⟩

def packetFormatGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (m : PacketPattern) (mask : ℕ) : List Gate :=
  slotPacketShape n t s m.readsInput mask ++
  accessListGates n t z s words (maskLanes mask) m.accesses ++
  (match m.zero with
  | none => []
  | some true => boundedWordConst (words (.operand 0)).width (words (.operand 0)).bit 0
  | some false => (words (.operand 0)).nonzeroGates)

theorem packetFormatGates_sound (n t z : ℕ) (s : ℕ × ℕ)
    (words : PacketExpr → BinaryPort) (m : PacketPattern) (mask : ℕ) (a : Assignment) (cost : ℕ)
    (hz : a z=false)
    (hw : ∀ p ∈ m.accesses,
      (words p.address).value a = p.address.eval (slotPacket a n t s cost) ∧
      (words p.value).value a = p.value.eval (slotPacket a n t s cost))
    (hOp : (words (.operand 0)).value a = (slotPacket a n t s cost).operand 0)
    (h : ∀ g ∈ packetFormatGates n t z s words m mask,g.Holds a) :
    let p := slotPacket a n t s cost
    p.input = (if m.readsInput then some (PacketExpr.eval p .symbol) else none) ∧
    p.accesses = m.accesses.map (PacketAccessPattern.eval p) ∧
    ∀ flag, m.zero=some flag → (p.operand 0=0 ↔ flag=true) := by
  rw [packetFormatGates,List.forall_mem_append,List.forall_mem_append] at h
  obtain ⟨⟨hShape,hAccess⟩,hZero⟩ := h
  have hV := slotPacketShape_view a n t s m.readsInput mask hShape
  have hInput := congrArg Prod.fst hV
  have hRows := congrArg Prod.snd hV
  have hAs := (accessListGates_exact n t z s words _ _ a (slotPacket a n t s cost) hz hw).mp hAccess
  refine ⟨?_,hRows.trans hAs,?_⟩
  · change (slotView a n t s).1 = _
    cases h : m.readsInput <;> simp [h,PacketExpr.eval,slotPacket,hInput]
  · intro flag hFlag
    rw [hFlag] at hZero
    cases flag
    · rw [BinaryPort.nonzeroGates_exact,hOp] at hZero
      simpa using hZero
    · rw [boundedWordConst_exact] at hZero
      change (words (.operand 0)).value a = 0 at hZero
      rw [hOp] at hZero
      simp [hZero]


theorem packetFormatGates_complete (n t z : ℕ) (s : ℕ × ℕ)
    (words : PacketExpr → BinaryPort) (m : PacketPattern) (a : Assignment) (cost : ℕ)
    (hz : a z=false)
    (hw : ∀ p ∈ m.accesses,
      (words p.address).value a = p.address.eval (slotPacket a n t s cost) ∧
      (words p.value).value a = p.value.eval (slotPacket a n t s cost))
    (hOp : (words (.operand 0)).value a = (slotPacket a n t s cost).operand 0)
    (h : let p := slotPacket a n t s cost
      p.input = (if m.readsInput then some (PacketExpr.eval p .symbol) else none) ∧
      p.accesses = m.accesses.map (PacketAccessPattern.eval p) ∧
      ∀ flag, m.zero=some flag → (p.operand 0=0 ↔ flag=true)) :
    ∃ mask < 8, ∀ g ∈ packetFormatGates n t z s words m mask,g.Holds a := by
  let p := slotPacket a n t s cost
  change p.input = _ ∧ p.accesses = _ ∧ _ at h
  obtain ⟨mask,hM,hFlags⟩ := mask_exists (fun i => a (slotRowPresent n t s i))
  have hIn : a (port n t s 0 0) = m.readsInput := by
    have hP := h.1
    change portInput a n t s = _ at hP
    cases hA : a (port n t s 0 0) <;> cases hR : m.readsInput <;>
      simp_all [portInput]
  have hShape := (slotPacketShape_exact a n t s m.readsInput mask).mpr ⟨hIn,hFlags⟩
  have hRows := congrArg Prod.snd (slotPacketShape_view a n t s m.readsInput mask hShape)
  have hAccess := (accessListGates_exact n t z s words (maskLanes mask) m.accesses a p hz hw).mpr
    (hRows.symm.trans h.2.1)
  refine ⟨mask,hM,?_⟩
  rw [packetFormatGates,List.forall_mem_append,List.forall_mem_append]
  refine ⟨⟨hShape,hAccess⟩,?_⟩
  change (words (.operand 0)).value a = p.operand 0 at hOp
  cases hZero : m.zero with
  | none => simp
  | some flag =>
    cases flag
    · rw [BinaryPort.nonzeroGates_exact,hOp]
      simpa using h.2.2 false hZero
    · rw [boundedWordConst_exact]
      change (words (.operand 0)).value a = 0
      rw [hOp]
      exact (h.2.2 true hZero).mpr rfl

theorem accessPatternGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (i : ℕ) (p : PacketAccessPattern) (w : ℕ)
    (hs : 2^s.2 ≤ w) (ha : (words p.address).width ≤ w) (hv : (words p.value).width ≤ w) :
    (accessPatternGates n t z s words i p).length ≤ 1+2*w := by
  have h1 := max_le hs ha
  have h2 := max_le hs hv
  simp only [accessPatternGates,List.length_append,List.length_cons,
    BinaryPort.equalGates,paddedWordCopy,length_wordCopy]
  omega

theorem accessListGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (is : List ℕ) (ps : List PacketAccessPattern) (w : ℕ) (hs : 2^s.2 ≤ w)
    (hFit : ∀ p ∈ ps, (words p.address).width ≤ w ∧ (words p.value).width ≤ w) :
    (accessListGates n t z s words is ps).length ≤ 1+is.length*(1+2*w) := by
  induction is generalizing ps with
  | nil =>
    cases ps <;> simp [accessListGates]
  | cons i is ih =>
    cases ps with
    | nil => simp [accessListGates]
    | cons p ps =>
      obtain ⟨ha,hv⟩ := hFit p List.mem_cons_self
      have h1 := accessPatternGates_length n t z s words i p w hs ha hv
      have h2 := ih ps (fun q hq => hFit q (List.mem_cons_of_mem _ hq))
      simp only [accessListGates,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul]
      omega

theorem packetFormatGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
    (m : PacketPattern) (mask w : ℕ) (hs : 2^s.2 ≤ w)
    (hFit : ∀ p ∈ m.accesses, (words p.address).width ≤ w ∧ (words p.value).width ≤ w)
    (h0 : (words (.operand 0)).width ≤ w) :
    (packetFormatGates n t z s words m mask).length ≤ 9+7*w := by
  have hShape : (slotPacketShape n t s m.readsInput mask).length = 4 := by
    simp [slotPacketShape]
  have hML : (maskLanes mask).length ≤ 3 := by
    simpa [maskLanes] using List.length_filter_le (p := physicalMask mask) (List.range 3)
  have hData := accessListGates_length n t z s words (maskLanes mask) m.accesses w hs hFit
  have hMono := Nat.mul_le_mul_right (1+2*w) hML
  have hConst := boundedWordConst_length (words (.operand 0)).width (words (.operand 0)).bit 0
  simp only [packetFormatGates,List.length_append,hShape]
  cases h : m.zero with
  | none => simp [h] <;> omega
  | some b =>
    cases b <;> simp [h,BinaryPort.nonzeroGates] <;> omega

end CNFEncComplexity.Robson

/- robson-gate-rename -/

namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime

def renameLiteralCode (name : ℕ → ℕ) (r : ℕ) : ℕ := 2*name (r/2)+r%2

theorem renameLiteralCode_exact (name : ℕ → ℕ) (l : Literal) :
    renameLiteralCode name (literalN l) = literalN (Literal.rename name l) := by
  cases l with
  | Neg r => simp [renameLiteralCode,literalN,Literal.rename,show (2*r)/2=r by omega,show (2*r)%2=0 by omega]
  | Pos r => simp [renameLiteralCode,literalN,Literal.rename,show (2*r+1)/2=r by omega,show (2*r+1)%2=1 by omega]

def renamedCode (name : ℕ → ℕ) (r : List ℕ) : List ℕ :=
  let tag := r.headD 0
  tag :: (if tag = 8 then r.tail.map (renameLiteralCode name) else r.tail.map name)

theorem renamedCode_exact (name : ℕ → ℕ) (g : Gate) :
    (g.rename name).code = renamedCode name g.code := by
  cases g with
  | pin o b => cases b <;> rfl
  | copy | inv | conj | disj | parity | mux => rfl
  | assert c =>
    simp only [Gate.rename,Gate.code,renamedCode,List.headD_cons,if_pos rfl,List.tail_cons,
      clauseN,List.map_map,List.cons.injEq,true_and]
    apply List.map_congr_left
    intro lit _
    exact (renameLiteralCode_exact name lit).symm

private theorem gateCode_poly : ComputableTidilyInPolyTime Gate.code gateEnc (encList encUnary) :=
  (id' (encIn:=gateEnc)).of_enc_eq fun _ => rfl

theorem gateRename_poly {A : Type} {e : A ↪ List Bool} {name : A → ℕ → ℕ}
    (hName : ComputableTidilyInPolyTime (fun p : A×ℕ => name p.1 p.2)
      (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun p : A×Gate => p.2.rename (name p.1))
      (encPair e gateEnc) gateEnc := by
  let ep := encPair e gateEnc
  let ei := encPair ep encUnary
  have hA := fst e gateEnc
  have hGate := snd e gateEnc
  have hCode := gateCode_poly.comp hGate
  have hTag := (headD (encA:=encUnary) 0).comp hCode
  have hTail := (listTail encUnary).comp hCode
  have hPref := fst ep encUnary
  have hIdx := snd ep encUnary
  have hN := hName.comp ((hA.comp hPref).prod hIdx)
  have hDiv : ComputableTidilyInPolyTime (fun p : (A×Gate)×ℕ => p.2 / 2) ei encUnary :=
    unary_div_poly.comp (hIdx.prod (const 2))
  have hMod : ComputableTidilyInPolyTime (fun p : (A×Gate)×ℕ => p.2 % 2) ei encUnary :=
    unary_mod_poly.comp (hIdx.prod (const 2))
  have hNL := hName.comp ((hA.comp hPref).prod hDiv)
  have hLiteral := unary_add.comp ((unary_mul.comp ((const 2).prod hNL)).prod hMod)
  have hTailN := mapWithInput (f:=fun (p : A×Gate) k => name p.1 k) hTail hN
  have hTailL := mapWithInput (f:=fun (p : A×Gate) k => renameLiteralCode (name p.1) k) hTail hLiteral
  have hPred := unary_beq hTag (const 8)
  apply gate_of_fields (code:=fun p : A×Gate => renamedCode (name p.1) p.2.code)
  · have hh := cons' hTag (hPred.ite' hTailL hTailN)
    convert hh using 1
    funext p
    simp [renamedCode,Function.comp_def,beq_iff_eq]
  · intro p
    exact renamedCode_exact _ _

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

/-- Keep shared names and inject private names into the chosen residue class. -/
def componentWire (S : ℕ) (part : Fin 3) (r : ℕ) : ℕ :=
  if r < S then r else S+3*(r-S)+part.val

theorem componentWire_owns (S : ℕ) (part : Fin 3) (r : ℕ) : owns S part (componentWire S part r) := by
  by_cases h : r < S
  · exact .inl (by simpa [componentWire,h] using h)
  · right
    simp [componentWire,h,Nat.add_assoc,Nat.add_mod,Nat.mod_eq_of_lt part.isLt]

def componentUnwire (S : ℕ) (r : ℕ) : ℕ :=
  if r < S then r else S+(r-S)/3

theorem componentUnwire_wire (S : ℕ) (part : Fin 3) (r : ℕ) :
    componentUnwire S (componentWire S part r) = r := by
  by_cases h : r < S
  · simp [componentWire,componentUnwire,h]
  · have hh : ¬ S+3*(r-S)+part.val < S := by omega
    have hs : (S+3*(r-S)+part.val)-S=3*(r-S)+part.val := by omega
    have hp : part.val/3=0 := Nat.div_eq_of_lt part.isLt
    rw [componentWire,if_neg h,componentUnwire,if_neg hh,hs,Nat.mul_add_div (by decide),hp]
    omega

theorem componentRename_extends (S : ℕ) (part : Fin 3) (gates : List Gate) (a : Assignment) :
    ExtendsWith S (gates.map (Gate.rename (componentWire S part))) a ↔ ExtendsWith S gates a := by
  constructor
  · rintro ⟨b,hKeep,hG⟩
    refine ⟨b∘componentWire S part,fun r hr => ?_,(renamedCircuit_correct _ _ _).1 hG⟩
    simpa [Function.comp_def,componentWire,hr] using hKeep r hr
  · rintro ⟨b,hKeep,hG⟩
    refine ⟨b∘componentUnwire S,fun r hr => ?_,(renamedCircuit_correct _ _ _).2 ?_⟩
    · simpa [Function.comp_def,componentUnwire,hr] using hKeep r hr
    · simpa [Function.comp_def,componentUnwire_wire] using hG

theorem componentRename_owns (S : ℕ) (part : Fin 3) (gs : List Gate)
    (g : Gate) (hg : g ∈ gs.map (Gate.rename (componentWire S part))) (r : ℕ)
    (hr : r ∈ CNFEncComplexity.Robson.Gate.names g) : owns S part r := by
  obtain ⟨g',_,rfl⟩ := List.mem_map.mp hg
  change r ∈ RobsonCNF.Gate.names (g'.rename (componentWire S part)) at hr
  rw [renamedNames] at hr
  obtain ⟨r',_,rfl⟩ := List.mem_map.mp hr
  exact componentWire_owns _ _ _

theorem componentRename_poly {A : Type} {e : A ↪ List Bool} (part : Fin 3)
    {S : A → ℕ} {gs : A → List Gate} (hS : ComputableTidilyInPolyTime S e encUnary)
    (hgs : ComputableTidilyInPolyTime gs e (encList gateEnc)) :
    ComputableTidilyInPolyTime (fun a => (gs a).map (Gate.rename (componentWire (S a) part)))
      e (encList gateEnc) := by
  have hPrefix := fst e encUnary
  have hBase := hS.comp hPrefix
  have hr := snd e encUnary
  have hCond := unary_lt' hr hBase
  have hRest := unary_sub.comp (hr.prod hBase)
  have hNum := unary_mul.comp ((const 3).prod hRest)
  have hEnd := unary_add.comp ((unary_add.comp (hBase.prod hNum)).prod (const part.val))
  have hName : ComputableTidilyInPolyTime
      (fun p : A×ℕ => componentWire (S p.1) part p.2) (encPair e encUnary) encUnary := by
    simpa only [componentWire,decide_eq_true_eq,Function.comp_def] using hCond.ite' hr hEnd
  exact mapWithInput hgs (gateRename_poly (e := e) (name := fun a => componentWire (S a) part) hName)

end CNFEncComplexity.Robson

/- shared port name bounds -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

theorem sharedLimit_poly {A : Type} {e : A ↪ List Bool} {n t : A → ℕ}
    (hn : ComputableTidilyInPolyTime n e encUnary) (ht : ComputableTidilyInPolyTime t e encUnary) :
    ComputableTidilyInPolyTime (fun a => sharedLimit (n a) (t a)) e encUnary := by
  have hH := layoutHeight_poly.comp ht
  have hW := layoutHorizon_poly.comp ht
  have hA := unary_add.comp (hH.prod (const 1))
  have hB := unary_mul.comp (hW.prod hA)
  have hC := unary_mul.comp (hB.prod (const 19))
  have hD := unary_mul.comp (hC.prod hW)
  exact unary_add.comp (hn.prod hD)

end CNFEncComplexity.Robson

/- formula compiler -/

/- robson-trace-kernel -/

namespace CNFEncComplexity.RobsonCNF

open CookLevin Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime

/-- Intermediate formula syntax with literals represented in unary, matching the
encoding used to feed formulas to the SAT language. -/
def unaryFormulaEnc : Formula ↪ List Bool :=
  (⟨formulaN,formulaN_injective⟩ : Formula ↪ List (List Nat)).trans
    (encList (encList encUnary))

def cookFormulaEnc : Formula ↪ List Bool :=
  ⟨encodeFormula,encodeFormula_injective⟩

private theorem formatNat_eq (n : ℕ) : CookLevin.encodeNat n = List.replicate n true ++ [false] := by
  induction n with
  | zero => rfl
  | succ n ih =>
    rw [CookLevin.encodeNat,List.replicate_succ,ih,List.cons_append]

private theorem formatNat :
    ComputableTidilyInPolyTime (fun n => true :: CookLevin.encodeNat n) encUnary encBits := by
  have h := bitsCons (const true) (bitsAppend (bitsReplicate true) (const [false]))
  simpa only [formatNat_eq] using h

private theorem formatList :
    ComputableTidilyInPolyTime (fun l => true :: CookLevin.encodeListNat l)
      (encList encUnary) encBits := by
  have hb := bitsFlatten ((map formatNat).comp (id' (encIn := encList encUnary)))
  have he (l : List ℕ) :
      CookLevin.encodeListNat l = (l.map fun n => true :: CookLevin.encodeNat n).flatten ++ [false] := by
    simpa only [List.map_id, List.flatten_eq_flatMap, List.flatMap_map, id_eq] using
      CookLevin.encodeListNat_map id l
  have h := bitsCons (const true) (bitsAppend hb (const [false]))
  simpa only [he,Function.comp_apply,id_eq] using h

/-- Serialize explicit unary literal lists into Cook–Levin's exact bit format. -/
theorem encodeFormulaN_polytime :
    ComputableTidilyInPolyTime CookLevin.encodeFormulaN (encList (encList encUnary)) encBits := by
  have hb := bitsFlatten ((map formatList).comp (id' (encIn := encList (encList encUnary))))
  have he (l : List (List ℕ)) :
      CookLevin.encodeFormulaN l = (l.map fun w => true :: CookLevin.encodeListNat w).flatten ++ [false] := by
    simpa only [List.map_id, List.flatten_eq_flatMap, List.flatMap_map, id_eq] using
      CookLevin.encodeFormulaN_map id l
  have h := bitsAppend hb (const [false])
  have he' : CookLevin.encodeFormulaN = (fun l => (l.map fun w =>
      true :: CookLevin.encodeListNat w).flatten ++ [false]) := funext he
  rw [he']
  exact h

/-- Transfer a verified formula constructor on explicit unary literals to the
required Cook–Levin formula encoding without a change to its mathematical output. -/
theorem to_cookFormulaEnc {α : Type} {encIn : α ↪ List Bool} {build : α → Formula}
    (h : ComputableInPolyTime build encIn unaryFormulaEnc) :
    ComputableInPolyTime build encIn cookFormulaEnc := by
  have hlist : ComputableTidilyInPolyTime (fun x => formulaN (build x)) encIn
      (encList (encList encUnary)) := h.tidy.of_enc_eq (fun x => rfl)
  exact ((encodeFormulaN_polytime.comp hlist).of_enc_eq (fun x => rfl)).computableInPolyTime

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.RobsonCNF

open CookLevin Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime

/-- The constructor tag precedes its wire numbers. A raw assertion stores its
literal numbers directly after the tag. -/
private abbrev Recipe := List (List (ℕ × ℕ))
private abbrev encFields := encList encUnary
private abbrev encFormulaFields := encList encFields
private abbrev encLiteralRecipe := encPair encUnary encUnary
private abbrev encClauseRecipe := encList encLiteralRecipe
private abbrev encRecipe := encList encClauseRecipe

/-- Each recipe literal specifies its index in the constructor record and its sign. -/
private def recipes : List Recipe := [
  [[(1,0)]],
  [[(1,1)]],
  [[(1,0),(2,1)],[(1,1),(2,0)]],
  [[(1,0),(2,0)],[(1,1),(2,1)]],
  [[(1,0),(2,1)],[(1,0),(3,1)],[(1,1),(2,0),(3,0)]],
  [[(1,1),(2,0)],[(1,1),(3,0)],[(1,0),(2,1),(3,1)]],
  [[(1,1),(2,0),(3,1)],[(1,1),(2,1),(3,0)],[(1,0),(2,1),(3,1)],[(1,0),(2,0),(3,0)]],
  [[(2,0),(1,0),(3,1)],[(2,0),(1,1),(3,0)],[(2,1),(1,0),(4,1)],[(2,1),(1,1),(4,0)]]
]

private def lookup (l : List ℕ) (i : ℕ) : ℕ :=
  (l[i]?).getD 0

private def buildLiteral (l : List ℕ) (spec : ℕ × ℕ) : ℕ :=
  2*lookup l spec.1+spec.2

private def buildClause (l : List ℕ) (spec : List (ℕ × ℕ)) : List ℕ :=
  spec.map (buildLiteral l)

private def buildClauses (l : List ℕ) : List (List ℕ) :=
  if lookup l 0 < 8 then
    ((recipes[lookup l 0]?).getD []).map (buildClause l)
  else [l.drop 1]

private theorem buildClauses_exact (g : Gate) :
    buildClauses g.code = formulaN g.compile := by
  cases g with
  | pin out b => cases b <;> rfl
  | copy => rfl
  | inv => rfl
  | conj => rfl
  | disj => rfl
  | parity => rfl
  | mux => rfl
  | assert => rfl

private theorem lookup_poly {α : Type} {input : α ↪ List Bool} {l : α → List ℕ} {i : α → ℕ}
    (hl : ComputableTidilyInPolyTime l input encFields)
    (hi : ComputableTidilyInPolyTime i input encUnary) :
    ComputableTidilyInPolyTime (fun x => lookup (l x) (i x)) input encUnary :=
  (optionGetD encUnary).comp ((ComputableTidilyInPolyTime.getElem? hl hi).prod (const 0))

private theorem buildLiteral_poly : ComputableTidilyInPolyTime
    (fun p : List ℕ × (ℕ × ℕ) => buildLiteral p.1 p.2)
    (encPair encFields encLiteralRecipe) encUnary := by
  have hl := fst encFields encLiteralRecipe
  have hs := snd encFields encLiteralRecipe
  have hlook := lookup_poly hl hs.fst'
  exact unary_add.comp ((unary_mul.comp ((const 2).prod hlook)).prod hs.snd')

private theorem buildClause_poly : ComputableTidilyInPolyTime
    (fun p : List ℕ × List (ℕ × ℕ) => buildClause p.1 p.2)
    (encPair encFields encClauseRecipe) encFields :=
  mapWith buildLiteral_poly (fst _ _) (snd _ _)

private theorem recipe_poly : ComputableTidilyInPolyTime
    (fun l : List ℕ => (recipes[lookup l 0]?).getD [])
    encFields encRecipe :=
  (optionGetD encRecipe).comp
    ((ComputableTidilyInPolyTime.getElem? (encL := encList encRecipe) (const recipes) (lookup_poly (id' (encIn := encFields)) (const 0))).prod
      (const []))

private theorem buildClauses_poly : ComputableTidilyInPolyTime buildClauses encFields encFormulaFields := by
  have hi := id' (encIn := encFields)
  have htag := lookup_poly hi (const 0)
  have hbranch := unary_lt' htag (const 8)
  have hy := mapWith buildClause_poly hi recipe_poly
  have hn := cons' (listDropWithInput hi (const 1)) (const [])
  convert hbranch.ite' hy hn using 1
  funext x
  simp [buildClauses]

theorem compile_polytime :
    ComputableInPolyTime compile (encList gateEnc) unaryFormulaEnc := by
  have hcode : ComputableTidilyInPolyTime Gate.code gateEnc encFields :=
    ComputableTidilyInPolyTime.of_eq (fun _ => rfl)
  have hGate : ComputableTidilyInPolyTime (fun g : Gate => buildClauses g.code)
      gateEnc encFormulaFields := buildClauses_poly.comp hcode
  have hPair : ComputableTidilyInPolyTime (fun p : List Gate × Gate => buildClauses p.2.code)
      (encPair (encList gateEnc) gateEnc) encFormulaFields := hGate.comp (snd _ _)
  have hs := flatMapWithInput (f := fun (_ : List Gate) (g : Gate) => buildClauses g.code)
    (id' (encIn := encList gateEnc)) hPair
  apply ComputableTidilyInPolyTime.computableInPolyTime
  refine hs.of_enc_eq (fun gs => ?_)
  change encFormulaFields (formulaN (compile gs)) = encFormulaFields (gs.flatMap (buildClauses ∘ Gate.code))
  congr 1
  simp [compile, formulaN, List.map_flatMap, buildClauses_exact, Function.comp_def]

end CNFEncComplexity.RobsonCNF

/- literal encoding -/

namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime
variable {A : Type} {input : A ↪ List Bool}

theorem negative_poly {x : A → ℕ} (hx : ComputableTidilyInPolyTime x input encUnary) :
    ComputableTidilyInPolyTime (fun a => literalN (.Neg (x a))) input encUnary :=
  unary_mul.comp ((const 2).prod hx)

theorem positive_poly {x : A → ℕ} (hx : ComputableTidilyInPolyTime x input encUnary) :
    ComputableTidilyInPolyTime (fun a => literalN (.Pos (x a))) input encUnary :=
  unary_add.comp ((negative_poly hx).prod (const 1))

theorem assert2_poly {x y : A → Literal}
    (hx : ComputableTidilyInPolyTime (fun a => literalN (x a)) input encUnary)
    (hy : ComputableTidilyInPolyTime (fun a => literalN (y a)) input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.assert [x a,y a]) input gateEnc :=
  gate_assert (cons' hx (cons' hy (const [])))

theorem assert3_poly {x y z : A → Literal}
    (hx : ComputableTidilyInPolyTime (fun a => literalN (x a)) input encUnary)
    (hy : ComputableTidilyInPolyTime (fun a => literalN (y a)) input encUnary)
    (hz : ComputableTidilyInPolyTime (fun a => literalN (z a)) input encUnary) :
    ComputableTidilyInPolyTime (fun a => Gate.assert [x a,y a,z a]) input gateEnc :=
  gate_assert (cons' hx (cons' hy (cons' hz (const []))))

end CNFEncComplexity.RobsonCNF

/- framed binary ports -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def BinaryPort.Below (w : BinaryPort) (limit : ℕ) : Prop :=
  ∀ i < w.width, w.bit i < limit

def BinaryPort.InFrame (w : BinaryPort) (common lo hi : ℕ) : Prop :=
  ∀ i < w.width, w.bit i < common ∨ lo ≤ w.bit i ∧ w.bit i < hi

def GateFrame (gs : List Gate) (common lo hi : ℕ) : Prop :=
  ∀ g ∈ gs, ∀ r ∈ g.names, r < common ∨ lo ≤ r ∧ r < hi

def GateSat (a : Assignment) (gs : List Gate) : Prop :=
  ∀ g ∈ gs, g.Holds a

def Keeps (a b : Assignment) (lo hi : ℕ) : Prop :=
  ∀ k, k < lo ∨ hi ≤ k → b k = a k

theorem BinaryPort.value_congr (w : BinaryPort) (a b : Assignment)
    (h : ∀ i < w.width, a (w.bit i) = b (w.bit i)) : w.value a = w.value b :=
  wireValue_congr h

theorem GateSat.append {a : Assignment} {g h : List Gate} :
    GateSat a (g++h) ↔ GateSat a g ∧ GateSat a h :=
  List.forall_mem_append

theorem GateFrame.append {g h : List Gate} {common lo hi : ℕ} :
    GateFrame (g++h) common lo hi ↔ GateFrame g common lo hi ∧ GateFrame h common lo hi := by
  exact List.forall_mem_append

theorem GateFrame.mono {g : List Gate} {p lo hi p' lo' hi' : ℕ}
    (h : GateFrame g p lo hi) (hp : p ≤ p') (hl : lo' ≤ lo) (hh : hi ≤ hi') :
    GateFrame g p' lo' hi' := by
  intro b hb i hi'
  rcases h b hb i hi' with h | ⟨h1,h2⟩
  · exact .inl (h.trans_le hp)
  · exact .inr ⟨hl.trans h1,h2.trans_le hh⟩

theorem BinaryPort.InFrame.mono {w : BinaryPort} {p lo hi p' lo' hi' : ℕ}
    (h : w.InFrame p lo hi) (hp : p ≤ p') (hl : lo' ≤ lo) (hh : hi ≤ hi') :
    w.InFrame p' lo' hi' := by
  intro i hi'
  rcases h i hi' with h | ⟨h1,h2⟩
  · exact .inl (h.trans_le hp)
  · exact .inr ⟨hl.trans h1,h2.trans_le hh⟩

theorem BinaryPort.InFrame.below {w : BinaryPort} {p lo hi : ℕ}
    (h : w.InFrame p lo hi) (hp : p ≤ hi) : w.Below hi := by
  intro i hi'
  rcases h i hi' with h | ⟨_,h⟩
  · exact h.trans_le hp
  · exact h

theorem GateSat.congr_framed {a b : Assignment} {gs : List Gate} {common lo hi : ℕ}
    (h : GateSat a gs) (hf : GateFrame gs common lo hi)
    (he : ∀ i, i < common ∨ lo ≤ i ∧ i < hi → a i = b i) : GateSat b gs := by
  intro g hg
  exact (g.holds_congr a b (fun i hi => he i (hf g hg i hi))).mp (h g hg)

theorem Keeps.trans {a b c : Assignment} {l u v : ℕ} (h : Keeps a b l u)
    (h' : Keeps b c u v) (hl : l ≤ u) (hu : u ≤ v) : Keeps a c l v := by
  intro i hi
  have hi₁ : i < l ∨ u ≤ i := by omega
  have hi₂ : i < u ∨ v ≤ i := by omega
  rw [h' i hi₂,h i hi₁]

def constantPort (z o n c : ℕ) : BinaryPort :=
  ⟨n, fun i => if c.testBit i then o else z⟩

theorem constantPort_value {a : Assignment} {z o n c : ℕ}
    (hz : a z = false) (ho : a o = true) (hc : c < 2^n) :
    (constantPort z o n c).value a = c := by
  unfold BinaryPort.value
  rw [wireValue_eq_bitString]
  have hh : (fun i : Fin n => a ((constantPort z o n c).bit i.val)) =
      (Cslib.BitString.equivFin n).symm ⟨c,hc⟩ := by
    funext i
    rw [Cslib.BitString.equivFin_symm_apply]
    simp only [constantPort]
    cases h : c.testBit i.val <;> simp [h,hz,ho]
  change ((Cslib.BitString.equivFin n) (fun i => a ((constantPort z o n c).bit i.val))).val = c
  rw [hh,Equiv.apply_symm_apply]

theorem constantPort_frame {z o n c p lo hi : ℕ} (hz : z < p) (ho : o < p) :
    (constantPort z o n c).InFrame p lo hi := by
  intro i _
  have h : (if c.testBit i then o else z) < p := by split <;> assumption
  exact .inl h

def cappedPort (z o n c : ℕ) : BinaryPort :=
  constantPort z o (n+1) (min c (2^n))

theorem cappedPort_value {a : Assignment} {z o n c : ℕ}
    (hz : a z = false) (ho : a o = true) :
    (cappedPort z o n c).value a = min c (2^n) := by
  apply constantPort_value hz ho
  exact (min_le_right _ _).trans_lt (Nat.pow_lt_pow_right (by decide) (Nat.lt_succ_self _))

def BinaryPort.padded (w : BinaryPort) (z n : ℕ) : BinaryPort :=
  ⟨n,paddedKey w.width z w.bit⟩

theorem BinaryPort.padded_value (w : BinaryPort) {a : Assignment} {z n : ℕ}
    (hz : a z=false) (hn : w.width ≤ n) :
    (w.padded z n).value a = w.value a :=
  wireValue_pad a _ _ _ hz _ hn

theorem BinaryPort.padded_frame {w : BinaryPort} {z n common lo hi : ℕ}
    (h : w.InFrame common lo hi) (hz : z < common) :
    (w.padded z n).InFrame common lo hi := by
  intro i _
  change (if i < w.width then w.bit i else z) < common ∨
    lo ≤ (if i < w.width then w.bit i else z) ∧ (if i < w.width then w.bit i else z) < hi
  split
  · exact h _ (by assumption)
  · exact .inl hz

def BinaryPort.addWidth (x y : BinaryPort) : ℕ := max x.width y.width

def BinaryPort.addPort (b : ℕ) (x y : BinaryPort) : BinaryPort :=
  ⟨x.addWidth y+1,addOutputWire b (x.addWidth y)⟩

def BinaryPort.addGates (z b : ℕ) (x y : BinaryPort) : List Gate :=
  let k := x.addWidth y
  rippleCircuit false b k (x.padded z k).bit (y.padded z k).bit

def BinaryPort.addEnd (b : ℕ) (x y : BinaryPort) : ℕ := b+8*x.addWidth y+1

theorem BinaryPort.addPort_names (b : ℕ) (x y : BinaryPort) {i : ℕ}
    (hi : i < (x.addPort b y).width) :
    b ≤ (x.addPort b y).bit i ∧ (x.addPort b y).bit i < x.addEnd b y := by
  simp only [BinaryPort.addPort,BinaryPort.addEnd,addOutputWire,rippleCarryWire,rippleBitWire] at hi ⊢
  split <;> omega

theorem BinaryPort.addGates_exact (z b : ℕ) (x y : BinaryPort) (a : Assignment)
    (hz : a z=false) (h : GateSat a (x.addGates z b y)) :
    (x.addPort b y).value a = x.value a+y.value a := by
  have q := rippleCircuit_add_exact b (x.addWidth y) (x.padded z _).bit (y.padded z _).bit a h
  change (x.addPort b y).value a = (x.padded z (x.addWidth y)).value a +
    (y.padded z (x.addWidth y)).value a at q
  rw [x.padded_value hz (show x.width ≤ x.addWidth y from le_max_left ..),
    y.padded_value hz (show y.width ≤ x.addWidth y from le_max_right ..)] at q
  exact q

theorem rippleFrame (sub : Bool) (b n : ℕ) (x y : ℕ → ℕ) {p lo : ℕ}
    (hl : lo ≤ b)
    (hx : ∀ i < n, x i < p ∨ lo ≤ x i ∧ x i < b)
    (hy : ∀ i < n, y i < p ∨ lo ≤ y i ∧ y i < b) :
    GateFrame (rippleCircuit sub b n x y) p lo (b+8*n+1) := by
  have hl' (k : ℕ) (hk : b ≤ k) (hq : k < b+8*n+1) :
      k < p ∨ lo ≤ k ∧ k < b+8*n+1 := .inr ⟨hl.trans hk,hq⟩
  intro g hg k hk
  rcases List.mem_cons.mp hg with rfl | hg
  · simp [Gate.names,RobsonCNF.Gate.names,rippleCarryWire] at hk
    subst k
    exact hl' b le_rfl (by omega)
  · obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
    have hi' := List.mem_range.mp hi
    have h1 := hx i hi'
    have h2 := hy i hi'
    have h1' : x i < p ∨ lo ≤ x i ∧ x i < b+8*n+1 := by omega
    have h2' : y i < p ∨ lo ≤ y i ∧ y i < b+8*n+1 := by omega
    simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
      cases sub <;>
      simp [Gate.names,RobsonCNF.Gate.names,rippleCarryWire,rippleXorWire,rippleBitWire] at hk <;> (repeat' first | subst k | rcases hk with hk | hk) <;>
      first
      | omega
      | exact hl' (b+8*i+3) (by omega) (by omega)
      | exact hl' (b+8*i+4) (by omega) (by omega)
      | exact hl' (b+8*i+5) (by omega) (by omega)
      | exact hl' (b+8*i+6) (by omega) (by omega)

theorem BinaryPort.addGates_frame (z b : ℕ) (x y : BinaryPort) {p lo : ℕ}
    (hz : z < p) (hl : lo ≤ b) (hx : x.InFrame p lo b) (hy : y.InFrame p lo b) :
    GateFrame (x.addGates z b y) p lo (x.addEnd b y) :=
  rippleFrame false b (x.addWidth y) _ _ hl (x.padded_frame hx hz) (y.padded_frame hy hz)

theorem BinaryPort.addGates_extend (z b : ℕ) (x y : BinaryPort) (a : Assignment)
    (hz : z < b) (hx : x.Below b) (hy : y.Below b) :
    ∃ c, Keeps a c b (x.addEnd b y) ∧ GateSat c (x.addGates z b y) := by
  apply rippleCircuit_extends_interval
  · intro i hi
    change (if i < x.width then x.bit i else z) < b
    split
    · exact hx i (by assumption)
    · exact hz
  · intro i hi
    change (if i < y.width then y.bit i else z) < b
    split
    · exact hy i (by assumption)
    · exact hz

def BinaryPort.subPort (b : ℕ) (x y : BinaryPort) : BinaryPort :=
  ⟨x.addWidth y,monusOutWire b (x.addWidth y)⟩

def BinaryPort.subGates (z b : ℕ) (x y : BinaryPort) : List Gate :=
  let k := x.addWidth y
  monusCircuit b k (x.padded z k).bit (y.padded z k).bit

def BinaryPort.subEnd (b : ℕ) (x y : BinaryPort) : ℕ := b+9*x.addWidth y+2

theorem BinaryPort.subPort_names (b : ℕ) (x y : BinaryPort) {i : ℕ}
    (hi : i < (x.subPort b y).width) :
    b ≤ (x.subPort b y).bit i ∧ (x.subPort b y).bit i < x.subEnd b y := by
  simp only [BinaryPort.subPort,BinaryPort.subEnd,monusOutWire] at hi ⊢
  omega

theorem BinaryPort.subGates_exact (z b : ℕ) (x y : BinaryPort) (a : Assignment)
    (hz : a z=false) (h : GateSat a (x.subGates z b y)) :
    (x.subPort b y).value a = x.value a-y.value a := by
  have q := monusCircuit_exact b (x.addWidth y) (x.padded z _).bit (y.padded z _).bit a h
  change (x.subPort b y).value a = (x.padded z (x.addWidth y)).value a -
    (y.padded z (x.addWidth y)).value a at q
  rw [x.padded_value hz (show x.width ≤ x.addWidth y from le_max_left ..),
    y.padded_value hz (show y.width ≤ x.addWidth y from le_max_right ..)] at q
  exact q

theorem BinaryPort.subGates_frame (z b : ℕ) (x y : BinaryPort) {p lo : ℕ}
    (hz : z < p) (hl : lo ≤ b) (hx : x.InFrame p lo b) (hy : y.InFrame p lo b) :
    GateFrame (x.subGates z b y) p lo (x.subEnd b y) := by
  let n := x.addWidth y
  have h : GateFrame (rippleCircuit true b n (x.padded z n).bit (y.padded z n).bit)
      p lo (b+8*n+1) := rippleFrame true b n _ _ hl (x.padded_frame hx hz) (y.padded_frame hy hz)
  apply GateFrame.append.mpr
  refine ⟨h.mono le_rfl le_rfl (by unfold BinaryPort.subEnd n; omega),?_⟩
  intro g hg k hk
  simp only [monusMask,List.mem_cons,List.mem_map] at hg
  rcases hg with rfl | ⟨i,hi,rfl⟩
  · simp [Gate.names,RobsonCNF.Gate.names,monusMaskWire,rippleCarryWire] at hk
    unfold BinaryPort.subEnd
    omega
  · have hi' := List.mem_range.mp hi
    simp [Gate.names,RobsonCNF.Gate.names,monusMaskWire,monusOutWire,rippleBitWire] at hk
    unfold BinaryPort.subEnd
    omega

theorem BinaryPort.subGates_extend (z b : ℕ) (x y : BinaryPort) (a : Assignment)
    (hz : z < b) (hx : x.Below b) (hy : y.Below b) :
    ∃ c, Keeps a c b (x.subEnd b y) ∧ GateSat c (x.subGates z b y) := by
  apply monusCircuit_extends_interval
  · intro i hi
    change (if i < x.width then x.bit i else z) < b
    split
    · exact hx i (by assumption)
    · exact hz
  · intro i hi
    change (if i < y.width then y.bit i else z) < b
    split
    · exact hy i (by assumption)
    · exact hz

end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).

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