Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Certificates for observed RAM memory

Definition
CNFEncComplexity_RobsonMemoryCertificates

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

complexity-theorysatisfiability

List-level soundness and completeness for RAM memory certificates. Includes injective trie labels, tiered updates, boundary snapshots, and permutation routing.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives

set_option maxHeartbeats 4000000
set_option linter.all false

/- memory certificates -/

namespace CNFEncComplexity.Robson

def atAddress (a : ℕ) (es : List MemoryAccess) : List MemoryAccess :=
  es.filter (fun e => decide (e.address = a))

/-- A permutation preserving the order of every address's accesses. An address sort using
the original positions as secondary keys has precisely this property. -/
def AddressStable (es fs : List MemoryAccess) : Prop :=
  ∀ a, atAddress a es = atAddress a fs

def cellReplay : ℕ → List MemoryAccess → ℕ
  | v, [] => v
  | _, e :: es => cellReplay e.value es

def cellValid : ℕ → List MemoryAccess → Prop
  | _, [] => True
  | v, e :: es => (e.writes = true ∨ v = e.value) ∧ cellValid e.value es

theorem replay_apply (current : Memory) (trace : List MemoryAccess) (a : ℕ) :
    replay current trace a = cellReplay (current a) (atAddress a trace) := by
  induction trace generalizing current with
  | nil => rfl
  | cons e es ih =>
    by_cases h : e.address = a
    · simp [replay, atAddress, h, ih, cellReplay]
    · have hh : a ≠ e.address := Ne.symm h
      simp [replay, atAddress, h, ih, Function.update_of_ne hh]

theorem valid_iff_cells (current : Memory) (trace : List MemoryAccess) :
    memoryValid current trace ↔ ∀ a, cellValid (current a) (atAddress a trace) := by
  induction trace generalizing current with
  | nil => simp [memoryValid, atAddress, cellValid]
  | cons e es ih =>
    simp only [memoryValid, ih]
    constructor
    · rintro ⟨he, hs⟩ a
      by_cases h : e.address = a
      · have ha := hs a
        simp [Function.update, h] at ha
        simpa [atAddress, cellValid, h] using And.intro (h ▸ he) ha
      · simpa [atAddress, h, Function.update_of_ne (Ne.symm h)] using hs a
    · intro hall
      have hfirst : (e.writes = true ∨ current e.address = e.value) ∧
          cellValid e.value (atAddress e.address es) := by
        simpa [atAddress, cellValid] using hall e.address
      refine ⟨hfirst.1, fun a => ?_⟩
      by_cases h : e.address = a
      · simpa [h] using hfirst.2
      · simpa [atAddress, h, Function.update_of_ne (Ne.symm h)] using hall a

theorem AddressStable.valid_iff {trace sorted : List MemoryAccess}
    (h : AddressStable trace sorted) (current : Memory) :
    memoryValid current trace ↔ memoryValid current sorted := by
  simp only [valid_iff_cells, h _]

theorem AddressStable.replay_eq {trace sorted : List MemoryAccess}
    (h : AddressStable trace sorted) (current : Memory) :
    replay current trace = replay current sorted := by
  funext a
  simp only [replay_apply, h a]

/-- A sorted trace can be checked using only each record, its immediate predecessor,
and the initial values when beginning an address block. -/
def adjacentValid (current : Memory) (trace : List MemoryAccess) : Prop :=
  (trace.head?.elim True fun e => e.writes = true ∨ current e.address = e.value) ∧
  trace.IsChain (fun e f =>
    f.writes = true ∨ (if e.address = f.address then e.value else current f.address) = f.value)

theorem adjacentValid_iff (current : Memory) (trace : List MemoryAccess)
    (ordered : trace.Pairwise (fun e f => e.address ≤ f.address)) :
    adjacentValid current trace ↔ memoryValid current trace := by
  induction trace generalizing current with
  | nil => simp [adjacentValid, memoryValid]
  | cons e es ih =>
    obtain ⟨horder, hs⟩ := List.pairwise_cons.1 ordered
    cases es with
    | nil => simp [adjacentValid, memoryValid]
    | cons f fs =>
      simp only [adjacentValid, List.head?_cons, Option.elim, List.isChain_cons_cons,
        memoryValid]
      have hs' := ih (Function.update current e.address e.value) hs
      have hprev : (if e.address = f.address then e.value else current f.address) =
          Function.update current e.address e.value f.address := by
        by_cases h : e.address = f.address <;> simp [h, Function.update, eq_comm]
      have hchain (a b : MemoryAccess) (hf : f.address ≤ a.address) (hb : a.address ≤ b.address) :
          (if a.address = b.address then a.value else current b.address) =
          (if a.address = b.address then a.value
            else Function.update current e.address e.value b.address) := by
        by_cases heq : a.address = b.address
        · simp [heq]
        · have h₁ : e.address ≤ f.address := horder f (by simp)
          have h₂ : b.address ≠ e.address := by omega
          simp [heq, Function.update_of_ne h₂]
      have hc :
          (f :: fs).IsChain (fun a b => b.writes = true ∨
            (if a.address = b.address then a.value else current b.address) = b.value) ↔
          (f :: fs).IsChain (fun a b => b.writes = true ∨
            (if a.address = b.address then a.value
             else Function.update current e.address e.value b.address) = b.value) := by
        have hrel (a b : MemoryAccess) (ha : a ∈ f :: fs) (hh : a.address ≤ b.address) :
            (b.writes = true ∨ (if a.address = b.address then a.value else current b.address) = b.value) ↔
            (b.writes = true ∨ (if a.address = b.address then a.value
             else Function.update current e.address e.value b.address) = b.value) := by
          have hfa : f.address ≤ a.address := by
            rcases List.mem_cons.1 ha with rfl | ha
            · exact Nat.le_refl _
            · exact (List.pairwise_cons.1 hs).1 _ ha
          rw [hchain a b hfa hh]
        have pchain := hs.isChain
        simp only [List.isChain_iff_getElem] at pchain ⊢
        refine forall_congr' (fun i => forall_congr' (fun hi => ?_))
        exact hrel _ _ (List.getElem_mem (by omega)) (pchain i hi)
      have heq : memoryValid (Function.update current e.address e.value) (f :: fs) ↔
          (f.writes = true ∨ (if e.address = f.address then e.value else current f.address) = f.value) ∧
          (f :: fs).IsChain (fun a b => b.writes = true ∨
            (if a.address = b.address then a.value else current b.address) = b.value) := by
        rw [← hs', adjacentValid]
        simp only [List.head?_cons, Option.elim, ← hprev, ← hc]
      simp only [memoryValid] at heq
      rw [heq]

theorem ordered_memory_certificate (current : Memory) (trace sorted : List MemoryAccess)
    (stable : AddressStable trace sorted)
    (ordered : sorted.Pairwise (fun e f => e.address ≤ f.address)) :
    memoryValid current trace ↔ adjacentValid current sorted :=
  (stable.valid_iff current).trans (adjacentValid_iff _ _ ordered).symm

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

def addressLE (a b : MemoryAccess) : Bool := decide (a.address ≤ b.address)

private theorem addressLE_trans (a b c : MemoryAccess) :
    addressLE a b → addressLE b c → addressLE a c := by
  simpa [addressLE] using (Nat.le_trans : a.address ≤ b.address → b.address ≤ c.address →
    a.address ≤ c.address)

private theorem addressLE_total (a b : MemoryAccess) : (addressLE a b || addressLE b a) = true := by
  simpa [addressLE] using Nat.le_total a.address b.address

def sortByAddress (trace : List MemoryAccess) : List MemoryAccess := trace.mergeSort addressLE

theorem sortByAddress_ordered (trace : List MemoryAccess) :
    (sortByAddress trace).Pairwise (fun e f => e.address ≤ f.address) := by
  simpa [sortByAddress, addressLE] using
    List.pairwise_mergeSort addressLE_trans addressLE_total trace

theorem sortByAddress_stable (trace : List MemoryAccess) :
    AddressStable trace (sortByAddress trace) := by
  intro a
  have hp : (atAddress a trace).Pairwise (fun e f => addressLE e f) := by
    apply List.pairwise_iff_getElem.2
    intro i j hi hj _
    have h₁ := List.mem_filter.1 (List.getElem_mem hi)
    have h₂ := List.mem_filter.1 (List.getElem_mem hj)
    simp only [decide_eq_true_eq] at h₁ h₂
    simp [addressLE, h₁.2, h₂.2]
  have hsub : List.Sublist (atAddress a trace) (sortByAddress trace) :=
    List.sublist_mergeSort addressLE_trans addressLE_total hp
      (List.filter_sublist (p := fun e : MemoryAccess => decide (e.address = a)))
  have hsub' : List.Sublist (atAddress a trace) (atAddress a (sortByAddress trace)) := by
    have hh := hsub.filter (fun e => decide (e.address = a))
    simpa [atAddress, List.filter_filter] using hh
  apply hsub'.eq_of_length
  exact ((List.mergeSort_perm trace addressLE).filter (fun e => decide (e.address = a))).symm.length_eq

/-- Address first, with the chronological position to break ties. -/
def taggedLE (a b : MemoryAccess × ℕ) : Prop :=
  a.1.address < b.1.address ∨ (a.1.address = b.1.address ∧ a.2 ≤ b.2)

theorem taggedLE_address {a b : MemoryAccess × ℕ} (h : taggedLE a b) :
    a.1.address ≤ b.1.address := by
  rcases h with h | ⟨h, _⟩ <;> omega

theorem taggedLE_time {a b : MemoryAccess × ℕ}
    (haddr : a.1.address = b.1.address) (h : taggedLE a b) : a.2 ≤ b.2 := by
  rcases h with h | ⟨_, h⟩ <;> omega

theorem taggedLE_trans (a b c : MemoryAccess × ℕ) :
    taggedLE a b → taggedLE b c → taggedLE a c := by
  unfold taggedLE
  rintro (h | ⟨h, t⟩) (h' | ⟨h', t'⟩) <;> omega

theorem taggedLE_total (a b : MemoryAccess × ℕ) : taggedLE a b ∨ taggedLE b a := by
  unfold taggedLE
  omega

theorem tag_ordered (trace : List MemoryAccess) :
    trace.zipIdx.Pairwise (fun a b => a.2 ≤ b.2) := by
  apply List.pairwise_iff_getElem.2
  intro i j hi hj hij
  simpa [List.getElem_zipIdx] using hij.le

/-- A sorted permutation of the records tagged by their chronological positions preserves
the order at every address. This is the witness format suited to a permutation network. -/
theorem tagged_sort_stable {trace : List MemoryAccess} {sorted : List (MemoryAccess × ℕ)}
    (hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise taggedLE) :
    AddressStable trace (sorted.map Prod.fst) := by
  intro addr
  let filterKey (a : MemoryAccess × ℕ) : Bool := decide (a.1.address = addr)
  have htime₁ : (trace.zipIdx.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) :=
    (tag_ordered trace).filter filterKey
  have htime₂ : (sorted.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) := by
    apply List.pairwise_iff_getElem.2
    intro i j hi hj hij
    let a := (sorted.filter filterKey)[i]
    let b := (sorted.filter filterKey)[j]
    have ha : a ∈ sorted.filter filterKey := List.getElem_mem hi
    have hb : b ∈ sorted.filter filterKey := List.getElem_mem hj
    have ht : taggedLE a b :=
      List.pairwise_iff_getElem.1 (horder.filter filterKey) i j hi hj hij
    have heq : a.1.address = b.1.address := by
      have hx := (List.mem_filter.1 ha).2
      have hy := (List.mem_filter.1 hb).2
      simp only [filterKey, decide_eq_true_eq] at hx hy
      exact hx.trans hy.symm
    exact taggedLE_time heq ht
  have hlex :
      trace.zipIdx.filter filterKey = sorted.filter filterKey := by
    apply List.Perm.eq_of_pairwise (le := fun a b : MemoryAccess × ℕ => decide (a.2 ≤ b.2))
    · intro a b ha hb hle hge
      have hp₁ : a ∈ trace.zipIdx := (List.mem_filter.1 ha).1
      have hp₂ : b ∈ trace.zipIdx := hperm.mem_iff.1 (List.mem_filter.1 hb).1
      have heq : a.2 = b.2 := Nat.le_antisymm (of_decide_eq_true hle) (of_decide_eq_true hge)
      rcases a with ⟨a,i⟩
      rcases b with ⟨b,j⟩
      change i = j at heq
      subst j
      obtain ⟨_, _, hia⟩ := List.mem_zipIdx hp₁
      obtain ⟨_, _, hjb⟩ := List.mem_zipIdx hp₂
      rw [hia, hjb]
    · simpa using htime₁
    · simpa using htime₂
    · exact (hperm.filter filterKey).symm
  have hh := congrArg (List.map Prod.fst) hlex
  change trace.filter (fun e => decide (e.address = addr)) =
    (sorted.map Prod.fst).filter (fun e => decide (e.address = addr))
  calc
    _ = (trace.zipIdx.map Prod.fst).filter (fun e => decide (e.address = addr)) := by
      rw [List.zipIdx_map_fst]
    _ = _ := by simpa only [List.filter_map, Function.comp_def, filterKey] using hh

theorem tagged_ordered_memory_certificate (current : Memory) (trace : List MemoryAccess)
    (sorted : List (MemoryAccess × ℕ))
    (hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise taggedLE) :
    memoryValid current trace ↔ adjacentValid current (sorted.map Prod.fst) :=
  ordered_memory_certificate current trace (sorted.map Prod.fst) (tagged_sort_stable hperm horder)
    (List.pairwise_map.mpr (horder.imp (fun h => taggedLE_address h)))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- A checked store record is a transition between optional values at one address.
A read retains a live value. Cancellation makes the address absent in this tier,
and a store creates a single live value in its new tier. Snapshots use the same
record format, with absent boundary entries represented by absent endpoints. -/
structure StoreRecord (Addr Val : Type) where
  addr : Addr
  before : Option Val
  after : Option Val
  deriving DecidableEq

namespace StoreRecord

variable {Addr Val : Type} [DecidableEq Addr]

/-- A checked record list describes a memory transformer with exact endpoint states. -/
inductive Runs : List (StoreRecord Addr Val) → (Addr → Option Val) → (Addr → Option Val) → Prop where
  | nil (mem : Addr → Option Val) : Runs [] mem mem
  | cons {r : StoreRecord Addr Val} {rs : List (StoreRecord Addr Val)}
      {mem finish : Addr → Option Val} :
      mem r.addr = r.before →
      Runs rs (Function.update mem r.addr r.after) finish →
      Runs (r :: rs) mem finish

theorem runs_append {A B : List (StoreRecord Addr Val)}
    {m n : Addr → Option Val} :
    Runs (A ++ B) m n ↔ ∃ k, Runs A m k ∧ Runs B k n := by
  induction A generalizing m with
  | nil =>
    simp only [List.nil_append]
    constructor
    · intro h
      exact ⟨m,.nil _,h⟩
    · rintro ⟨k,h,hr⟩
      cases h
      exact hr
  | cons r rs ih =>
    constructor
    · intro h
      cases h with
      | cons hread hrest =>
        obtain ⟨k,h₁,h₂⟩ := ih.mp hrest
        exact ⟨k,.cons hread h₁,h₂⟩
    · rintro ⟨k,h₁,h₂⟩
      cases h₁ with
      | cons hread hrest =>
        exact .cons hread (ih.mpr ⟨k,hrest,h₂⟩)

theorem run_swap {r s : StoreRecord Addr Val} {L : List (StoreRecord Addr Val)}
    {m n : Addr → Option Val} (hd : r.addr ≠ s.addr) :
    Runs (r::s::L) m n ↔ Runs (s::r::L) m n := by
  have hComm : (Function.update (Function.update m r.addr r.after) s.addr s.after) =
      Function.update (Function.update m s.addr s.after) r.addr r.after := by
    funext a
    by_cases ha : a = r.addr
    · subst a
      simp [Function.update_of_ne hd]
    · by_cases hb : a = s.addr
      · subst a
        simp [Function.update_of_ne hd.symm]
      · simp [Function.update_of_ne ha, Function.update_of_ne hb]
  constructor <;> intro h
  · cases h with
    | cons hr hs =>
      cases hs with
      | cons hs' hL =>
        have hsb : m s.addr = s.before := by
          simpa only [Function.update_of_ne hd.symm] using hs'
        have hrb : (Function.update m s.addr s.after) r.addr = r.before := by
          simpa only [Function.update_of_ne hd] using hr
        exact .cons hsb (.cons hrb (hComm ▸ hL))
  · cases h with
    | cons hs hr =>
      cases hr with
      | cons hr' hL =>
        have hrb : m r.addr = r.before := by
          simpa only [Function.update_of_ne hd] using hr'
        have hsb : (Function.update m r.addr r.after) s.addr = s.before := by
          simpa only [Function.update_of_ne hd.symm] using hs
        exact .cons hrb (.cons hsb (hComm.symm ▸ hL))

/-- The record order that matters for a memory trace is just the separate order
of records at each address. -/
def At (a : Addr) : List (StoreRecord Addr Val) → List (StoreRecord Addr Val) :=
  List.filter (fun r => r.addr == a)

/-- A per-address trace is valid if it forms a chain of consecutive value states. -/
inductive Chain : List (StoreRecord Addr Val) → Option Val → Option Val → Prop where
  | nil (state : Option Val) : Chain [] state state
  | cons {r : StoreRecord Addr Val} {rs : List (StoreRecord Addr Val)} {start finish : Option Val} :
      start = r.before → Chain rs r.after finish → Chain (r::rs) start finish

/-- Address-filtered chains characterize the exact chronological memory semantics. -/
theorem runs_iff_address_chains {xs : List (StoreRecord Addr Val)}
    {m n : Addr → Option Val} :
    Runs xs m n ↔ ∀ a, Chain (At a xs) (m a) (n a) := by
  induction xs generalizing m with
  | nil =>
    constructor
    · intro h
      cases h
      exact fun _ => .nil _
    · intro h
      have he : m = n := funext fun a => by
        have ha := h a
        change Chain [] (m a) (n a) at ha
        have hs {u v : Option Val} (h : Chain ([] : List (StoreRecord Addr Val)) u v) : u = v := by
          cases h
          rfl
        exact hs ha
      subst n
      exact .nil _
  | cons r rs ih =>
    constructor
    · intro h
      cases h with
      | cons hRead hRest =>
        have hr := ih.mp hRest
        intro a
        by_cases he : a = r.addr
        · subst a
          simp only [At,List.filter_cons,beq_self_eq_true,if_true]
          have hc : Chain (At r.addr rs) r.after (n r.addr) := by simpa using hr r.addr
          exact .cons hRead hc
        · have he' : (r.addr == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm he)
          simpa only [At,List.filter_cons,he',Bool.false_eq_true,if_false,Function.update_of_ne he] using hr a
    · intro h
      have hh := h r.addr
      simp only [At,List.filter_cons,beq_self_eq_true,if_true] at hh
      cases hh with
      | cons hRead hRest =>
        refine .cons hRead (ih.mpr fun a => ?_)
        by_cases he : a = r.addr
        · subst a
          simpa [At] using hRest
        · have he' : (r.addr == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm he)
          simpa only [At,List.filter_cons,he',Bool.false_eq_true,if_false,Function.update_of_ne he] using h a

/-- A stable permutation grouped by address preserves memory consistency. -/
theorem runs_of_stable {xs ys : List (StoreRecord Addr Val)} {m n : Addr → Option Val}
    (h : ∀ a, At a xs = At a ys) : Runs xs m n ↔ Runs ys m n := by
  simp only [runs_iff_address_chains,h]

/-- Consecutive checkpoint groups compose exactly when the shared snapshot agrees. -/
theorem runs_concat_of_groups {groups : List (List (StoreRecord Addr Val))}
    (trace : List (Addr → Option Val))
    (h : List.Forall₂ (fun xs (mn : (Addr → Option Val) × (Addr → Option Val)) =>
      Runs xs mn.1 mn.2) groups (trace.zip trace.tail)) :
    ∀ m n, trace.head? = some m → trace.getLast? = some n →
      Runs groups.flatten m n := by
  induction groups generalizing trace with
  | nil =>
    intro m n hm hn
    cases trace with
    | nil => simp at hm
    | cons k ks =>
      cases ks with
      | nil =>
        simp at hm hn
        subst m
        subst n
        exact .nil _
      | cons l ls => cases h
  | cons xs groups ih =>
    intro m n hm hn
    cases trace with
    | nil => simp at hm
    | cons k ks =>
      cases ks with
      | nil => cases h
      | cons l ls =>
        simp at hm
        subst m
        change List.Forall₂ _ (xs::groups) ((k,l)::((l::ls).zip ls)) at h
        cases h with
        | cons hRun hRest =>
          have hTail : Runs groups.flatten l n := ih (l::ls) hRest l n (by simp) (by simpa using hn)
          exact runs_append.mpr ⟨l,hRun,hTail⟩

end StoreRecord
end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- An edge in the witness dictionary of prefixes of wide binary words. The identifier
zero is reserved for the empty prefix. -/
structure WordEdge where
  parent : ℕ
  digit : ℕ
  child : ℕ
  deriving DecidableEq

namespace WordEdge

def key (e : WordEdge) : ℕ × ℕ := (e.parent,e.digit)

/-- The two sorts certify these two functional dependencies. Edges with identical
keys have identical children, and edges with identical children have identical keys. -/
structure Interned (edges : List WordEdge) : Prop where
  nonzero : ∀ e ∈ edges, e.child ≠ 0
  keyFn : ∀ e ∈ edges, ∀ f ∈ edges, e.key = f.key → e.child = f.child
  childFn : ∀ e ∈ edges, ∀ f ∈ edges, e.child = f.child → e.key = f.key

/-- The input digit list is in reverse path order, so a cons follows one more trie edge. -/
inductive Represents (edges : List WordEdge) : List ℕ → ℕ → Prop where
  | nil : Represents edges [] 0
  | cons {d : ℕ} {ds : List ℕ} {parent child : ℕ} :
      Represents edges ds parent → (⟨parent,d,child⟩ : WordEdge) ∈ edges →
      Represents edges (d::ds) child

theorem Represents.functional {edges : List WordEdge} (hi : Interned edges)
    {digits : List ℕ} {i j : ℕ} (h : Represents edges digits i)
    (h' : Represents edges digits j) : i = j := by
  induction h generalizing j with
  | nil => cases h'; rfl
  | @cons d ds a b _ h1 ih =>
    cases h' with
    | @cons _ _ c t h2 h3 =>
      have he : a = c := ih h2
      exact hi.keyFn _ h1 _ h3 (by simp [key,he])

theorem Represents.injective {edges : List WordEdge} (hi : Interned edges)
    {s t : List ℕ} {i : ℕ} (h : Represents edges s i)
    (h' : Represents edges t i) : s = t := by
  induction h generalizing t with
  | nil =>
    cases h' with
    | nil => rfl
    | cons _ h3 => exact False.elim (hi.nonzero _ h3 rfl)
  | @cons d ds a b _ h1 ih =>
    cases h' with
    | nil => exact False.elim (hi.nonzero _ h1 rfl)
    | @cons e es c _ h2 h3 =>
      have hk := hi.childFn _ h1 _ h3 rfl
      have hac : a = c := congrArg Prod.fst hk
      have hde : d = e := congrArg Prod.snd hk
      subst c e
      exact congrArg (List.cons d) (ih h2)

theorem Represents.eq_iff {edges : List WordEdge} (hi : Interned edges)
    {s t : List ℕ} {i j : ℕ} (h : Represents edges s i)
    (h' : Represents edges t j) : i = j ↔ s = t := by
  constructor
  · intro hh
    subst j
    exact h.injective hi h'
  · intro hh
    subst t
    exact h.functional hi h'

private def suffixes : List ℕ → Finset (List ℕ)
  | [] => ∅
  | d::ds => insert (d::ds) (suffixes ds)

private theorem suffixes_nonempty {xs ys : List ℕ} (h : ys ∈ suffixes xs) : ys ≠ [] := by
  induction xs with
  | nil => simp [suffixes] at h
  | cons x xs ih =>
    rcases Finset.mem_insert.mp h with rfl | h
    · simp
    · exact ih h

private theorem suffixes_card_le (xs : List ℕ) : (suffixes xs).card ≤ xs.length := by
  induction xs with
  | nil => simp [suffixes]
  | cons x xs ih =>
    exact (Finset.card_insert_le ..).trans (Nat.succ_le_succ ih)

private theorem suffixes_tail {xs ys : List ℕ} (h : ys ∈ suffixes xs) :
    ys.tail = [] ∨ ys.tail ∈ suffixes xs := by
  induction xs with
  | nil => simp [suffixes] at h
  | cons x xs ih =>
    rcases Finset.mem_insert.mp h with rfl | h
    · cases xs with
      | nil => exact Or.inl rfl
      | cons a as =>
          exact Or.inr (Finset.mem_insert_of_mem (Finset.mem_insert_self ..))
    · rcases ih h with h | h
      · exact Or.inl h
      · exact Or.inr (Finset.mem_insert_of_mem h)

private def vocabulary : List (List ℕ) → Finset (List ℕ)
  | [] => ∅
  | w::ws => suffixes w ∪ vocabulary ws

private theorem vocabulary_card_le (words : List (List ℕ)) :
    (vocabulary words).card ≤ (words.map List.length).sum := by
  induction words with
  | nil => simp [vocabulary]
  | cons w ws ih =>
    exact (Finset.card_union_le ..).trans (Nat.add_le_add (suffixes_card_le w) ih)

private theorem suffixes_subset_vocabulary {w : List ℕ} {words : List (List ℕ)}
    (h : w ∈ words) : suffixes w ⊆ vocabulary words := by
  induction words with
  | nil => simp at h
  | cons z zs ih =>
    rcases List.mem_cons.1 h with rfl | h
    · exact Finset.subset_union_left
    · exact (ih h).trans Finset.subset_union_right

private theorem vocabulary_nonempty {words : List (List ℕ)} {ys : List ℕ}
    (h : ys ∈ vocabulary words) : ys ≠ [] := by
  induction words with
  | nil => simp [vocabulary] at h
  | cons w ws ih =>
    rcases Finset.mem_union.mp h with h | h
    · exact suffixes_nonempty h
    · exact ih h

private theorem vocabulary_tail {words : List (List ℕ)} {ys : List ℕ}
    (h : ys ∈ vocabulary words) : ys.tail = [] ∨ ys.tail ∈ vocabulary words := by
  induction words with
  | nil => simp [vocabulary] at h
  | cons w ws ih =>
    rcases Finset.mem_union.mp h with h | h
    · exact (suffixes_tail h).imp_right (Finset.mem_union_left _)
    · exact (ih h).imp_right (Finset.mem_union_right _)

private theorem vocabulary_full_mem {words : List (List ℕ)} {ys : List ℕ}
    (h : ys ∈ words) (hne : ys ≠ []) : ys ∈ vocabulary words := by
  apply suffixes_subset_vocabulary h
  cases ys with
  | nil => exact False.elim (hne rfl)
  | cons x xs => exact Finset.mem_insert_self ..

private theorem vocabulary_label_exists (words : List (List ℕ)) :
    ∃ lab : List ℕ → ℕ, lab [] = 0 ∧
      (∀ w ∈ vocabulary words, 0 < lab w ∧ lab w ≤ (words.map List.length).sum) ∧
      (∀ u ∈ insert [] (vocabulary words), ∀ v ∈ insert [] (vocabulary words),
        lab u = lab v → u = v) := by
  classical
  let X := vocabulary words
  let enc : X ≃ Fin X.card :=
    Fintype.equivFinOfCardEq (by simp)
  let lab (w : List ℕ) : ℕ := if h : w ∈ X then (enc ⟨w,h⟩).val+1 else 0
  have hn : [] ∉ X := fun h => vocabulary_nonempty h rfl
  refine ⟨lab, dif_neg hn, ?_, ?_⟩
  · intro w hw
    rw [show lab w = (enc ⟨w,hw⟩).val+1 from dif_pos hw]
    exact ⟨Nat.zero_lt_succ _, (enc ⟨w,hw⟩).isLt.trans_le (vocabulary_card_le words)⟩
  · intro u hu v hv he
    rcases Finset.mem_insert.mp hu with rfl | hu
    · by_contra hh
      have h v (hv : v ∈ X) : lab v ≠ 0 := by rw [show lab v = _ from dif_pos hv]; omega
      exact h v ((Finset.mem_insert.mp hv).resolve_left (Ne.symm hh)) (he.symm.trans (dif_neg hn))
    · have hpos : 0 < lab u := by rw [show lab u = (enc ⟨u,hu⟩).val+1 from dif_pos hu]; omega
      rcases Finset.mem_insert.mp hv with rfl | hv
      · rw [show lab [] = 0 from dif_neg hn] at he
        omega
      · have heq : (enc ⟨u,hu⟩).val+1 = (enc ⟨v,hv⟩).val+1 := by
          rw [← show lab u = _ from dif_pos hu, ← show lab v = _ from dif_pos hv]
          exact he
        have hval : (enc ⟨u,hu⟩).val = (enc ⟨v,hv⟩).val := by omega
        exact congrArg Subtype.val (enc.injective (Fin.ext hval))

/-- An arbitrary batch of words has an interned dictionary with no more records
than the total number of digits. Identifiers are bounded by that same budget. -/
theorem intern_exists (words : List (List ℕ)) :
    ∃ (edges : List WordEdge) (lab : List ℕ → ℕ), Interned edges ∧ edges.length ≤ (words.map List.length).sum ∧
      (∀ w ∈ words, Represents edges w (lab w)) ∧
      ∀ e ∈ edges, max e.parent e.child ≤ (words.map List.length).sum := by
  classical
  obtain ⟨lab,hzero,hbound,hinj⟩ := vocabulary_label_exists words
  let build (w : List ℕ) : WordEdge := ⟨lab w.tail,w.headD 0,lab w⟩
  let edges := (vocabulary words).toList.map build
  have htail (w : List ℕ) (hw : w ∈ vocabulary words) :
      w.tail ∈ insert [] (vocabulary words) := by
    rcases vocabulary_tail hw with h | h
    · simp [h]
    · exact Finset.mem_insert_of_mem h
  have hmem (w : List ℕ) (hw : w ∈ vocabulary words) : build w ∈ edges := by
    apply List.mem_map.2
    exact ⟨w,Finset.mem_toList.2 hw,rfl⟩
  have habst (e : WordEdge) (he : e ∈ edges) :
      ∃ w ∈ vocabulary words, e = build w := by
    obtain ⟨w,hw,heq⟩ := List.mem_map.1 he
    exact ⟨w,Finset.mem_toList.1 hw,heq.symm⟩
  refine ⟨edges,lab, ⟨?_,?_,?_⟩, ?_, ?_, ?_⟩
  · intro e he
    obtain ⟨w,hw,rfl⟩ := habst e he
    exact (hbound w hw).1.ne'
  · intro e he f hf heq
    obtain ⟨u,hu,rfl⟩ := habst e he
    obtain ⟨v,hv,rfl⟩ := habst f hf
    have h1 : lab u.tail = lab v.tail := congrArg Prod.fst heq
    have h2 : u.headD 0 = v.headD 0 := congrArg Prod.snd heq
    have h3 : u.tail = v.tail := hinj _ (htail _ hu) _ (htail _ hv) h1
    have heq : u = v := by
      cases u with
      | nil => exact False.elim (vocabulary_nonempty hu rfl)
      | cons x xs =>
        cases v with
        | nil => exact False.elim (vocabulary_nonempty hv rfl)
        | cons y ys =>
          have hx : x = y := h2
          have hs : xs = ys := h3
          rw [hx,hs]
    rw [heq]
  · intro e he f hf heq
    obtain ⟨u,hu,rfl⟩ := habst e he
    obtain ⟨v,hv,rfl⟩ := habst f hf
    have h : u = v := hinj _ (Finset.mem_insert_of_mem hu) _ (Finset.mem_insert_of_mem hv) heq
    rw [h]
  · simpa [edges] using vocabulary_card_le words
  · have code (w : List ℕ) (hw : w = [] ∨ w ∈ vocabulary words) :
        Represents edges w (lab w) := by
      induction w with
      | nil => rw [hzero]; exact .nil
      | cons d ds ih =>
        have hm : d::ds ∈ vocabulary words := hw.resolve_left (by simp)
        have hc : build (d::ds) ∈ edges := hmem _ hm
        exact .cons (ih (vocabulary_tail hm)) hc
    intro w hw
    by_cases h : w = []
    · exact code _ (.inl h)
    · exact code _ (.inr (vocabulary_full_mem hw h))
  · intro e he
    obtain ⟨w,hw,rfl⟩ := habst e he
    have hc : lab w ≤ (words.map List.length).sum := (hbound w hw).2
    have hp : lab w.tail ≤ (words.map List.length).sum := by
      rcases vocabulary_tail hw with ht | ht
      · rw [ht,hzero]
        exact Nat.zero_le _
      · exact (hbound _ ht).2
    exact max_le hp hc

end WordEdge

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- In a key-ordered list, adjacent equal-key comparisons establish a global
functional dependency. Only non-strict monotonicity and antisymmetry are used. -/
theorem functional_of_adjacent {α β γ : Type} [PartialOrder β] {rows : List α}
    (key : α → β) (value : α → γ)
    (ordered : rows.Pairwise (fun e f => key e ≤ key f))
    (adjacent : rows.IsChain (fun e f => key e = key f → value e = value f)) :
    ∀ e ∈ rows, ∀ f ∈ rows, key e = key f → value e = value f := by
  induction rows with
  | nil => simp
  | cons head tail ih =>
    obtain ⟨firstLE, orderedTail⟩ := List.pairwise_cons.1 ordered
    have adjTail : tail.IsChain (fun e f => key e = key f → value e = value f) := by
      cases tail with
      | nil => simp
      | cons next rest => exact (List.isChain_cons_cons.mp adjacent).2
    have htail := ih orderedTail adjTail
    have headEq (f : α) (hf : f ∈ tail) (hkey : key head = key f) : value head = value f := by
      cases tail with
      | nil => simp at hf
      | cons next rest =>
        have hle : key next ≤ key f := by
          rcases List.mem_cons.1 hf with rfl | hf
          · exact le_rfl
          · exact (List.pairwise_cons.1 orderedTail).1 _ hf
        have heq : key head = key next :=
          le_antisymm (firstLE next (by simp)) (hkey ▸ hle)
        exact ((List.isChain_cons_cons.1 adjacent).1 heq).trans
          (htail next (by simp) f hf (heq.symm.trans hkey))
    intro e he f hf hkey
    rcases List.mem_cons.1 he with hh | he
    · subst e
      rcases List.mem_cons.1 hf with hh | hf
      · rw [hh]
      · exact headEq _ hf hkey
    · rcases List.mem_cons.1 hf with hh | hf
      · subst f
        exact (headEq _ he hkey.symm).symm
      · exact htail e he f hf hkey

open WordEdge in
/-- Two sorted-permutation checks on the occupied chunk lanes certify canonical
interning. The key sort uses an injective packing of the parent identifier and
the next digit. -/
theorem interned_of_sorted_certificates
    (edges keySort childSort : List WordEdge) {β : Type} [PartialOrder β]
    (pack : (ℕ × ℕ) → β) (pack_injective : Function.Injective pack)
    (nonzero : ∀ e ∈ edges, e.child ≠ 0)
    (keyPerm : keySort.Perm edges) (childPerm : childSort.Perm edges)
    (keyOrdered : keySort.Pairwise (fun e f => pack e.key ≤ pack f.key))
    (childOrdered : childSort.Pairwise (fun e f => e.child ≤ f.child))
    (keyCheck : keySort.IsChain (fun e f => pack e.key = pack f.key → e.child = f.child))
    (childCheck : childSort.IsChain (fun e f => e.child = f.child → pack e.key = pack f.key)) :
    WordEdge.Interned edges := by
  have hkey := functional_of_adjacent (pack ∘ WordEdge.key) WordEdge.child keyOrdered keyCheck
  have hchild := functional_of_adjacent WordEdge.child (pack ∘ WordEdge.key) childOrdered childCheck
  refine ⟨nonzero,?_,?_⟩
  · intro e he f hf h
    exact hkey _ (keyPerm.mem_iff.2 he) _ (keyPerm.mem_iff.2 hf) (congrArg pack h)
  · intro e he f hf h
    exact pack_injective (hchild _ (childPerm.mem_iff.2 he) _ (childPerm.mem_iff.2 hf) h)

theorem WordEdge.Interned.of_subset {edges more : List WordEdge}
    (h : WordEdge.Interned more) (sub : ∀ x ∈ edges, x ∈ more) :
    WordEdge.Interned edges where
  nonzero e he := h.nonzero e (sub e he)
  keyFn e he f hf := h.keyFn e (sub e he) f (sub f hf)
  childFn e he f hf := h.childFn e (sub e he) f (sub f hf)

/-- An occupied word chunk provides exactly one actual trie-edge occurrence. -/
def WordEdge.Chain (edges : List WordEdge) (digits : List ℕ) (id : ℕ) : Prop :=
  (edges.map WordEdge.digit = digits) ∧
  (edges.head?.elim 0 WordEdge.child = id) ∧
  (edges.getLast?.elim 0 WordEdge.parent = 0) ∧
  edges.IsChain (fun e f => e.parent = f.child)

theorem WordEdge.Represents.exists_chain {dict : List WordEdge} {digits : List ℕ} {id : ℕ}
    (h : WordEdge.Represents dict digits id) :
    ∃ rows, WordEdge.Chain rows digits id ∧ ∀ e ∈ rows, e ∈ dict := by
  induction h with
  | nil => exact ⟨[],by simp [WordEdge.Chain],by simp⟩
  | @cons d ds parent child hp he ih =>
    obtain ⟨rows,⟨hmap,hfirst,hlast,hlink⟩,hsub⟩ := ih
    let row : WordEdge := ⟨parent,d,child⟩
    refine ⟨row::rows,⟨?_, rfl, ?_, ?_⟩,?_⟩
    · simp [row,hmap]
    · cases rows with
      | nil => simpa using hfirst.symm
      | cons first rest =>
        simpa using hlast
    · cases rows with
      | nil => simp
      | cons first rest =>
        apply List.isChain_cons_cons.2
        exact ⟨hfirst.symm,hlink⟩
    · intro e h
      rcases List.mem_cons.1 h with rfl | h
      · exact he
      · exact hsub _ h

/-- Reading the lane rows as a linked chain gives the exact trie certificate. -/
theorem WordEdge.Chain.represents {dict rows : List WordEdge} {digits : List ℕ} {id : ℕ}
    (h : WordEdge.Chain rows digits id) (sub : ∀ e ∈ rows, e ∈ dict) :
    WordEdge.Represents dict digits id := by
  induction rows generalizing digits id with
  | nil =>
    obtain ⟨hm,hf,_,_⟩ := h
    simp at hm hf
    subst digits id
    exact .nil
  | cons e es ih =>
    obtain ⟨hm,hf,hl,hlink⟩ := h
    have hs : WordEdge.Chain es (es.map WordEdge.digit) e.parent := by
      cases es with
      | nil =>
        have hr : e.parent = 0 := hl
        simp [WordEdge.Chain,hr]
      | cons f fs =>
        obtain ⟨hrel,htail⟩ := List.isChain_cons_cons.1 hlink
        exact ⟨rfl,hrel.symm,by simpa using hl,htail⟩
    have hh := ih hs (fun f hf => sub f (by simp [hf]))
    subst digits id
    exact .cons hh (sub e (by simp))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Even labels encode short words literally. Odd labels use trie identifiers for
long words. The tag separates the two representations, including at zero. -/
inductive WordLabel (b : ℕ) (dict : List WordEdge) : ℕ → ℕ → Prop where
  | small {x : ℕ} : x.size ≤ b → WordLabel b dict x (2*x)
  | wide {x id : ℕ} : b < x.size → WordEdge.Represents dict (Nat.digits (2^b) x) id →
      WordLabel b dict x (2*id+1)

theorem WordLabel.eq_iff {b : ℕ} {dict : List WordEdge} (good : WordEdge.Interned dict)
    {x y i j : ℕ} (hx : WordLabel b dict x i) (hy : WordLabel b dict y j) :
    i = j ↔ x = y := by
  cases hx <;> cases hy
  · omega
  · constructor
    · omega
    · intro h
      subst y
      omega
  · constructor
    · omega
    · intro h
      subst y
      omega
  · rename_i u hu hi v hv hj
    have hd := hi.eq_iff good hj
    rw [Nat.digits_inj_iff] at hd
    omega

theorem WordLabel.size_le {b : ℕ} {dict : List WordEdge} {x i : ℕ}
    (hx : WordLabel b dict x i)
    (bound : ∀ e ∈ dict, e.child < 2^b) :
    i.size ≤ b+1 ∧ i.size ≤ x.size+1 := by
  cases hx with
  | small hx =>
    have hu : 2*x < 2^(x.size+1) := by
      rw [Nat.pow_succ]
      have hlt := Nat.lt_size_self x
      omega
    have hsize := Nat.size_le.mpr hu
    omega
  | @wide id hx hr =>
    have huAux {ds : List ℕ} {z : ℕ} (h : WordEdge.Represents dict ds z) : z < 2^b := by
      cases h with
      | nil => exact Nat.pow_pos (by decide)
      | cons _ h => exact bound _ h
    have hu := huAux hr
    have hs : (2*id+1).size ≤ b+1 := by
      apply Nat.size_le.mpr
      rw [Nat.pow_succ]
      omega
    omega

/-- Supply compact labels for all words in a batch. Dictionary size and maximal ID
are at most the total digit count of the wide words, not the sum of their values. -/
theorem wordLabels_exist (b : ℕ) (words : List ℕ) :
    ∃ (dict : List WordEdge) (label : ℕ → ℕ),
      WordEdge.Interned dict ∧ label 0 = 0 ∧
      (∀ x ∈ words, WordLabel b dict x (label x)) ∧
      let slots := (((words.filter fun x => b < x.size).map (Nat.digits (2^b))).map List.length).sum
      dict.length ≤ slots ∧ ∀ e ∈ dict, max e.parent e.child ≤ slots := by
  let wide := (words.filter fun x => b < x.size).map (Nat.digits (2^b))
  obtain ⟨dict,code,hGood,hSize,hRep,hBound⟩ := WordEdge.intern_exists wide
  let label (x : ℕ) : ℕ := if b < x.size then 2*code (Nat.digits (2^b) x)+1 else 2*x
  refine ⟨dict,label,hGood,by simp [label],?_,hSize,hBound⟩
  intro x hx
  by_cases h : b < x.size
  · have hm : Nat.digits (2^b) x ∈ wide := by
      apply List.mem_map.2
      refine ⟨x,List.mem_filter.2 ⟨hx,by simpa using h⟩,rfl⟩
    simpa only [label,if_pos h] using (WordLabel.wide h (hRep _ hm))
  · simpa only [label,if_neg h] using (WordLabel.small (Nat.le_of_not_gt h))

/-- The compact representation checks the same reads and writes. The store need
only agree at represented addresses. -/
structure AccessLabels (b : ℕ) (dict : List WordEdge) (e e' : MemoryAccess) : Prop where
  address : WordLabel b dict e.address e'.address
  value : WordLabel b dict e.value e'.value
  writes : e.writes = e'.writes

def MemoryLabels (b : ℕ) (dict : List WordEdge) (mem mem' : Memory) : Prop :=
  ∀ a z, WordLabel b dict a z → WordLabel b dict (mem a) (mem' z)

theorem AccessLabels.update {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
    (good : WordEdge.Interned dict) (agree : MemoryLabels b dict mem mem')
    {e e' : MemoryAccess} (he : AccessLabels b dict e e') :
    MemoryLabels b dict (Function.update mem e.address e.value)
      (Function.update mem' e'.address e'.value) := by
  intro a z hz
  by_cases h : a = e.address
  · have hz' : z = e'.address := ((hz.eq_iff good he.address).2 h)
    subst a z
    simpa using he.value
  · have hz' : z ≠ e'.address := (hz.eq_iff good he.address).not.mpr h
    simpa only [Function.update_of_ne h, Function.update_of_ne hz'] using agree a z hz

theorem AccessLabels.check_iff {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
    (good : WordEdge.Interned dict) (agree : MemoryLabels b dict mem mem')
    {e e' : MemoryAccess} (he : AccessLabels b dict e e') :
    (e.writes = true ∨ mem e.address = e.value) ↔
      (e'.writes = true ∨ mem' e'.address = e'.value) :=
  or_congr (he.writes ▸ Iff.rfl) ((agree _ _ he.address).eq_iff good he.value).symm

/-- Compact labels preserve the exact logical behavior of the recorded memory
trace. Thus the tiered, sorted memory certificate can use these compact labels
while each arithmetic packet keeps its full source words. -/
theorem memoryValid_iff_compact {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
    {events events' : List MemoryAccess} (good : WordEdge.Interned dict)
    (agree : MemoryLabels b dict mem mem')
    (hLabels : List.Forall₂ (AccessLabels b dict) events events') :
    memoryValid mem events ↔ memoryValid mem' events' := by
  induction hLabels generalizing mem mem' with
  | nil => rfl
  | cons hx _ ih =>
    exact and_congr (hx.check_iff good agree) (ih (hx.update good agree))

theorem memoryValid_initial_iff_compact {b : ℕ} {dict : List WordEdge}
    {events events' : List MemoryAccess} (good : WordEdge.Interned dict)
    (hLabels : List.Forall₂ (AccessLabels b dict) events events') :
    memoryValid (fun _ => 0) events ↔ memoryValid (fun _ => 0) events' :=
  memoryValid_iff_compact good (fun _ _ _ => WordLabel.small (by simp)) hLabels

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

abbrev Tier := ℕ → ℕ → ℕ
abbrev TierRecord := StoreRecord (ℕ × ℕ) ℕ

/-- A logical address has one live value. Its physical tier is determined by
that address and value. Initial zero values have their own live records. -/
def liveMemory (tier : Tier) (mem : Memory) : (ℕ × ℕ) → Option ℕ :=
  fun key => if key.1 = tier key.2 (mem key.2) then some (mem key.2) else none

theorem liveMemory_some_iff (tier : Tier) (mem : Memory) (key : ℕ × ℕ) (v : ℕ) :
    liveMemory tier mem key = some v ↔ key.1 = tier key.2 v ∧ mem key.2 = v := by
  unfold liveMemory
  split <;> simp_all
  intro he hmem
  exact ‹_ ≠ _› (by simpa [hmem] using he)

/-- Attach the old value of every write. For a change of tier, cancel the old
copy before creating the new live value. The two actions share the same logical
address, allowing local checks to identify them. -/
def tieredAccess (tier : Tier) (e : MemoryAccess) (old : ℕ) : List TierRecord :=
  let dest := (tier e.address e.value, e.address)
  let src := (tier e.address old, e.address)
  if e.writes then
    if src = dest then [⟨dest, some old, some e.value⟩]
    else [⟨src, some old, none⟩, ⟨dest, none, some e.value⟩]
  else [⟨dest, some e.value, some e.value⟩]

theorem tieredAccess_length (tier : Tier) (e : MemoryAccess) (old : ℕ) :
    (tieredAccess tier e old).length ≤ 2 := by
  simp only [tieredAccess]
  split <;> (try split) <;> simp

private theorem live_replace (tier : Tier) (mem : Memory) (a v : ℕ)
    (h : tier a (mem a) = tier a v) :
    liveMemory tier (Function.update mem a v) =
      Function.update (liveMemory tier mem) (tier a v,a) (some v) := by
  funext key
  obtain ⟨t,b⟩ := key
  by_cases hb : b = a
  · subst b
    by_cases ht : t = tier a v
    · subst t
      simp [liveMemory]
    · simp [liveMemory, h, ht]
  · have hk : (t,b) ≠ (tier a v,a) := by simp [hb]
    simp [liveMemory, Function.update_of_ne hb, Function.update_of_ne hk]

private theorem live_move (tier : Tier) (mem : Memory) (a v : ℕ)
    (h : tier a (mem a) ≠ tier a v) :
    liveMemory tier (Function.update mem a v) =
      Function.update (Function.update (liveMemory tier mem) (tier a (mem a),a) none)
        (tier a v,a) (some v) := by
  funext key
  obtain ⟨t,b⟩ := key
  by_cases hb : b = a
  · subst b
    by_cases ht : t = tier a v
    · subst t
      simp [liveMemory]
    · by_cases hs : t = tier a (mem a)
      · subst t
        simp [liveMemory, h]
      · simp [liveMemory, ht, hs]
  · have hk : (t,b) ≠ (tier a v,a) := by simp [hb]
    have hl : (t,b) ≠ (tier a (mem a),a) := by simp [hb]
    simp [liveMemory, Function.update_of_ne hb, Function.update_of_ne hk, Function.update_of_ne hl]

/-- Checking one tiered action enforces exactly the RAM read condition and results
in the same logical memory update. A write's old-value witness cannot be forged
because it must name an existing live record. -/
theorem tieredAccess_sound {tier : Tier} {mem : Memory} {e : MemoryAccess}
    {old : ℕ} {finish : (ℕ × ℕ) → Option ℕ}
    (run : StoreRecord.Runs (tieredAccess tier e old) (liveMemory tier mem) finish) :
    (e.writes = true ∨ mem e.address = e.value) ∧
      (e.writes = true → old = mem e.address) ∧
      finish = liveMemory tier (Function.update mem e.address e.value) := by
  simp only [tieredAccess] at run
  split at run
  · rename_i hw
    split at run
    · rename_i same
      cases run with
      | cons hbefore rest =>
        cases rest
        obtain ⟨htier,hold⟩ := (liveMemory_some_iff ..).mp hbefore
        change (tier e.address e.value : ℕ) = tier e.address old at htier
        change mem e.address = old at hold
        have heq : tier e.address (mem e.address) = tier e.address e.value := (congrArg (tier e.address) hold).trans htier.symm
        exact ⟨Or.inl hw, fun _ => hold.symm, (live_replace _ _ _ _ heq).symm⟩
    · rename_i diff
      cases run with
      | cons hbefore rest =>
        cases rest with
        | cons _ done =>
          cases done
          obtain ⟨_,hold⟩ := (liveMemory_some_iff ..).mp hbefore
          change mem e.address = old at hold
          have hdiff : tier e.address (mem e.address) ≠ tier e.address e.value := by
            intro eq
            exact diff (Prod.ext (hold ▸ eq) rfl)
          subst old
          exact ⟨Or.inl hw, fun _ => rfl, (live_move _ _ _ _ hdiff).symm⟩
  · rename_i hw
    cases run with
    | cons hbefore rest =>
      cases rest
      obtain ⟨_,hv⟩ := (liveMemory_some_iff ..).mp hbefore
      have hkeep (s : (ℕ × ℕ) → Option ℕ) (key : ℕ × ℕ) (v : ℕ)
          (h : s key = some v) : Function.update s key (some v) = s := by
        rw [← h, Function.update_eq_self]
      refine ⟨Or.inr hv, fun h => False.elim (hw h), ?_⟩
      rw [hkeep _ _ _ hbefore, ← hv, Function.update_eq_self]

theorem tieredAccess_complete (tier : Tier) (mem : Memory) (e : MemoryAccess)
    (h : e.writes = true ∨ mem e.address = e.value) :
    StoreRecord.Runs (tieredAccess tier e (mem e.address)) (liveMemory tier mem)
      (liveMemory tier (Function.update mem e.address e.value)) := by
  unfold tieredAccess
  dsimp
  split
  · rename_i hw
    split
    · rename_i same
      have hs : tier e.address (mem e.address) = tier e.address e.value := congrArg Prod.fst same
      rw [live_replace _ _ _ _ hs]
      exact .cons ((liveMemory_some_iff ..).mpr ⟨hs.symm, rfl⟩) (.nil _)
    · rename_i diff
      have hs : tier e.address (mem e.address) ≠ tier e.address e.value :=
        fun h => diff (Prod.ext h rfl)
      rw [live_move _ _ _ _ hs]
      refine .cons ((liveMemory_some_iff ..).mpr ⟨rfl,rfl⟩) (.cons ?_ (.nil _))
      simp [liveMemory, hs.symm]
  · rename_i hw
    have hv := h.resolve_left hw
    rw [live_replace _ _ _ _ (congrArg (tier e.address) hv)]
    exact .cons ((liveMemory_some_iff ..).mpr ⟨rfl,hv⟩) (.nil _)

/-- A witness for the old word at each write yields the chronologically ordered
tiered store records. -/
inductive TieredTrace (tier : Tier) : List MemoryAccess → List TierRecord → Prop where
  | nil : TieredTrace tier [] []
  | cons {e : MemoryAccess} {es : List MemoryAccess} {old : ℕ} {rs : List TierRecord} :
      TieredTrace tier es rs → TieredTrace tier (e :: es) (tieredAccess tier e old ++ rs)

theorem TieredTrace.length_le {tier : Tier} {events : List MemoryAccess} {records : List TierRecord}
    (expanded : TieredTrace tier events records) :
    records.length ≤ 2*events.length := by
  induction expanded with
  | nil => simp
  | @cons e es old rs hx ih =>
    have hl := tieredAccess_length tier e old
    simp only [List.length_append, List.length_cons]
    omega

theorem TieredTrace.sound {tier : Tier} {events : List MemoryAccess} {records : List TierRecord}
    (expanded : TieredTrace tier events records) (mem : Memory)
    {finish : (ℕ × ℕ) → Option ℕ}
    (run : StoreRecord.Runs records (liveMemory tier mem) finish) :
    memoryValid mem events ∧ finish = liveMemory tier (replay mem events) := by
  induction expanded generalizing mem with
  | nil =>
    cases run
    exact ⟨trivial, rfl⟩
  | cons hex ih =>
    obtain ⟨mid, hr, hs⟩ := StoreRecord.runs_append.1 run
    obtain ⟨hv, _, hm⟩ := tieredAccess_sound hr
    subst mid
    obtain ⟨hValid, hFinish⟩ := ih _ hs
    exact ⟨⟨hv,hValid⟩,hFinish⟩

theorem tieredTrace_complete (tier : Tier) (events : List MemoryAccess) (mem : Memory)
    (valid : memoryValid mem events) :
    ∃ records, TieredTrace tier events records ∧
      StoreRecord.Runs records (liveMemory tier mem) (liveMemory tier (replay mem events)) := by
  induction events generalizing mem with
  | nil => exact ⟨[], .nil, .nil _⟩
  | cons e es ih =>
    obtain ⟨hr,hs⟩ := valid
    obtain ⟨rs,ht,hrun⟩ := ih _ hs
    exact ⟨_, .cons ht, StoreRecord.runs_append.2 ⟨_, tieredAccess_complete _ _ _ hr, hrun⟩⟩

theorem memoryValid_iff_tieredTrace (tier : Tier) (events : List MemoryAccess) (mem : Memory) :
    memoryValid mem events ↔ ∃ records finish,
      TieredTrace tier events records ∧ StoreRecord.Runs records (liveMemory tier mem) finish := by
  constructor
  · intro hv
    obtain ⟨rs,hex,hr⟩ := tieredTrace_complete tier events mem hv
    exact ⟨rs,_,hex,hr⟩
  · rintro ⟨rs,finish,hex,hr⟩
    exact (hex.sound _ hr).1

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

abbrev LocalRecord := StoreRecord ℕ ℕ
abbrev LocalMemory := ℕ → Option ℕ

def localRecord (r : TierRecord) : LocalRecord := ⟨r.addr.2,r.before,r.after⟩

/-- Pass a tier to its own verifier, preserving chronological order. -/
def atTier (j : ℕ) (records : List TierRecord) : List LocalRecord :=
  (records.filter fun r => decide (r.addr.1 = j)).map localRecord

private theorem At_atTier (records : List TierRecord) (j a : ℕ) :
    StoreRecord.At a (atTier j records) =
      (StoreRecord.At (j,a) records).map localRecord := by
  simp only [atTier, StoreRecord.At, List.filter_map, List.filter_filter]
  congr 1
  apply congrArg (fun f : TierRecord → Bool => records.filter f)
  funext r
  rcases r with ⟨⟨i,k⟩,_,_⟩
  apply Bool.eq_iff_iff.2
  simp [localRecord, beq_iff_eq, and_comm]

private theorem chain_map_local (rs : List TierRecord) (before after : Option ℕ) :
    StoreRecord.Chain (rs.map localRecord) before after ↔
      StoreRecord.Chain rs before after := by
  induction rs generalizing before with
  | nil => constructor <;> intro h <;> cases h <;> exact .nil _
  | cons r rs ih =>
    constructor
    · intro h
      cases h with
      | cons hr hs => exact .cons hr (ih _ |>.1 hs)
    · intro h
      cases h with
      | cons hr hs => exact .cons hr (ih _ |>.2 hs)

/-- Partitioning by tier is sound even though records from different tiers can
refer to the same logical address. Their physical keys are different. -/
theorem tier_runs_iff (records : List TierRecord) (start finish : (ℕ × ℕ) → Option ℕ) :
    StoreRecord.Runs records start finish ↔
      ∀ j, StoreRecord.Runs (atTier j records) (fun a => start (j,a)) (fun a => finish (j,a)) := by
  rw [StoreRecord.runs_iff_address_chains]
  simp_rw [StoreRecord.runs_iff_address_chains, At_atTier, chain_map_local]
  constructor
  · intro H j a
    exact H (j,a)
  · intro H key
    exact H key.1 key.2

def localReplay : LocalMemory → List LocalRecord → LocalMemory
  | mem, [] => mem
  | mem, e::es => localReplay (Function.update mem e.addr e.after) es

def localValid : LocalMemory → List LocalRecord → Prop
  | _, [] => True
  | mem, e::es => mem e.addr = e.before ∧
    localValid (Function.update mem e.addr e.after) es

theorem localRuns_iff (start finish : LocalMemory) (records : List LocalRecord) :
    StoreRecord.Runs records start finish ↔
      localValid start records ∧ finish = localReplay start records := by
  induction records generalizing start with
  | nil =>
    constructor
    · intro h; cases h; exact ⟨trivial,rfl⟩
    · rintro ⟨_,rfl⟩
      exact .nil _
  | cons e es ih =>
    constructor
    · intro h
      cases h with
      | cons he hs =>
        obtain ⟨hv,hr⟩ := (ih _).1 hs
        exact ⟨⟨he,hv⟩,hr⟩
    · rintro ⟨⟨he,hv⟩,hr⟩
      exact .cons he ((ih _).2 ⟨hv,hr⟩)

/-- Check a sorted local trace without a dynamic memory lookup. Each nonfirst
record compares only against the preceding record, or the fixed initialization
rule if it starts a new address block. -/
def localAdjacent (start : LocalMemory) (records : List LocalRecord) : Prop :=
  (records.head?.elim True fun r => start r.addr = r.before) ∧
  records.IsChain (fun r s =>
    (if r.addr = s.addr then r.after else start s.addr) = s.before)

theorem localAdjacent_iff_localValid (start : LocalMemory) (records : List LocalRecord)
    (ordered : records.Pairwise (fun r s => r.addr ≤ s.addr)) :
    localAdjacent start records ↔ localValid start records := by
  induction records generalizing start with
  | nil => simp [localAdjacent,localValid]
  | cons e es ih =>
    obtain ⟨horder, hs⟩ := List.pairwise_cons.1 ordered
    cases es with
    | nil => simp [localAdjacent,localValid]
    | cons f fs =>
      simp only [localAdjacent, List.head?_cons, Option.elim, List.isChain_cons_cons,localValid]
      have hs' := ih (Function.update start e.addr e.after) hs
      have hprev : (if e.addr = f.addr then e.after else start f.addr) =
          Function.update start e.addr e.after f.addr := by
        by_cases h : e.addr = f.addr <;> simp [h, Function.update, eq_comm]
      have hchain (a b : LocalRecord) (hf : f.addr ≤ a.addr) (hb : a.addr ≤ b.addr) :
          (if a.addr = b.addr then a.after else start b.addr) =
          (if a.addr = b.addr then a.after
            else Function.update start e.addr e.after b.addr) := by
        by_cases heq : a.addr = b.addr
        · simp [heq]
        · have h₁ : e.addr ≤ f.addr := horder f (by simp)
          have h₂ : b.addr ≠ e.addr := by omega
          simp [heq, Function.update_of_ne h₂]
      have hc :
          (f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after else start b.addr) = b.before) ↔
          (f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after
             else Function.update start e.addr e.after b.addr) = b.before) := by
        have hrel (a b : LocalRecord) (ha : a ∈ f :: fs) (hh : a.addr ≤ b.addr) :
            ((if a.addr = b.addr then a.after else start b.addr) = b.before) ↔
            ((if a.addr = b.addr then a.after
             else Function.update start e.addr e.after b.addr) = b.before) := by
          have hfa : f.addr ≤ a.addr := by
            rcases List.mem_cons.1 ha with rfl | ha
            · exact Nat.le_refl _
            · exact (List.pairwise_cons.1 hs).1 _ ha
          rw [hchain a b hfa hh]
        have pchain := hs.isChain
        simp only [List.isChain_iff_getElem] at pchain ⊢
        refine forall_congr' (fun i => forall_congr' (fun hi => ?_))
        exact hrel _ _ (List.getElem_mem (by omega)) (pchain i hi)
      have heq : localValid (Function.update start e.addr e.after) (f :: fs) ↔
          ((if e.addr = f.addr then e.after else start f.addr) = f.before) ∧
          (f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after else start b.addr) = b.before) := by
        rw [← hs', localAdjacent]
        simp only [List.head?_cons, Option.elim, ← hprev, ← hc]
      simp only [localValid] at heq
      rw [heq]

/-- Lexicographic order by the address, then by the original position. The
position is supplied as a local batch index. -/
def localTaggedLE (x y : LocalRecord × ℕ) : Prop :=
  x.1.addr < y.1.addr ∨ (x.1.addr = y.1.addr ∧ x.2 ≤ y.2)

theorem localTaggedLE_trans (x y z : LocalRecord × ℕ) :
    localTaggedLE x y → localTaggedLE y z → localTaggedLE x z := by
  unfold localTaggedLE
  rintro (hx | ⟨hx,ht⟩) (hy | ⟨hy,ht'⟩) <;> omega

theorem localTaggedLE_total (x y : LocalRecord × ℕ) : localTaggedLE x y ∨ localTaggedLE y x := by
  unfold localTaggedLE
  omega

private theorem localTaggedLE_addr {x y : LocalRecord × ℕ} (h : localTaggedLE x y) :
    x.1.addr ≤ y.1.addr := by
  rcases h with h | ⟨h,_⟩ <;> omega

private theorem localTaggedLE_time {x y : LocalRecord × ℕ}
    (ha : x.1.addr = y.1.addr) (h : localTaggedLE x y) : x.2 ≤ y.2 := by
  rcases h with h | ⟨_,h⟩ <;> omega

private theorem same_clock {tr : List (LocalRecord × ℕ)}
    (chron : tr.Pairwise (fun a b => a.2 < b.2)) {x y : LocalRecord × ℕ}
    (hx : x ∈ tr) (hy : y ∈ tr) (he : x.2 = y.2) : x = y := by
  obtain ⟨i,hi,hx'⟩ := List.getElem_of_mem hx
  obtain ⟨j,hj,hy'⟩ := List.getElem_of_mem hy
  have ht : tr[i].2 = tr[j].2 := by rw [hx',hy',he]
  have hij : i = j := by
    rcases Nat.lt_trichotomy i j with h|h|h
    · have hh := List.pairwise_iff_getElem.1 chron i j hi hj h
      omega
    · exact h
    · have hh := List.pairwise_iff_getElem.1 chron j i hj hi h
      omega
  subst j
  exact hx'.symm.trans hy'

theorem localTagged_stable_general {trace sorted : List (LocalRecord × ℕ)}
    (chron : trace.Pairwise (fun a b => a.2 < b.2))
    (hperm : sorted.Perm trace) (horder : sorted.Pairwise localTaggedLE) :
    ∀ addr, StoreRecord.At addr (trace.map Prod.fst) = StoreRecord.At addr (sorted.map Prod.fst) := by
  intro addr
  let filterKey (a : LocalRecord × ℕ) : Bool := a.1.addr == addr
  have htime₁ : (trace.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) :=
    (chron.imp fun h => Nat.le_of_lt h).filter filterKey
  have htime₂ : (sorted.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) := by
    apply List.pairwise_iff_getElem.2
    intro i j hi hj hij
    let a := (sorted.filter filterKey)[i]
    let b := (sorted.filter filterKey)[j]
    have ha : a ∈ sorted.filter filterKey := List.getElem_mem hi
    have hb : b ∈ sorted.filter filterKey := List.getElem_mem hj
    have ht : localTaggedLE a b :=
      List.pairwise_iff_getElem.1 (horder.filter filterKey) i j hi hj hij
    have heq : a.1.addr = b.1.addr := by
      have hx := (List.mem_filter.1 ha).2
      have hy := (List.mem_filter.1 hb).2
      simp only [filterKey, beq_iff_eq] at hx hy
      exact hx.trans hy.symm
    exact localTaggedLE_time heq ht
  have hlex : trace.filter filterKey = sorted.filter filterKey := by
    apply List.Perm.eq_of_pairwise (le := fun a b : LocalRecord × ℕ => decide (a.2 ≤ b.2))
    · intro a b ha hb hle hge
      have hp₁ : a ∈ trace := (List.mem_filter.1 ha).1
      have hp₂ : b ∈ trace := hperm.mem_iff.1 (List.mem_filter.1 hb).1
      exact same_clock chron hp₁ hp₂ (Nat.le_antisymm (of_decide_eq_true hle) (of_decide_eq_true hge))
    · simpa using htime₁
    · simpa using htime₂
    · exact (hperm.filter filterKey).symm
  have hh := congrArg (List.map Prod.fst) hlex
  simpa only [StoreRecord.At,List.filter_map,Function.comp_def,filterKey] using hh

theorem localTagged_stable {trace : List LocalRecord} {sorted : List (LocalRecord × ℕ)}
    (hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise localTaggedLE) :
    ∀ addr, StoreRecord.At addr trace = StoreRecord.At addr (sorted.map Prod.fst) := by
  have htime : trace.zipIdx.Pairwise (fun a b => a.2 < b.2) := by
    apply List.pairwise_iff_getElem.2
    intro i j hi hj hij
    simpa [List.getElem_zipIdx] using hij
  simpa only [List.zipIdx_map_fst] using localTagged_stable_general htime hperm horder

theorem localSorted_exists (trace : List LocalRecord) :
    ∃ sorted : List (LocalRecord × ℕ), sorted.Perm trace.zipIdx ∧ sorted.Pairwise localTaggedLE := by
  classical
  let cmp (x y : LocalRecord × ℕ) := decide (localTaggedLE x y)
  refine ⟨trace.zipIdx.mergeSort cmp,List.mergeSort_perm _ _,?_⟩
  have ht (x y z : LocalRecord × ℕ) (h1 : cmp x y = true) (h2 : cmp y z = true) : cmp x z = true :=
    decide_eq_true (localTaggedLE_trans x y z (of_decide_eq_true h1) (of_decide_eq_true h2))
  have ho (x y : LocalRecord × ℕ) : (cmp x y || cmp y x) = true := by
    simpa [cmp] using localTaggedLE_total x y
  simpa only [cmp,decide_eq_true_eq] using List.pairwise_mergeSort (le := cmp) ht ho trace.zipIdx

/-- Exact validity of an arbitrary tagged sorting certificate. After sorting,
adjacent comparison is sufficient for each record. -/
theorem sortedMemory_iff (start : LocalMemory) (trace : List LocalRecord)
    (sorted : List (LocalRecord × ℕ))
    (perm : sorted.Perm trace.zipIdx) (ordered : sorted.Pairwise localTaggedLE) :
    localAdjacent start (sorted.map Prod.fst) ↔
      ∃ finish, StoreRecord.Runs trace start finish := by
  have htag : (sorted.map Prod.fst).Pairwise (fun a b => a.addr ≤ b.addr) :=
    List.pairwise_map.mpr (ordered.imp fun h => localTaggedLE_addr h)
  rw [localAdjacent_iff_localValid _ _ htag]
  constructor
  · intro h
    let finish := localReplay start (sorted.map Prod.fst)
    exact ⟨finish, (StoreRecord.runs_of_stable (localTagged_stable perm ordered)).mpr
      ((localRuns_iff _ _ _).2 ⟨h,rfl⟩)⟩
  · rintro ⟨finish,h⟩
    exact ((localRuns_iff _ _ _).1
      ((StoreRecord.runs_of_stable (localTagged_stable perm ordered)).mp h)).1

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- A local sort witness for one physical group. -/
def LocalCertificate (start : LocalMemory) (trace : List LocalRecord) : Prop :=
  ∃ sorted : List (LocalRecord × ℕ), sorted.Perm trace.zipIdx ∧
    sorted.Pairwise localTaggedLE ∧ localAdjacent start (sorted.map Prod.fst)

theorem localCertificate_iff (start : LocalMemory) (records : List LocalRecord) :
    LocalCertificate start records ↔ ∃ finish, StoreRecord.Runs records start finish := by
  constructor
  · rintro ⟨sorted,hp,ho,hc⟩
    exact (sortedMemory_iff start records sorted hp ho).1 hc
  · intro h
    obtain ⟨sorted,hp,ho⟩ := localSorted_exists records
    exact ⟨sorted,hp,ho,(sortedMemory_iff start records sorted hp ho).2 h⟩

/-- An address range provides the entire finite snapshot at a group boundary. -/
def LocalMemory.Restricted (q : ℕ) (state : LocalMemory) : Prop :=
    ∀ a, q ≤ a → state a = none

def beginSnapshot (q : ℕ) (state : LocalMemory) : List LocalRecord :=
  (List.range q).map (fun a => ⟨a,none,state a⟩)

def endSnapshot (q : ℕ) (state : LocalMemory) : List LocalRecord :=
  (List.range q).map (fun a => ⟨a,state a,none⟩)

def frameGroup (q : ℕ) (start finish : LocalMemory) (group : List LocalRecord) :
    List LocalRecord :=
  beginSnapshot q start ++ group ++ endSnapshot q finish

private theorem filter_range_key (a q : ℕ) :
    (List.range q).filter (fun x => x == a) = if a < q then [a] else [] := by
  induction q with
  | zero => simp
  | succ q ih =>
    rw [List.range_succ,List.filter_append,ih]
    by_cases h : a < q
    · simp [h,show a < q+1 by omega,show q ≠ a by omega]
    · by_cases he : q = a
      · subst a
        simp
      · simp [h,he,show ¬a < q+1 by omega]

private theorem at_map_range (mk : ℕ → LocalRecord) (h : ∀ a, (mk a).addr = a) (a q : ℕ) :
    StoreRecord.At a ((List.range q).map mk) = if a < q then [mk a] else [] := by
  have he : ((fun r : LocalRecord => r.addr == a) ∘ mk) = (fun x => x == a) :=
    funext fun x => by simp [h]
  rw [StoreRecord.At,List.filter_map,he,filter_range_key]
  split <;> rfl

theorem beginSnapshot_run (q : ℕ) (state : LocalMemory)
    (bounded : LocalMemory.Restricted q state) :
    StoreRecord.Runs (beginSnapshot q state) (fun _ => none) state := by
  apply StoreRecord.runs_iff_address_chains.mpr
  intro a
  unfold beginSnapshot
  rw [at_map_range _ (fun _ => rfl)]
  split
  · exact .cons rfl (.nil _)
  · rename_i ha
    rw [bounded a (Nat.le_of_not_gt ha)]
    exact .nil _

theorem endSnapshot_run (q : ℕ) (state : LocalMemory)
    (bounded : LocalMemory.Restricted q state) :
    StoreRecord.Runs (endSnapshot q state) state (fun _ => none) := by
  apply StoreRecord.runs_iff_address_chains.mpr
  intro a
  unfold endSnapshot
  rw [at_map_range _ (fun _ => rfl)]
  split
  · exact .cons rfl (.nil _)
  · rename_i ha
    rw [bounded a (Nat.le_of_not_gt ha)]
    exact .nil _

theorem localRun_outside {q : ℕ} {group : List LocalRecord} {start finish : LocalMemory}
    (bounded : ∀ r ∈ group, r.addr < q) (initial : LocalMemory.Restricted q start)
    (run : StoreRecord.Runs group start finish) :
    LocalMemory.Restricted q finish := by
  intro a ha
  have hch := (StoreRecord.runs_iff_address_chains.1 run) a
  have hnil : StoreRecord.At a group = [] := by
    apply List.filter_eq_nil_iff.2
    intro r hr
    have hh := bounded r hr
    have he : r.addr ≠ a := by omega
    simp [he]
  rw [hnil,initial a ha] at hch
  have empty {u v : Option ℕ} (hh : StoreRecord.Chain ([] : List LocalRecord) u v) : u=v := by
    cases hh
    rfl
  exact (empty hch).symm

private theorem endSnapshot_injective_initial (q : ℕ) (m finish state : LocalMemory)
    (boundedM : LocalMemory.Restricted q m) (boundedN : LocalMemory.Restricted q state)
    (run : StoreRecord.Runs (endSnapshot q state) m finish) :
    m = state := by
  funext a
  by_cases h : a < q
  · have hch := (StoreRecord.runs_iff_address_chains.1 run) a
    rw [endSnapshot,at_map_range _ (fun _ => rfl),if_pos h] at hch
    cases hch
    assumption
  · rw [boundedM a (Nat.le_of_not_gt h),boundedN a (Nat.le_of_not_gt h)]

/-- Checking a group's boundary records gives exactly its declared start and
finish states. The sorted circuit itself has a constant all-absent initialization. -/
theorem frameGroup_iff_run (q : ℕ) (start finish : LocalMemory) (group : List LocalRecord)
    (bounded : ∀ r ∈ group, r.addr < q) (hs : LocalMemory.Restricted q start)
    (hf : LocalMemory.Restricted q finish) :
    LocalCertificate (fun _ => none) (frameGroup q start finish group) ↔
      StoreRecord.Runs group start finish := by
  rw [localCertificate_iff]
  constructor
  · rintro ⟨final,run⟩
    obtain ⟨middle,run₂,run₃⟩ := StoreRecord.runs_append.1 run
    obtain ⟨start',run₁,run₂⟩ := StoreRecord.runs_append.1 run₂
    have hRun := beginSnapshot_run q start hs
    have hStart := ((localRuns_iff _ _ _).1 run₁).2.trans
      ((localRuns_iff _ _ _).1 hRun).2.symm
    subst start'
    have hMid := endSnapshot_injective_initial q middle final finish
      (localRun_outside bounded hs run₂) hf run₃
    subst middle
    exact run₂
  · intro run
    refine ⟨_, StoreRecord.runs_append.2 ⟨finish, ?_, endSnapshot_run q finish hf⟩⟩
    exact StoreRecord.runs_append.2 ⟨start,beginSnapshot_run q start hs,run⟩

/-- Fixed groups, including the last padded group. The group count and capacity
depend only on the circuit shape. -/
def fixedGroups {α : Type} (capacity : ℕ) : ℕ → List α → List (List α)
  | 0, _ => []
  | count+1, rows => rows.take capacity :: fixedGroups capacity count (rows.drop capacity)

@[simp] theorem fixedGroups_length {α : Type} (rows : List α) (capacity count : ℕ) :
    (fixedGroups capacity count rows).length = count := by
  induction count generalizing rows with
  | zero => rfl
  | succ count ih => simp [fixedGroups,ih]

theorem fixedGroups_each_length {α : Type} (rows : List α) (capacity count : ℕ) :
    ∀ g ∈ fixedGroups capacity count rows, g.length ≤ capacity := by
  induction count generalizing rows with
  | zero => simp [fixedGroups]
  | succ count ih =>
    intro g hg
    rcases List.mem_cons.1 hg with (rfl|hg)
    · simp
    · exact ih _ _ hg

theorem fixedGroups_flatten {α : Type} (rows : List α) (capacity count : ℕ)
    (h : rows.length ≤ capacity * count) :
    (fixedGroups capacity count rows).flatten = rows := by
  induction count generalizing rows with
  | zero =>
    simp at h
    simp [h,fixedGroups]
  | succ count ih =>
    have hd : (rows.drop capacity).length ≤ capacity*count := by
      rw [List.length_drop]
      rw [Nat.mul_succ] at h
      omega
    simp only [fixedGroups,List.flatten_cons,ih _ hd,List.take_append_drop]

/-- Snapshot witnesses for fixed groups, with each boundary checked exactly once
as a finish and once as a start. -/
inductive SnapshotCertificate (q : ℕ) : List (List LocalRecord) → LocalMemory → Prop where
  | nil (m : LocalMemory) : SnapshotCertificate q [] m
  | cons {xs : List LocalRecord} {rest : List (List LocalRecord)} {m n : LocalMemory} :
      LocalMemory.Restricted q n →
      LocalCertificate (fun _ => none) (frameGroup q m n xs) →
      SnapshotCertificate q rest n → SnapshotCertificate q (xs::rest) m

theorem snapshotCertificate_iff (q : ℕ) (groups : List (List LocalRecord)) (start : LocalMemory)
    (bounded : ∀ group ∈ groups, ∀ r ∈ group, r.addr < q)
    (hStart : LocalMemory.Restricted q start) :
    SnapshotCertificate q groups start ↔ ∃ finish, StoreRecord.Runs groups.flatten start finish := by
  induction groups generalizing start with
  | nil => exact ⟨fun _ => ⟨_,.nil _⟩,fun _ => .nil _⟩
  | cons group gs ih =>
    have hGroup := bounded group (by simp)
    have hRest : ∀ g ∈ gs, ∀ r ∈ g, r.addr < q :=
      fun g hg => bounded g (List.mem_cons_of_mem _ hg)
    constructor
    · intro h
      cases h with
      | cons hn cert rest =>
        obtain ⟨finish,run⟩ := (ih _ hRest hn).1 rest
        exact ⟨finish,StoreRecord.runs_append.2 ⟨_,
          (frameGroup_iff_run _ _ _ _ hGroup hStart hn).1 cert,run⟩⟩
    · rintro ⟨finish,run⟩
      obtain ⟨mid,run₁,run₂⟩ := StoreRecord.runs_append.1 run
      have hm := localRun_outside hGroup hStart run₁
      exact .cons hm ((frameGroup_iff_run _ _ _ _ hGroup hStart hm).2 run₁)
        ((ih _ hRest hm).2 ⟨finish,run₂⟩)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

def activeTagged (rows : List (Option LocalRecord × ℕ)) : List (LocalRecord × ℕ) :=
  rows.filterMap (fun row => row.1.map (fun active => (active,row.2)))

theorem activeTagged_chron (rows : List (Option LocalRecord × ℕ))
    (ordered : rows.Pairwise (fun a b => a.2 < b.2)) :
    (activeTagged rows).Pairwise (fun a b => a.2 < b.2) := by
  apply ordered.filterMap
  intro x y hlt u hx v hy
  rcases x with ⟨ox,i⟩
  rcases y with ⟨oy,j⟩
  cases ox <;> cases oy <;> simp_all
  rw [←hx,←hy]
  exact hlt

theorem activeTagged_of_slots (rows : List (Option LocalRecord)) (offset : ℕ) :
    (activeTagged (rows.zipIdx offset)).map Prod.fst = rows.filterMap id := by
  induction rows generalizing offset with
  | nil => rfl
  | cons r rs ih =>
    rw [List.zipIdx_cons]
    cases r <;> simp_all [activeTagged]

/-- A fixed network may permute all rows, including blanks. Occupied records
carry their original physical row numbers. No compaction is needed for their
timestamps, since gaps do not change the chronological order. -/
theorem slotSorted_iff (initial : LocalMemory) (rows : List (Option LocalRecord))
    (sorted : List (Option LocalRecord × ℕ))
    (hperm : sorted.Perm rows.zipIdx)
    (horder : (activeTagged sorted).Pairwise localTaggedLE) :
    localAdjacent initial ((activeTagged sorted).map Prod.fst) ↔
      ∃ final, StoreRecord.Runs (rows.filterMap id) initial final := by
  have htime : rows.zipIdx.Pairwise (fun a b => a.2 < b.2) := by
    apply List.pairwise_iff_getElem.2
    intro i j hi hj hij
    simpa [List.getElem_zipIdx] using hij
  have hchron := activeTagged_chron rows.zipIdx htime
  have hd : (activeTagged sorted).Perm (activeTagged rows.zipIdx) := hperm.filterMap _
  have hs := localTagged_stable_general hchron hd horder
  simp only [activeTagged_of_slots] at hs
  have htag : ((activeTagged sorted).map Prod.fst).Pairwise (fun a b => a.addr ≤ b.addr) :=
    List.pairwise_map.mpr (horder.imp fun h => localTaggedLE_addr h)
  rw [localAdjacent_iff_localValid _ _ htag]
  constructor
  · intro hv
    exact ⟨_, (StoreRecord.runs_of_stable hs).mpr ((localRuns_iff _ _ _).2 ⟨hv,rfl⟩)⟩
  · rintro ⟨f,hr⟩
    exact ((localRuns_iff _ _ _).1 ((StoreRecord.runs_of_stable hs).mp hr)).1

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Place occupied records before empty slots, then use local address and time. -/
def slotTaggedLE (x y : Option LocalRecord × ℕ) : Prop :=
  match x.1,y.1 with
  | some a,some b => localTaggedLE (a,x.2) (b,y.2)
  | none,some _ => False
  | _,none => True

theorem slotTaggedLE_trans (x y z : Option LocalRecord × ℕ) :
    slotTaggedLE x y → slotTaggedLE y z → slotTaggedLE x z := by
  rcases x with ⟨x,i⟩
  rcases y with ⟨y,j⟩
  rcases z with ⟨z,k⟩
  cases x <;> cases y <;> cases z <;>
    simp [slotTaggedLE]
  exact localTaggedLE_trans _ _ _

theorem slotTaggedLE_total (x y : Option LocalRecord × ℕ) :
    slotTaggedLE x y ∨ slotTaggedLE y x := by
  rcases x with ⟨x,i⟩
  rcases y with ⟨y,j⟩
  cases x <;> cases y <;> simp [slotTaggedLE,localTaggedLE_total]

private theorem occupied_ordered {rows : List (Option LocalRecord × ℕ)}
    (ho : rows.Pairwise slotTaggedLE) : (activeTagged rows).Pairwise localTaggedLE := by
  apply ho.filterMap
  intro x y h u hx v hy
  rcases x with ⟨x,i⟩
  rcases y with ⟨y,j⟩
  cases x <;> cases y <;> simp_all [slotTaggedLE]

def slotBefore (initial : LocalMemory) (r s : Option LocalRecord × ℕ) : Prop :=
  match r.1,s.1 with
  | some a,some b => (if a.addr = b.addr then a.after else initial b.addr) = b.before
  | _,_ => True

def slotsAdjacent (initial : LocalMemory) (rows : List (Option LocalRecord × ℕ)) : Prop :=
  (rows.head?.bind Prod.fst |>.elim True fun r => initial r.addr = r.before) ∧
  rows.IsChain (slotBefore initial)

private theorem no_active_after_blank {tail : List (Option LocalRecord × ℕ)} {j : ℕ}
    (h : (none,j) :: tail |>.Pairwise slotTaggedLE) :
    activeTagged tail = [] := by
  apply List.filterMap_eq_nil_iff.2
  intro x hx
  have hp := (List.pairwise_cons.1 h).1 x hx
  rcases x with ⟨r,i⟩
  cases r <;> simp_all [slotTaggedLE]

private theorem slotsChain_iff_active (initial : LocalMemory)
    (rows : List (Option LocalRecord × ℕ)) (hord : rows.Pairwise slotTaggedLE) :
    rows.IsChain (slotBefore initial) ↔
      ((activeTagged rows).map Prod.fst).IsChain
        (fun a b => (if a.addr = b.addr then a.after else initial b.addr) = b.before) := by
  induction rows with
  | nil => simp [activeTagged]
  | cons e es ih =>
    obtain ⟨r,j⟩ := e
    have hTail := (List.pairwise_cons.1 hord).2
    cases r with
    | none =>
      have hactive : activeTagged ((none,j) :: es) = [] := no_active_after_blank (tail := es) hord
      rw [hactive]
      simp only [List.map_nil,List.isChain_nil]
      apply iff_true_intro
      apply List.isChain_iff_getElem.2
      intro i hi
      have hs : ∀ x ∈ (none,j) :: es, x.1 = none := by
        intro x hx
        rcases List.mem_cons.1 hx with rfl | hx
        · rfl
        · have hp := (List.pairwise_cons.1 hord).1 x hx
          cases x with
          | mk r i => cases r <;> simp_all [slotTaggedLE]
      unfold slotBefore
      rw [hs _ (List.getElem_mem (by omega))]
      cases ((none,j)::es)[i+1].1 <;> trivial
    | some r =>
      cases es with
      | nil => simp [activeTagged]
      | cons f fs =>
        obtain ⟨s,k⟩ := f
        cases s with
        | none =>
          have hp : activeTagged ((none,k) :: fs) = [] := no_active_after_blank (tail := fs) hTail
          have hactive : activeTagged ((some r,j) :: (none,k) :: fs) = [(r,j)] :=
            congrArg (List.cons (r,j)) hp
          rw [hactive]
          have htail := (ih hTail).2 (by simp [hp])
          simp [slotBefore,htail,List.isChain_cons_cons]
        | some s =>
          have ht := ih hTail
          simp only [activeTagged,List.filterMap_cons,Option.map,List.map_cons] at ht ⊢
          simp only [List.isChain_cons_cons,slotBefore]
          exact and_congr Iff.rfl ht

private theorem slotsAdjacent_iff_active (initial : LocalMemory)
    (rows : List (Option LocalRecord × ℕ)) (hord : rows.Pairwise slotTaggedLE) :
    slotsAdjacent initial rows ↔ localAdjacent initial ((activeTagged rows).map Prod.fst) := by
  unfold slotsAdjacent localAdjacent
  apply and_congr _ (slotsChain_iff_active initial rows hord)
  cases rows with
  | nil => rfl
  | cons row rs =>
    obtain ⟨r,i⟩ := row
    cases r with
    | none =>
      have hactive : activeTagged ((none,i)::rs) = [] := no_active_after_blank (tail := rs) hord
      simp [hactive]
    | some r => rfl

def OptionalCertificate (initial : LocalMemory) (rows : List (Option LocalRecord)) : Prop :=
  ∃ sorted : List (Option LocalRecord × ℕ),
    sorted.Perm rows.zipIdx ∧ sorted.Pairwise slotTaggedLE ∧ slotsAdjacent initial sorted

/-- Empty fixed lanes require no tests beyond sorted order. Chronological
adjacency is tested without removing them in the circuit. -/
theorem optionalCertificate_iff (initial : LocalMemory) (rows : List (Option LocalRecord)) :
    OptionalCertificate initial rows ↔ ∃ finish, StoreRecord.Runs (rows.filterMap id) initial finish := by
  constructor
  · rintro ⟨sorted,hp,ho,ha⟩
    exact (slotSorted_iff initial rows sorted hp (occupied_ordered ho)).1
      ((slotsAdjacent_iff_active initial sorted ho).1 ha)
  · intro hw
    classical
    let cmp (x y : Option LocalRecord × ℕ) := decide (slotTaggedLE x y)
    let sorted := rows.zipIdx.mergeSort cmp
    have ht (x y z : Option LocalRecord × ℕ) (h1 : cmp x y = true) (h2 : cmp y z = true) :
        cmp x z = true := decide_eq_true (slotTaggedLE_trans x y z
          (of_decide_eq_true h1) (of_decide_eq_true h2))
    have ho (x y : Option LocalRecord × ℕ) : (cmp x y || cmp y x) = true := by
      simpa [cmp] using slotTaggedLE_total x y
    have hsort : sorted.Pairwise slotTaggedLE := by
      simpa only [cmp,decide_eq_true_eq] using List.pairwise_mergeSort (le := cmp) ht ho rows.zipIdx
    have hp : sorted.Perm rows.zipIdx := List.mergeSort_perm _ _
    have ha := (slotSorted_iff initial rows sorted hp (occupied_ordered hsort)).2 hw
    exact ⟨sorted,hp,hsort,(slotsAdjacent_iff_active initial sorted hsort).2 ha⟩

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- The snapshot rows occupy fixed lanes; the middle lanes may be empty. -/
def optionFrame (q : ℕ) (start finish : LocalMemory) (rows : List (Option LocalRecord)) :
    List (Option LocalRecord) :=
  (beginSnapshot q start).map some ++ rows ++ (endSnapshot q finish).map some

theorem optionFrame_length (q : ℕ) (start finish : LocalMemory)
    (rows : List (Option LocalRecord)) :
    (optionFrame q start finish rows).length = q+rows.length+q := by
  simp [optionFrame,beginSnapshot,endSnapshot,Nat.add_assoc]

theorem optionFrame_iff (q : ℕ) (start finish : LocalMemory) (rows : List (Option LocalRecord))
    (bounded : ∀ r ∈ rows.filterMap id, r.addr < q)
    (hs : LocalMemory.Restricted q start) (hf : LocalMemory.Restricted q finish) :
    OptionalCertificate (fun _ => none) (optionFrame q start finish rows) ↔
      StoreRecord.Runs (rows.filterMap id) start finish := by
  rw [optionalCertificate_iff, ← frameGroup_iff_run _ _ _ _ bounded hs hf,localCertificate_iff]
  simp [optionFrame,frameGroup,List.filterMap_append,List.filterMap_map]

/-- The group endpoints are represented by a sequence of finite snapshots, not by
linking all global memory values to all events. -/
inductive OptionSnapshotCertificate (q : ℕ) :
    List (List (Option LocalRecord)) → LocalMemory → Prop where
  | nil (m : LocalMemory) : OptionSnapshotCertificate q [] m
  | cons {xs : List (Option LocalRecord)} {rest : List (List (Option LocalRecord))} {m n : LocalMemory} :
      LocalMemory.Restricted q n →
      OptionalCertificate (fun _ => none) (optionFrame q m n xs) →
      OptionSnapshotCertificate q rest n → OptionSnapshotCertificate q (xs::rest) m

theorem optionSnapshotCertificate_iff (q : ℕ) (groups : List (List (Option LocalRecord)))
    (start : LocalMemory)
    (bounded : ∀ r ∈ groups.flatten.filterMap id, r.addr < q)
    (hStart : LocalMemory.Restricted q start) :
    OptionSnapshotCertificate q groups start ↔
      ∃ finish, StoreRecord.Runs (groups.flatten.filterMap id) start finish := by
  induction groups generalizing start with
  | nil => exact ⟨fun _ => ⟨_,.nil _⟩,fun _ => .nil _⟩
  | cons group gs ih =>
    simp only [List.flatten_cons,List.filterMap_append,List.mem_append] at bounded ⊢
    have hGroup (r : LocalRecord) (hr : r ∈ group.filterMap id) := bounded r (.inl hr)
    have hRest (r : LocalRecord) (hr : r ∈ gs.flatten.filterMap id) := bounded r (.inr hr)
    constructor
    · intro h
      cases h with
      | cons hn cert rest =>
        obtain ⟨finish,run⟩ := (ih _ hRest hn).1 rest
        exact ⟨finish,StoreRecord.runs_append.2 ⟨_,
          (optionFrame_iff _ _ _ _ hGroup hStart hn).1 cert,run⟩⟩
    · rintro ⟨finish,run⟩
      obtain ⟨mid,run₁,run₂⟩ := StoreRecord.runs_append.1 run
      have hm := localRun_outside hGroup hStart run₁
      exact .cons hm ((optionFrame_iff _ _ _ _ hGroup hStart hm).2 run₁)
        ((ih _ hRest hm).2 ⟨finish,run₂⟩)

/-- With at most one group, use the known initialization and no snapshots. Otherwise
split the fixed chronological lanes before testing each group. -/
def TierBatchCertificate (q count : ℕ) (rows : List (Option LocalRecord)) (start : LocalMemory) :
    Prop :=
  if rows.length ≤ q then OptionalCertificate start rows
  else OptionSnapshotCertificate q (fixedGroups q count rows) start

theorem tierBatchCertificate_iff (q count : ℕ) (rows : List (Option LocalRecord)) (start : LocalMemory)
    (capacity : rows.length ≤ q*count)
    (bounded : ∀ r ∈ rows.filterMap id, r.addr < q)
    (hStart : LocalMemory.Restricted q start) :
    TierBatchCertificate q count rows start ↔
      ∃ finish, StoreRecord.Runs (rows.filterMap id) start finish := by
  unfold TierBatchCertificate
  split
  · exact optionalCertificate_iff start rows
  · have hf := fixedGroups_flatten rows q count capacity
    have hb : ∀ r ∈ (fixedGroups q count rows).flatten.filterMap id, r.addr < q := hf.symm ▸ bounded
    have h := optionSnapshotCertificate_iff q (fixedGroups q count rows) start hb hStart
    rw [hf] at h
    exact h

theorem finite_tier_runs_iff (levels : ℕ) (records : List TierRecord) (start : (ℕ × ℕ) → Option ℕ)
    (levelBound : ∀ r ∈ records, r.addr.1 < levels) :
    (∃ finish, StoreRecord.Runs records start finish) ↔
      ∀ j < levels, ∃ finish, StoreRecord.Runs (atTier j records) (fun a => start (j,a)) finish := by
  constructor
  · rintro ⟨finish,hr⟩ j _
    exact ⟨fun a => finish (j,a),(tier_runs_iff ..).1 hr j⟩
  · intro h
    classical
    let finish (key : ℕ × ℕ) :=
      if bound : key.1 < levels then (h key.1 bound).choose key.2 else start key
    refine ⟨finish,(tier_runs_iff ..).2 fun j => ?_⟩
    by_cases hj : j < levels
    · simpa only [finish,dif_pos hj] using (h j hj).choose_spec
    · have hnil : atTier j records = [] := by
        unfold atTier
        have hnone : (records.filter fun r => decide (r.addr.1 = j)) = [] := by
          apply List.filter_eq_nil_iff.2
          intro r hr
          have hb := levelBound r hr
          have hneq : r.addr.1 ≠ j := by omega
          simp [hneq]
        simp [hnone]
      simpa only [hnil,finish,dif_neg hj] using (StoreRecord.Runs.nil (fun a => start (j,a)))

/-- Exact bounded memory verifier, over finite groups of chronologically ordered
physical lanes. It works with the compact labels from the word dictionary. -/
theorem finiteTiersCertificate_iff (levels : ℕ) (records : List TierRecord)
    (start : (ℕ × ℕ) → Option ℕ) (q count : ℕ → ℕ)
    (rows : ℕ → List (Option LocalRecord))
    (levels_ok : ∀ r ∈ records, r.addr.1 < levels)
    (projection : ∀ j < levels, (rows j).filterMap id = atTier j records)
    (capacity : ∀ j < levels, (rows j).length ≤ q j * count j)
    (bounded : ∀ j < levels, ∀ r ∈ atTier j records, r.addr < q j)
    (start_ok : ∀ j < levels, LocalMemory.Restricted (q j) (fun a => start (j,a))) :
    (∀ j < levels, TierBatchCertificate (q j) (count j) (rows j) (fun a => start (j,a))) ↔
      ∃ finish, StoreRecord.Runs records start finish := by
  rw [finite_tier_runs_iff levels records start levels_ok]
  refine forall_congr' fun j => forall_congr' fun hj => ?_
  rw [tierBatchCertificate_iff _ _ _ _ (capacity j hj) ?_ (start_ok j hj), projection j hj]
  intro r hr
  exact bounded j hj r (projection j hj ▸ hr)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- An address and value use the narrowest dyadic width that contains their bits
and a leading marker. -/
def bitTier (address value : ℕ) : ℕ := (max address.size value.size).size

theorem bitTier_width (address value : ℕ) :
    address.size < 2^bitTier address value ∧ value.size < 2^bitTier address value :=
  ⟨(le_max_left ..).trans_lt (Nat.lt_size_self _),
    (le_max_right ..).trans_lt (Nat.lt_size_self _)⟩

theorem bitTier_le {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
    bitTier a v ≤ b.size :=
  Nat.size_le_size (max_le ha hv)

theorem bitTier_initial_restricted (j : ℕ) :
    LocalMemory.Restricted (2^(2^j)) (fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
  intro a h
  have he : j ≠ bitTier a 0 := by
    intro heq
    have hsize := (bitTier_width a 0).1
    rw [← heq] at hsize
    have hA := Nat.size_le.mp hsize.le
    omega
  simp [liveMemory,he]

/-- Every actual tier record fits that tier's address and word width. -/
structure TierRecordFits (maxWidth : ℕ) (r : TierRecord) : Prop where
  level : r.addr.1 ≤ maxWidth.size
  address : r.addr.2.size < 2^r.addr.1
  before : ∀ v, r.before = some v → v.size < 2^r.addr.1
  after : ∀ v, r.after = some v → v.size < 2^r.addr.1

private theorem fits_read {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
    TierRecordFits b (⟨(bitTier a v,a),some v,some v⟩ : TierRecord) := by
  obtain ⟨h1,h2⟩ := bitTier_width a v
  exact ⟨bitTier_le ha hv,h1,
    fun _ he => Option.some.inj he ▸ h2,
    fun _ he => Option.some.inj he ▸ h2⟩

private theorem fits_replace {a old v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b)
    (same : bitTier a old = bitTier a v) :
    TierRecordFits b (⟨(bitTier a v,a),some old,some v⟩ : TierRecord) := by
  obtain ⟨h1,h2⟩ := bitTier_width a v
  exact ⟨bitTier_le ha hv,h1,
    fun _ he => Option.some.inj he ▸ (same ▸ (bitTier_width a old).2),
    fun _ he => Option.some.inj he ▸ h2⟩

private theorem fits_cancel {a old b : ℕ} (ha : a.size ≤ b) (hv : old.size ≤ b) :
    TierRecordFits b (⟨(bitTier a old,a),some old,none⟩ : TierRecord) := by
  obtain ⟨h1,h2⟩ := bitTier_width a old
  exact ⟨bitTier_le ha hv,h1,
    fun _ he => Option.some.inj he ▸ h2,fun v he => by change none = some v at he; contradiction⟩

private theorem fits_install {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
    TierRecordFits b (⟨(bitTier a v,a),none,some v⟩ : TierRecord) := by
  obtain ⟨h1,h2⟩ := bitTier_width a v
  exact ⟨bitTier_le ha hv,h1,fun v he => by change none = some v at he; contradiction,
    fun _ he => Option.some.inj he ▸ h2⟩

theorem tieredAccess_fits {e : MemoryAccess} {old b : ℕ}
    (ha : e.address.size ≤ b) (hv : e.value.size ≤ b) (ho : old.size ≤ b) :
    ∀ r ∈ tieredAccess bitTier e old, TierRecordFits b r := by
  intro r hr
  unfold tieredAccess at hr
  dsimp only at hr
  split at hr
  · split at hr
    · rename_i hs
      have hs' : bitTier e.address old = bitTier e.address e.value := congrArg Prod.fst hs
      obtain rfl := List.mem_singleton.1 hr
      exact fits_replace ha hv hs'
    · simp only [List.mem_cons,List.not_mem_nil,or_false] at hr
      rcases hr with rfl|rfl
      · exact fits_cancel ha ho
      · exact fits_install ha hv
  · obtain rfl := List.mem_singleton.1 hr
    exact fits_read ha hv

/-- Completeness for bounded compact words. Every generated tier record has both
its old and its new value within its dyadic word width. -/
theorem tieredTrace_complete_bounded (b : ℕ) (events : List MemoryAccess) (m : Memory)
    (valid : memoryValid m events)
    (start : ∀ a, (m a).size ≤ b)
    (widths : ∀ e ∈ events, e.address.size ≤ b ∧ e.value.size ≤ b) :
    ∃ records, TieredTrace bitTier events records ∧
      StoreRecord.Runs records (liveMemory bitTier m) (liveMemory bitTier (replay m events)) ∧
      ∀ r ∈ records, TierRecordFits b r := by
  induction events generalizing m with
  | nil => exact ⟨[],.nil,.nil _,by simp⟩
  | cons e es ih =>
    obtain ⟨hread,htail⟩ := valid
    obtain ⟨ha,hv⟩ := widths e (by simp)
    let m' := Function.update m e.address e.value
    have hm' (a : ℕ) : (m' a).size ≤ b := by
      by_cases he : a=e.address
      · subst a; simpa [m'] using hv
      · simpa only [m',Function.update_of_ne he] using start a
    have hWidth (x : MemoryAccess) (hx : x ∈ es) := widths x (List.mem_cons_of_mem _ hx)
    obtain ⟨rs,hex,hr,hfit⟩ := ih m' htail hm' hWidth
    refine ⟨_,.cons (old := m e.address) hex,
      StoreRecord.runs_append.2 ⟨liveMemory bitTier m',tieredAccess_complete _ _ _ hread,hr⟩,?_⟩
    intro r h
    rcases List.mem_append.1 h with h|h
    · exact tieredAccess_fits ha hv (start e.address) r h
    · exact hfit r h

theorem atTier_address_bounded {records : List TierRecord} {b j : ℕ}
    (fits : ∀ r ∈ records, TierRecordFits b r) :
    ∀ r ∈ atTier j records, r.addr < 2^(2^j) := by
  intro r hr
  obtain ⟨r',hr',rfl⟩ := List.mem_map.1 hr
  obtain ⟨hm,hj⟩ := List.mem_filter.1 hr'
  simp only [decide_eq_true_eq] at hj
  have ha := (fits r' hm).address
  rw [hj] at ha
  exact Nat.size_le.mp ha.le

/-- The exact compact memory verifier, for chronological slot rows of the
declared fixed shape. Bit widths imply the finite address and tier bounds. -/
theorem compactMemoryCertificate_iff {b : ℕ} {physical : List TierRecord}
    (fits : ∀ r ∈ physical, TierRecordFits (b+1) r)
    (count : ℕ → ℕ) (rows : ℕ → List (Option LocalRecord))
    (projection : ∀ j < (b+1).size+1, (rows j).filterMap id = atTier j physical)
    (capacity : ∀ j < (b+1).size+1, (rows j).length ≤ 2^(2^j)*count j) :
    (∀ j < (b+1).size+1,
      TierBatchCertificate (2^(2^j)) (count j) (rows j)
        (fun a => liveMemory bitTier (fun _=>0) (j,a))) ↔
      ∃ final, StoreRecord.Runs physical (liveMemory bitTier (fun _=>0)) final := by
  exact finiteTiersCertificate_iff _ _ _ _ _ _
    (fun r hr => Nat.lt_succ_of_le (fits r hr).level)
    projection capacity
    (fun _ _ => atTier_address_bounded fits)
    (fun j _ => bitTier_initial_restricted j)

theorem compactMemoryCertificate_sound {b : ℕ} {dict : List WordEdge}
    {original compact : List MemoryAccess} (good : WordEdge.Interned dict)
    (labels : List.Forall₂ (AccessLabels b dict) original compact)
    {physical : List TierRecord} (expanded : TieredTrace bitTier compact physical)
    (fits : ∀ r ∈ physical, TierRecordFits (b+1) r)
    (count : ℕ → ℕ) (rows : ℕ → List (Option LocalRecord))
    (projection : ∀ j < (b+1).size+1, (rows j).filterMap id = atTier j physical)
    (capacity : ∀ j < (b+1).size+1, (rows j).length ≤ 2^(2^j)*count j)
    (certificate : ∀ j < (b+1).size+1,
      TierBatchCertificate (2^(2^j)) (count j) (rows j)
        (fun a => liveMemory bitTier (fun _=>0) (j,a))) :
    memoryValid (fun _=>0) original := by
  obtain ⟨final,run⟩ :=
    (compactMemoryCertificate_iff fits count rows projection capacity).1 certificate
  exact (memoryValid_initial_iff_compact good labels).2 (expanded.sound _ run).1

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Raw and compact records have the same control flag and labels for each
observed word. The raw old field is immaterial on a read. -/
structure ObservedLabels (b : ℕ) (dict : List WordEdge) (r r' : ObservedAccess) : Prop where
  action : AccessLabels b dict r.action r'.action
  old : r.action.writes = true → WordLabel b dict r.old r'.old

theorem observedMemoryValid_iff_labels {b : ℕ} {dict : List WordEdge} {m m' : Memory}
    {rows rows' : List ObservedAccess} (good : WordEdge.Interned dict)
    (agree : MemoryLabels b dict m m') (h : List.Forall₂ (ObservedLabels b dict) rows rows') :
    observedMemoryValid m rows ↔ observedMemoryValid m' rows' := by
  induction h generalizing m m' with
  | nil => rfl
  | @cons r r' rest rest' hrow _ ih =>
    refine and_congr ?_ (ih (hrow.action.update good agree))
    have ha := agree _ _ hrow.action.address
    cases hw : r.action.writes with
    | false =>
      have hw' : r'.action.writes = false := hrow.action.writes.symm.trans hw
      simpa [hw,hw'] using (ha.eq_iff good hrow.action.value).symm
    | true =>
      have hw' : r'.action.writes = true := hrow.action.writes.symm.trans hw
      simpa [hw,hw'] using (ha.eq_iff good (hrow.old hw)).symm

theorem observedMemoryValid_initial_iff_labels {b : ℕ} {dict : List WordEdge}
    {rows rows' : List ObservedAccess} (good : WordEdge.Interned dict)
    (h : List.Forall₂ (ObservedLabels b dict) rows rows') :
    observedMemoryValid (fun _ => 0) rows ↔ observedMemoryValid (fun _ => 0) rows' :=
  observedMemoryValid_iff_labels good (fun _ _ _ => WordLabel.small (by simp)) h

def tieredObservations (tier : Tier) (rows : List ObservedAccess) : List TierRecord :=
  rows.flatMap fun row => tieredAccess tier row.action row.old

theorem tieredObservations_length (tier : Tier) (rows : List ObservedAccess) :
    (tieredObservations tier rows).length ≤ 2*rows.length := by
  induction rows with
  | nil => simp [tieredObservations]
  | cons r rs ih =>
    have hr := tieredAccess_length tier r.action r.old
    change (tieredAccess tier r.action r.old ++ tieredObservations tier rs).length ≤ _
    simp only [List.length_append,List.length_cons]
    omega

theorem tieredObservations_sound {tier : Tier} {m : Memory} {rows : List ObservedAccess}
    {finish : (ℕ × ℕ) → Option ℕ}
    (run : StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m) finish) :
    observedMemoryValid m rows ∧ finish = liveMemory tier (replay m (rows.map ObservedAccess.action)) := by
  induction rows generalizing m with
  | nil => cases run; exact ⟨trivial,rfl⟩
  | cons row tail ih =>
    change StoreRecord.Runs (tieredAccess tier row.action row.old ++ tieredObservations tier tail) _ _ at run
    obtain ⟨mid, first, last⟩ := StoreRecord.runs_append.mp run
    obtain ⟨he,hold,rfl⟩ := tieredAccess_sound first
    obtain ⟨ht,hf⟩ := ih last
    refine ⟨⟨?_,ht⟩,hf⟩
    cases hw : row.action.writes with
    | false => simpa [hw] using (he.resolve_left (by simp [hw]))
    | true => simpa [hw] using (hold hw).symm

theorem tieredObservations_complete (tier : Tier) (m : Memory) (rows : List ObservedAccess)
    (h : observedMemoryValid m rows) :
    StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m)
      (liveMemory tier (replay m (rows.map ObservedAccess.action))) := by
  induction rows generalizing m with
  | nil => exact .nil _
  | cons row tail ih =>
    obtain ⟨he,ht⟩ := h
    change StoreRecord.Runs (tieredAccess tier row.action row.old ++ tieredObservations tier tail) _ _
    apply StoreRecord.runs_append.mpr
    refine ⟨liveMemory tier (Function.update m row.action.address row.action.value),?_,ih _ ht⟩
    cases hw : row.action.writes with
    | false =>
      have hh : m row.action.address = row.action.value := by simpa [hw] using he
      have hlocal := tieredAccess_complete tier m row.action (Or.inr hh)
      simpa [tieredAccess,hw] using hlocal
    | true =>
      have hh : m row.action.address = row.old := by simpa [hw] using he
      rw [← hh]
      exact tieredAccess_complete tier m row.action (Or.inl hw)

theorem observedMemoryValid_iff_tieredObservations (tier : Tier) (m : Memory)
    (rows : List ObservedAccess) : observedMemoryValid m rows ↔ ∃ finish,
      StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m) finish :=
  ⟨fun h => ⟨_,tieredObservations_complete _ _ _ h⟩, fun ⟨_,run⟩ => (tieredObservations_sound run).1⟩

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- A long word contributes at most twice its binary length divided by the
number of bits in each trie digit. -/
theorem labelDigitWeight {b x : ℕ} (hb : 0 < b) (hx : b < x.size) :
    b*((Nat.digits (2^b) x).length) ≤ 2*x.size := by
  let q := (x.size-1)/b+1
  have hmod := Nat.mod_lt (x.size-1) hb
  have he := Nat.div_add_mod (x.size-1) b
  have hq : x.size ≤ b*q := by
    unfold q
    rw [Nat.mul_add,Nat.mul_one]
    omega
  have hxq : x < (2^b)^q := by
    rw [← Nat.pow_mul]
    exact Nat.size_le.mp hq
  have hb' : 1 < 2^b := one_lt_pow₀ (by decide) (Nat.ne_zero_of_lt hb)
  have hlen := (Nat.digits_length_le_iff hb' x).2 hxq
  refine (Nat.mul_le_mul_left b hlen).trans ?_
  unfold q
  rw [Nat.mul_add,Nat.mul_one]
  have hp := Nat.div_mul_le_self (x.size-1) b
  rw [Nat.mul_comm ((x.size-1)/b)] at hp
  omega

def labelEntries (b : ℕ) (words : List ℕ) : ℕ :=
  (((words.filter fun x => b < x.size).map (Nat.digits (2^b))).map List.length).sum

theorem labelEntries_budget {b : ℕ} (hb : 0 < b) (words : List ℕ) :
    b*labelEntries b words ≤ 2*(words.map Nat.size).sum := by
  induction words with
  | nil => simp [labelEntries]
  | cons x xs ih =>
    unfold labelEntries at ih ⊢
    rw [List.filter_cons]
    by_cases hx : b < x.size
    · simp only [decide_eq_true_eq, hx, if_true, List.map_cons,List.sum_cons,Nat.mul_add]
      exact Nat.add_le_add (labelDigitWeight hb hx) ih
    · simp only [decide_eq_true_eq,hx,if_false,List.map_cons,List.sum_cons,Nat.mul_add]
      exact ih.trans (Nat.le_add_left _ _)

theorem wordLabels_exist_bounded (words : List ℕ) {B : ℕ}
    (hB : (words.map Nat.size).sum ≤ B) (b : ℕ) (hb : 0 < b) (hLarge : 2*B < 2^b) :
    ∃ (dict : List WordEdge) (label : ℕ → ℕ),
      WordEdge.Interned dict ∧ label 0 = 0 ∧
      dict.length ≤ labelEntries b words ∧
      (∀ e ∈ dict, max e.parent e.child < 2^b) ∧
      ∀ x ∈ words, WordLabel b dict x (label x) ∧ (label x).size ≤ b+1 ∧ (label x).size ≤ x.size+1 := by
  obtain ⟨d,l,hGood,hl0,hword,hd,hBound⟩ := wordLabels_exist b words
  have hs : labelEntries b words ≤ 2*B := by
    calc
      _ ≤ b*labelEntries b words := by simpa using (Nat.mul_le_mul_right (labelEntries b words) hb)
      _ ≤ 2*(words.map Nat.size).sum := labelEntries_budget hb words
      _ ≤ _ := Nat.mul_le_mul_left _ hB
  have hChild (e : WordEdge) (he : e ∈ d) : max e.parent e.child < 2^b :=
    ((hBound e he).trans hs).trans_lt hLarge
  exact ⟨d,l,hGood,hl0,hd,hChild,fun x hx => ⟨hword x hx,
    (hword x hx).size_le (fun e he => (le_max_right ..).trans_lt (hChild e he))⟩⟩

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

private theorem bitSum_lt (f : ℕ → Bool) (m : ℕ) :
    ((List.range m).map fun k => (f k).toNat*2^k).sum < 2^m := by
  induction m with
  | zero => simp
  | succ m ih =>
    rw [List.range_succ,List.map_append,List.sum_append,List.map_singleton,List.sum_singleton,pow_succ]
    cases h : f m <;> simp [h] <;> omega

theorem portWord_size (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) (f : ℕ) :
    (portWord α n t s f).size ≤ 2^s.2 :=
  Nat.size_le.mpr (bitSum_lt _ _)

theorem layoutSlot_end {t : ℕ} {s : ℕ × ℕ} (h : s ∈ layoutSlots t) :
    s.1+2^s.2 ≤ layoutHorizon t := by
  rcases s with ⟨a,j⟩
  obtain ⟨ha,hj,hm⟩ := layout_mem.mp h
  let q := 2^(layoutHeight t-j)
  have hh : layoutHorizon t = 2^j*q := by
    unfold layoutHorizon q
    rw [← pow_add,Nat.add_sub_of_le hj]
  have he := Nat.div_add_mod a (2^j)
  rw [hm,Nat.add_zero] at he
  have hquot : a / 2^j < q := by
    apply Nat.lt_of_mul_lt_mul_left (a := 2^j)
    rw [he,← hh]
    exact ha
  change a+2^j ≤ layoutHorizon t
  calc
    a+2^j = 2^j*(a/2^j+1) := by rw [Nat.mul_add,Nat.mul_one,he]
    _ ≤ 2^j*q := Nat.mul_le_mul_left _ (Nat.succ_le_of_lt hquot)
    _ = layoutHorizon t := hh.symm

theorem widths_le_of_pairwise {ls : List (ℕ × ℕ)} {lo hi : ℕ}
    (h : ls.Pairwise (fun s r => s.1+2^s.2 ≤ r.1))
    (hLo : ∀ s ∈ ls, lo ≤ s.1) (hHi : ∀ s ∈ ls, s.1+2^s.2 ≤ hi) (hI : lo ≤ hi) :
    (ls.map fun s => 2^s.2).sum ≤ hi-lo := by
  induction ls generalizing lo with
  | nil => simp
  | cons s rest ih =>
    obtain ⟨hs,hr⟩ := List.pairwise_cons.mp h
    have hL := hLo s (by simp)
    have hH := hHi s (by simp)
    have hSum := ih hr hs (fun r hr' => hHi r (List.mem_cons_of_mem _ hr')) hH
    simp only [List.map_cons,List.sum_cons]
    omega

theorem liveWidths_le {α : Assignment} {n t : ℕ} (h : SlotsWellFormed α n t) :
    ((liveSlots α n t).map fun s => 2^s.2).sum ≤ layoutHorizon t := by
  simpa using widths_le_of_pairwise (lo := 0) h.1 (fun _ _ => Nat.zero_le _)
    (fun _ hs => layoutSlot_end (List.mem_filter.mp hs).1) (Nat.zero_le _)

theorem portMemory_sizes {α : Assignment} {n t : ℕ} {s : ℕ × ℕ}
    {r : ObservedAccess} {i : ℕ} (hr : portMemory α n t s i = some r) :
    r.action.address.size ≤ 2^s.2 ∧ r.action.value.size ≤ 2^s.2 ∧ r.old.size ≤ 2^s.2 := by
  dsimp only [portMemory] at hr
  split at hr
  · obtain rfl := Option.some.inj hr
    exact ⟨portWord_size ..,portWord_size ..,portWord_size ..⟩
  · contradiction

def observationWords (rows : List ObservedAccess) : List ℕ :=
  rows.flatMap fun r => [r.action.address,r.action.value,r.old]

theorem slotObservationWord_budget (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
    ((observationWords (slotRows α n t s)).map Nat.size).sum ≤ 9*2^s.2 := by
  have hBound : ∀ r ∈ slotRows α n t s,
      r.action.address.size + r.action.value.size + r.old.size ≤ 3*2^s.2 := by
    intro r hr
    obtain ⟨i,_,hi⟩ := List.mem_filterMap.mp hr
    obtain ⟨ha,hv,ho⟩ := portMemory_sizes hi
    omega
  have hLen : (slotRows α n t s).length ≤ 3 := by
    simpa [slotRows] using (List.length_filterMap_le (f := portMemory α n t s) (l := List.range 3))
  have haux (rows : List ObservedAccess) (h : ∀ r ∈ rows,
      r.action.address.size + r.action.value.size + r.old.size ≤ 3*2^s.2) :
      ((observationWords rows).map Nat.size).sum ≤ rows.length*(3*2^s.2) := by
    induction rows with
    | nil => simp [observationWords]
    | cons r rest ih =>
      have h₁ := h r (by simp)
      have h₂ := ih (fun q hq => h q (List.mem_cons_of_mem _ hq))
      change (r.action.address.size+(r.action.value.size+(r.old.size+
        ((observationWords rest).map Nat.size).sum))) ≤ (rest.length+1)* (3*2^s.2)
      rw [Nat.add_mul,Nat.one_mul]
      omega
  exact (haux _ hBound).trans (by simpa [← Nat.mul_assoc] using Nat.mul_le_mul_right (3*2^s.2) hLen)

private theorem wordSum_append (xs ys : List ObservedAccess) :
    ((observationWords (xs++ys)).map Nat.size).sum =
      ((observationWords xs).map Nat.size).sum+((observationWords ys).map Nat.size).sum := by
  simp [observationWords,List.flatMap_append]

theorem memoryStream_word_budget {α : Assignment} {n t : ℕ} (h : SlotsWellFormed α n t) :
    ((observationWords (memoryStream α n t)).map Nat.size).sum ≤ 9*layoutHorizon t := by
  have he : (liveSlots α n t).flatMap (slotRows α n t) = memoryStream α n t := by
    change ((layoutSlots t).filter (slotLive α n t)).flatMap (slotRows α n t) =
      (layoutSlots t).flatMap (slotRows α n t)
    have hi (ls : List (ℕ×ℕ)) (hL : ∀ s ∈ ls, slotLive α n t s = false → slotRows α n t s = []) :
        (ls.filter (slotLive α n t)).flatMap (slotRows α n t) = ls.flatMap (slotRows α n t) := by
      induction ls with
      | nil => rfl
      | cons s ss ih =>
        have hS := ih (fun u hu => hL u (List.mem_cons_of_mem _ hu))
        cases hw : slotLive α n t s
        · simp [hw,hS,hL s (by simp) hw]
        · simp [hw,hS]
    exact hi _ (fun s hs hw => (h.2 s hs hw).2)
  have hSum (ls : List (ℕ×ℕ)) :
      ((observationWords (ls.flatMap (slotRows α n t))).map Nat.size).sum ≤
        9*(ls.map fun s => 2^s.2).sum := by
    induction ls with
    | nil => simp [observationWords]
    | cons s ss ih =>
      rw [List.flatMap_cons, wordSum_append,List.map_cons,List.sum_cons,Nat.mul_add]
      exact Nat.add_le_add (slotObservationWord_budget α n t s) ih
  rw [← he]
  exact (hSum _).trans (Nat.mul_le_mul_left _ (liveWidths_le h))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

def compactRow (f : ℕ → ℕ) (r : ObservedAccess) : ObservedAccess :=
  ⟨⟨f r.action.address,f r.action.value,r.action.writes⟩,f r.old⟩

theorem compactRow_fits {b : ℕ} {rows : List ObservedAccess} {r : ObservedAccess}
    {f : ℕ → ℕ} (hr : r ∈ rows) (h : ∀ x ∈ observationWords rows, (f x).size ≤ b+1) :
    (f r.action.address).size ≤ b+1 ∧ (f r.action.value).size ≤ b+1 ∧ (f r.old).size ≤ b+1 := by
  have hwords : ∀ x ∈ [r.action.address,r.action.value,r.old], x ∈ observationWords rows :=
    fun x hx => List.mem_flatMap.mpr ⟨r,hr,hx⟩
  exact ⟨h _ (hwords _ (by simp)),h _ (hwords _ (by simp)),h _ (hwords _ (by simp))⟩

theorem compactRows_labels {b : ℕ} {dict : List WordEdge} {rows : List ObservedAccess}
    {f : ℕ → ℕ} (h : ∀ x ∈ observationWords rows, WordLabel b dict x (f x)) :
    List.Forall₂ (ObservedLabels b dict) rows (rows.map (compactRow f)) := by
  induction rows with
  | nil => exact .nil
  | cons r rr ih =>
    refine .cons ⟨⟨h _ ?_,h _ ?_,rfl⟩,fun _ => h _ ?_⟩ (ih ?_)
    · exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
    · exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
    · exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
    · intro x hx
      obtain ⟨s,hs,hmem⟩ := List.mem_flatMap.mp hx
      exact h _ (List.mem_flatMap.mpr ⟨s,List.mem_cons_of_mem _ hs,hmem⟩)

/-- On a well-formed layout, the fixed log-width parameter suffices to hold all
distinct prefixes and the total number of required rows is proportional to
the occupied payload divided by that width. -/
theorem memoryStream_labels {α : Assignment} {n t b : ℕ} (h : SlotsWellFormed α n t)
    (hb : 0 < b) (hWide : 18*layoutHorizon t < 2^b) :
    let rows := memoryStream α n t
    ∃ (dict : List WordEdge) (label : ℕ → ℕ),
      WordEdge.Interned dict ∧ label 0 = 0 ∧
      (∀ e ∈ dict, max e.parent e.child < 2^b) ∧
      (∀ x ∈ observationWords rows,
        WordLabel b dict x (label x) ∧ (label x).size ≤ b+1 ∧ (label x).size ≤ x.size+1) ∧
      b*dict.length ≤ 18*layoutHorizon t := by
  dsimp only
  let W := observationWords (memoryStream α n t)
  let M := layoutHorizon t
  have hlt : 2*(9*M) < 2^b := by
    rw [show 2*(9*M)=18*M by omega]
    exact hWide
  have hW : (W.map Nat.size).sum ≤ 9*M := memoryStream_word_budget h
  obtain ⟨d,f,hGood,hZero,hNum,hId,hLabel⟩ := wordLabels_exist_bounded W hW b hb hlt
  refine ⟨d,f,hGood,hZero,hId,hLabel,?_⟩
  have hB := (Nat.mul_le_mul_left b hNum).trans ((labelEntries_budget hb W).trans (Nat.mul_le_mul_left 2 hW))
  exact hB.trans (by dsimp [M]; omega)

/-- A compact record from a slot of width 2^j enters at most tier j+2,
including the tag and rounding to the next dyadic width. -/
theorem bounded_tier_of_slot {j a v : ℕ} (ha : a.size ≤ 2^j+1)
    (hv : v.size ≤ 2^j+1) : bitTier a v ≤ j+2 := by
  refine (bitTier_le ha hv).trans ?_
  apply Nat.size_le.mpr
  rw [Nat.pow_add]
  simp only [show (2:ℕ)^2=4 by decide]
  have hp : 0 < 2^j := by positivity
  omega

theorem tieredRow_eligible {s : ℕ × ℕ} {r : ObservedAccess} {f : ℕ → ℕ}
    (ha : (f r.action.address).size ≤ 2^s.2+1)
    (hv : (f r.action.value).size ≤ 2^s.2+1)
    (ho : (f r.old).size ≤ 2^s.2+1) :
    ∀ row ∈ tieredAccess bitTier (compactRow f r).action (compactRow f r).old,
      row.addr.1 ≤ s.2+2 := by
  have hDest := bounded_tier_of_slot ha hv
  have hSrc := bounded_tier_of_slot ha ho
  intro row hr
  unfold tieredAccess at hr
  dsimp only at hr
  split at hr
  · split at hr
    · obtain rfl := List.mem_singleton.mp hr
      exact hDest
    · simp only [List.mem_cons,List.not_mem_nil,or_false] at hr
      rcases hr with rfl|rfl
      · exact hSrc
      · exact hDest
  · obtain rfl := List.mem_singleton.mp hr
    exact hDest

theorem tieredObservations_fits {b : ℕ} {rows : List ObservedAccess} {f : ℕ → ℕ}
    (h : ∀ x ∈ observationWords rows, (f x).size ≤ b+1) :
    ∀ r ∈ tieredObservations bitTier (rows.map (compactRow f)), TierRecordFits (b+1) r := by
  intro row hr
  obtain ⟨r',h',h''⟩ := List.mem_flatMap.mp hr
  obtain ⟨raw,hRaw,rfl⟩ := List.mem_map.mp h'
  obtain ⟨ha,hv,ho⟩ := compactRow_fits hRaw h
  exact tieredAccess_fits ha hv ho row h''

/-- Exact checking of fixed chronological compact tier lanes by their batched
sort-and-snapshot certificates. Compact labels preserve even the old values
claimed at overwrites. -/
theorem observed_compactBatches_iff {b : ℕ} {dict : List WordEdge} {raw packed : List ObservedAccess}
    (good : WordEdge.Interned dict) (labels : List.Forall₂ (ObservedLabels b dict) raw packed)
    (fits : ∀ r ∈ tieredObservations bitTier packed, TierRecordFits (b+1) r)
    (count : ℕ → ℕ) (lanes : ℕ → List (Option LocalRecord))
    (proj : ∀ j < (b+1).size+1,
      (lanes j).filterMap id = atTier j (tieredObservations bitTier packed))
    (cap : ∀ j < (b+1).size+1, (lanes j).length ≤ 2^(2^j)*count j) :
    observedMemoryValid (fun _ => 0) raw ↔
      ∀ j < (b+1).size+1, TierBatchCertificate (2^(2^j)) (count j) (lanes j)
        (fun a => liveMemory bitTier (fun _ => 0) (j,a)) :=
  (observedMemoryValid_initial_iff_labels good labels).trans
    ((observedMemoryValid_iff_tieredObservations bitTier (fun _ => 0) packed).trans
      (compactMemoryCertificate_iff fits count lanes proj cap).symm)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

/-- The dyadic slot and local chunk number for a given tier and physical lane. -/
def chunkLaneSource (b j i : ℕ) : (ℕ × ℕ) × ℕ :=
  let q := 2^(j-b)
  ((i/q*2^j,j),i%q)

def physicalChunkLane (b a k : ℕ) : ℕ := a/2^b+k

theorem chunkLaneSource_point {b j i : ℕ} (h : b ≤ j) :
    let s := (chunkLaneSource b j i).1
    let k := (chunkLaneSource b j i).2
    2^b*i=s.1+2^b*k ∧ s.1 ≤ 2^b*i ∧ 2^b*i < s.1+2^s.2 := by
  let q := 2^(j-b)
  have hq : 0 < q := Nat.pow_pos (by decide)
  have hB : 0 < 2^b := Nat.pow_pos (by decide)
  have hW : 2^j=2^b*q := by
    unfold q
    rw [← Nat.pow_add,Nat.add_sub_of_le h]
  have hEq : 2^b*i=i/q*2^j+2^b*(i%q) := by
    calc
      _ = 2^b*(q*(i/q)+i%q) := congrArg (2^b*·) (Nat.div_add_mod i q).symm
      _ = _ := by rw [hW]; ring
  have hmod := Nat.mul_lt_mul_of_pos_left (Nat.mod_lt i hq) hB
  change 2^b*i=i/q*2^j+2^b*(i%q) ∧
    i/q*2^j ≤ 2^b*i ∧ 2^b*i < i/q*2^j+2^j
  rw [← hW] at hmod
  omega

theorem chunkLaneSource_mem {t b j i : ℕ} (hb : b ≤ j) (hj : j ≤ layoutHeight t)
    (hi : i < layoutHorizon t / 2^b) :
    (chunkLaneSource b j i).1 ∈ layoutSlots t := by
  obtain ⟨_,hlo,_⟩ := chunkLaneSource_point (i := i) hb
  have hB : 0 < 2^b := Nat.pow_pos (by decide)
  have hh := Nat.mul_lt_mul_of_pos_left hi hB
  have he := Nat.div_add_mod (layoutHorizon t) (2^b)
  have hHi : 2^b*i < layoutHorizon t := by omega
  apply layout_mem.mpr
  exact ⟨hlo.trans_lt hHi,hj,Nat.mul_mod_left _ _⟩

theorem chunkLaneSource_chunk_lt (b j i : ℕ) :
    (chunkLaneSource b j i).2 < 2^(j-b) :=
  Nat.mod_lt _ (Nat.pow_pos (by decide))

theorem chunkLaneSource_inverse {b j a k : ℕ} (hb : b ≤ j)
    (ha : a % 2^j = 0) (hk : k < 2^(j-b)) :
    chunkLaneSource b j (physicalChunkLane b a k) = ((a,j),k) := by
  let q := 2^(j-b)
  have hq : 0 < q := Nat.pow_pos (by decide)
  have hB : 0 < 2^b := Nat.pow_pos (by decide)
  have hW : 2^j=2^b*q := by
    unfold q
    rw [← Nat.pow_add,Nat.add_sub_of_le hb]
  have hA : 2^j*(a/2^j)=a := by
    simpa [ha] using Nat.div_add_mod a (2^j)
  have hA' : a/2^b = q*(a/2^j) := by
    calc
      _ = (2^j*(a/2^j))/2^b := congrArg (fun n : ℕ => n/2^b) hA.symm
      _ = (2^b*(q*(a/2^j)))/2^b := by rw [hW,Nat.mul_assoc]
      _ = _ := Nat.mul_div_cancel_left _ hB
  unfold chunkLaneSource physicalChunkLane
  dsimp only
  change ((((a/2^b+k)/q)*2^j,j),(a/2^b+k)%q) = _
  rw [hA',Nat.mul_add_div hq,Nat.mul_add_mod,Nat.div_eq_of_lt hk,
    Nat.add_zero,Nat.mod_eq_of_lt hk,Nat.mul_comm (a/2^j),hA]

theorem physicalChunkLane_lt {t b j a k : ℕ} (hS : (a,j) ∈ layoutSlots t)
    (hb : b ≤ j) (hk : k < 2^(j-b)) :
    physicalChunkLane b a k < layoutHorizon t/2^b := by
  obtain ⟨_,hj,ha⟩ := layout_mem.mp hS
  have hEq := chunkLaneSource_inverse hb ha hk
  have hP := chunkLaneSource_point (i := physicalChunkLane b a k) hb
  rw [hEq] at hP
  have hEnd := layoutSlot_end hS
  have hlt : 2^b*physicalChunkLane b a k < layoutHorizon t := hP.2.2.trans_le hEnd
  have hDiv : 2^b ∣ layoutHorizon t := Nat.pow_dvd_pow _ (hb.trans hj)
  have hE : 2^b*(layoutHorizon t/2^b) = layoutHorizon t := by
    simpa [Nat.mod_eq_zero_of_dvd hDiv] using
      Nat.div_add_mod (layoutHorizon t) (2^b)
  have hPos : 0 < 2^b := Nat.pow_pos (by decide)
  apply (Nat.mul_lt_mul_left hPos).mp
  simpa only [hE] using hlt

/-- Two occupied slots containing the same time point must be the same slot. -/
theorem liveSlot_unique_point {α : Assignment} {n t x : ℕ} (h : SlotsWellFormed α n t)
    {s r : ℕ × ℕ} (hs : s ∈ liveSlots α n t) (hr : r ∈ liveSlots α n t)
    (hsx : s.1 ≤ x ∧ x < s.1+2^s.2) (hrx : r.1 ≤ x ∧ x < r.1+2^r.2) : s=r := by
  obtain ⟨i,hi,his⟩ := List.mem_iff_getElem.mp hs
  obtain ⟨j,hj,hjr⟩ := List.mem_iff_getElem.mp hr
  have hp := List.pairwise_iff_getElem.mp h.1
  rcases lt_trichotomy i j with hlt | he | hgt
  · have he := hp i j hi hj hlt
    rw [his,hjr] at he
    omega
  · subst j
    exact his.symm.trans hjr
  · have he := hp j i hj hi hgt
    rw [his,hjr] at he
    omega

/-- Candidate tiers can share every physical lane; at most one contributes
from the occupied schedule for any given lane. -/
theorem chunkLaneSource_unique {α : Assignment} {n t b i j k : ℕ}
    (h : SlotsWellFormed α n t) (hj : b ≤ j) (hk : b ≤ k)
    (hJ : (chunkLaneSource b j i).1 ∈ liveSlots α n t)
    (hK : (chunkLaneSource b k i).1 ∈ liveSlots α n t) : j=k := by
  have hPJ := (chunkLaneSource_point (i := i) hj).2
  have hPK := (chunkLaneSource_point (i := i) hk).2
  exact congrArg Prod.snd (liveSlot_unique_point h hJ hK hPJ hPK)

/-- One candidate per physical lane per eligible tier, independent of the trace. -/
def chunkPoolSources (t b : ℕ) : List ((ℕ × ℕ) × ℕ) :=
  ((List.range (layoutHeight t+1-b)).map (fun j => b+j)).flatMap (fun j =>
    (List.range (layoutHorizon t/2^b)).map (chunkLaneSource b j))

theorem chunkPoolSources_length (t b : ℕ) :
    (chunkPoolSources t b).length = (layoutHeight t+1-b)*(layoutHorizon t/2^b) := by
  have h (ls : List ℕ) :
      (ls.flatMap (fun j =>
        (List.range (layoutHorizon t/2^b)).map (chunkLaneSource b j))).length =
        ls.length*(layoutHorizon t/2^b) := by
    induction ls with
    | nil => simp
    | cons i is ih =>
      simp [ih,Nat.succ_mul,Nat.add_comm]
  rw [chunkPoolSources,h]
  simp

theorem chunkPoolSources_wire_budget (t b width factor : ℕ) (hw : width ≤ factor*2^b) :
    (chunkPoolSources t b).length*width ≤ factor*(layoutHeight t+1)*layoutHorizon t := by
  have hq := Nat.div_mul_le_self (layoutHorizon t) (2^b)
  have hh := Nat.sub_le (layoutHeight t+1) b
  rw [chunkPoolSources_length]
  calc
    _ ≤ ((layoutHeight t+1-b)*(layoutHorizon t/2^b))*(factor*2^b) :=
      Nat.mul_le_mul_left _ hw
    _ = factor*(layoutHeight t+1-b)*((layoutHorizon t/2^b)*2^b) := by ring
    _ ≤ _ := Nat.mul_le_mul (Nat.mul_le_mul_left _ hh) hq

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

/-- Reserve room for the short/long tag and tier rounding by permitting a row
to move up two tiers. Narrowen its lane spacing accordingly. -/
def tierLane (j a : ℕ) : ℕ := physicalChunkLane (j-2) a 0

theorem tierLane_lt {t j a k : ℕ} (hs : (a,k) ∈ layoutSlots t) (hj : j ≤ k+2) :
    tierLane j a < layoutHorizon t / 2^(j-2) := by
  exact physicalChunkLane_lt hs (by omega) (Nat.pow_pos (by decide))

theorem tierLane_occupied_unique {a c k l j n t : ℕ} {α : Assignment}
    (h : SlotsWellFormed α n t)
    (hs : (a,k) ∈ liveSlots α n t) (hr : (c,l) ∈ liveSlots α n t)
    (hk : j ≤ k+2) (hl : j ≤ l+2)
    (hEq : tierLane j a = tierLane j c) :
    (a,k)=(c,l) := by
  have hm {x y : ℕ} (hxy : (x,y) ∈ liveSlots α n t) :
      x % 2^y = 0 := (layout_mem.mp (List.mem_filter.mp hxy).1).2.2
  have hbk : j-2 ≤ k := by omega
  have hbl : j-2 ≤ l := by omega
  have hKa : chunkLaneSource (j-2) k (tierLane j a) = ((a,k),0) :=
    chunkLaneSource_inverse hbk (hm hs) (Nat.pow_pos (by decide))
  have hLc : chunkLaneSource (j-2) l (tierLane j c) = ((c,l),0) :=
    chunkLaneSource_inverse hbl (hm hr) (Nat.pow_pos (by decide))
  have hP := chunkLaneSource_point (i := tierLane j a) hbk
  have hQ := chunkLaneSource_point (i := tierLane j c) hbl
  rw [hKa] at hP
  rw [hLc,← hEq] at hQ
  exact liveSlot_unique_point h hs hr hP.2 hQ.2

private def slotBitLanes (t : ℕ) : List ((ℕ × ℕ) × ℕ) :=
  (layoutSlots t).flatMap fun s => (List.range (2^s.2)).map (s,·)

private theorem slotBitLanes_nodup (t : ℕ) : (slotBitLanes t).Nodup := by
  unfold slotBitLanes
  rw [List.nodup_flatMap]
  constructor
  · intro s _
    exact List.nodup_range.map (fun _ _ he => (Prod.mk.inj he).2)
  · apply (layout_nodup t).imp
    intro s r hsr
    apply List.disjoint_left.mpr
    intro q hq hQ
    obtain ⟨u,_,rfl⟩ := List.mem_map.mp hq
    obtain ⟨v,_,hv⟩ := List.mem_map.mp hQ
    exact hsr (Prod.mk.inj hv).1.symm

private theorem slotBitLanes_subset (t : ℕ) : slotBitLanes t ⊆ chunkPoolSources t 0 := by
  intro x hx
  obtain ⟨s,hs,hX⟩ := List.mem_flatMap.mp hx
  obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hX
  rcases s with ⟨a,k⟩
  obtain ⟨ha,hk,hAlign⟩ := layout_mem.mp hs
  simp only [List.mem_range] at hj
  have hk' : j < 2^(k-0) := by simpa using hj
  have hR := physicalChunkLane_lt (b := 0) hs (Nat.zero_le _) hk'
  unfold chunkPoolSources
  apply List.mem_flatMap.mpr
  refine ⟨k,?_,?_⟩
  · simp
    omega
  · apply List.mem_map.mpr
    exact ⟨physicalChunkLane 0 a j,List.mem_range.mpr hR,
      chunkLaneSource_inverse (Nat.zero_le _) hAlign hk'⟩

theorem layoutSlots_totalWidth_le (t : ℕ) :
    ((layoutSlots t).map fun s => 2^s.2).sum ≤ (layoutHeight t+1)*layoutHorizon t := by
  have h := (slotBitLanes_nodup t).length_le_of_subset (slotBitLanes_subset t)
  simpa [slotBitLanes,List.length_flatMap,chunkPoolSources_length] using h

/-- A potential record from a width 2^k slot can have a destination tier j
among 0 through k+2. Generate exactly these candidates. -/
def tierPoolCandidates (t : ℕ) : List ((ℕ × ℕ) × ℕ) :=
  (layoutSlots t).flatMap fun s => (List.range (s.2+3)).map (s,·)

private theorem rangeWidthSum (n : ℕ) :
    ((List.range n).map (fun k => (2:ℕ)^k)).sum+1 = 2^n := by
  induction n with
  | zero => decide
  | succ n ih =>
    rw [List.range_succ,List.map_append,List.sum_append,List.map_singleton,List.sum_singleton,Nat.pow_succ]
    omega

theorem tierPoolCandidates_totalWidth (t : ℕ) :
    ((tierPoolCandidates t).map fun x => 2^x.2).sum ≤
      8*(layoutHeight t+1)*layoutHorizon t := by
  unfold tierPoolCandidates
  rw [List.map_flatMap]
  have split {α : Type} (f : α → List ℕ) (xs : List α) :
      (xs.flatMap f).sum = (xs.map fun x => (f x).sum).sum := by
    induction xs with
    | nil => rfl
    | cons x xs ih => simp [List.sum_append,ih]
  rw [split]
  have h : ((layoutSlots t).map
    (fun s => (((List.range (s.2+3)).map (s,·)).map (fun x => (2:ℕ)^x.2)).sum)).sum ≤
      ((layoutSlots t).map fun s => 8*2^s.2).sum := by
    apply List.sum_le_sum
    intro s _
    simp only [List.map_map,Function.comp_def]
    have hh := rangeWidthSum (s.2+3)
    rw [Nat.pow_add] at hh
    omega
  rw [List.sum_map_mul_left] at h
  exact h.trans (by
    rw [Nat.mul_assoc]
    exact Nat.mul_le_mul_left _ (layoutSlots_totalWidth_le t))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.RobsonCNF

open CookLevin

/-- Require each cut list to contain exactly one true flag. The Boolean prefix
accumulators use one gate and one clause per lane, without testing pairs of lanes. -/
def cutMarkerGates (markers : List ℕ) (acc : ℕ → ℕ) : List Gate :=
  .pin (acc 0) false :: .pin (acc markers.length) true ::
    (markers.zipIdx.flatMap fun p =>
      [.disj (acc (p.2+1)) (acc p.2) p.1,
        .assert [.Neg (acc p.2),.Neg p.1]])

theorem cutMarkerGates_length (markers : List ℕ) (acc : ℕ → ℕ) :
    (cutMarkerGates markers acc).length = 2+2*markers.length := by
  unfold cutMarkerGates
  simp only [List.length_cons]
  have H {α : Type} (xs : List α) (f : α → List Gate) (h : ∀ x, (f x).length = 2) :
      (xs.flatMap f).length = 2*xs.length := by
    induction xs with
    | nil => rfl
    | cons y ys ih => simp [h,ih,Nat.mul_succ] <;> omega
  rw [H _ _ (fun _ => rfl),List.length_zipIdx]
  omega

private theorem marker_mem_zipIdx (markers : List ℕ) (i : Fin markers.length) :
    (markers[i.val],i.val) ∈ markers.zipIdx := by
  have hh := List.getElem_mem (l := markers.zipIdx) (n := i.val) (by simpa using i.isLt)
  simpa using hh

theorem cutMarkerGates_local (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment) :
    (∀ g ∈ cutMarkerGates markers acc, g.Holds α) ↔
      α (acc 0) = false ∧ α (acc markers.length) = true ∧
      ∀ i : Fin markers.length,
        α (acc (i.val+1)) = (α (acc i.val) || α markers[i.val]) ∧
        ¬ (α (acc i.val) = true ∧ α markers[i.val] = true) := by
  constructor
  · intro h
    refine ⟨h (.pin (acc 0) false) (by simp [cutMarkerGates]),
      h (.pin (acc markers.length) true) (by simp [cutMarkerGates]),?_⟩
    intro i
    have hmem := marker_mem_zipIdx markers i
    have g1 : Gate.disj (acc (i.val+1)) (acc i.val) markers[i.val] ∈
        cutMarkerGates markers acc := by
      simp only [cutMarkerGates,List.mem_cons]
      exact Or.inr (Or.inr (List.mem_flatMap.mpr ⟨_,hmem,by simp⟩))
    have g2 : Gate.assert [.Neg (acc i.val),.Neg markers[i.val]] ∈
        cutMarkerGates markers acc := by
      simp only [cutMarkerGates,List.mem_cons]
      exact Or.inr (Or.inr (List.mem_flatMap.mpr ⟨_,hmem,by simp⟩))
    have h2 := h _ g2
    refine ⟨h _ g1,?_⟩
    cases hA : α (acc i.val) <;> cases hB : α markers[i.val] <;>
      simp_all [Gate.Holds,satisfiesClause,satisfiesLiteral]
  · rintro ⟨h0,h1,h⟩ g hg
    simp only [cutMarkerGates,List.mem_cons] at hg
    rcases hg with rfl | rfl | hg
    · exact h0
    · exact h1
    · obtain ⟨⟨r,j⟩,hR,hM⟩ := List.mem_flatMap.mp hg
      obtain ⟨i,hi,hI⟩ := List.mem_iff_getElem.mp hR
      have hi' : i < markers.length := by simpa using hi
      have he : (markers[i]'hi',i)=(r,j) := by simpa using hI
      obtain ⟨he₁,he₂⟩ := Prod.mk.inj he
      subst r
      subst j
      have hj := h ⟨i,hi'⟩
      rcases List.mem_cons.mp hM with rfl | hM
      · exact hj.1
      · have hLast := List.mem_singleton.mp hM
        subst g
        have hN := hj.2
        cases hA : α (acc i) <;> cases hB : α (markers[i]'hi') <;>
          simp_all [Gate.Holds,satisfiesClause,satisfiesLiteral]

/-- Exact meaning of the enabled markers without mentioning their prefix wires. -/
def OneCut (α : Assignment) (markers : List ℕ) : Prop :=
  ∃ j : Fin markers.length, ∀ i : Fin markers.length,
    α markers[i.val] = decide (i=j)

private theorem prefixEq (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
    (h0 : α (acc 0)=false)
    (h : ∀ i : Fin markers.length,
      α (acc (i.val+1)) = (α (acc i.val) || α markers[i.val]))
    (m : ℕ) (hm : m ≤ markers.length) :
    α (acc m)=true ↔ ∃ k : Fin markers.length, k.val < m ∧ α markers[k.val]=true := by
  induction m with
  | zero => simp [h0]
  | succ m ih =>
    let i : Fin markers.length := ⟨m,by omega⟩
    have he := h i
    change α (acc (m+1)) = (α (acc m) || α markers[i.val]) at he
    rw [he,Bool.or_eq_true,ih (by omega)]
    constructor
    · rintro (⟨k,hk,hK⟩ | hI)
      · exact ⟨k,by omega,hK⟩
      · exact ⟨i,by simp [i],hI⟩
    · rintro ⟨k,hk,hK⟩
      by_cases e : k.val=m
      · have hh : k=i := Fin.ext e
        exact Or.inr (hh ▸ hK)
      · exact Or.inl ⟨k,by omega,hK⟩

theorem cutMarkerGates_sound (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
    (h : ∀ g ∈ cutMarkerGates markers acc, g.Holds α) : OneCut α markers := by
  obtain ⟨h0,hN,h⟩ := (cutMarkerGates_local markers acc α).mp h
  have hEq := prefixEq markers acc α h0 (fun i => (h i).1)
  obtain ⟨j,hj,hJT⟩ := (hEq _ le_rfl).mp hN
  refine ⟨j,?_⟩
  intro i
  by_cases e : i=j
  · subst i
    simpa using hJT
  · have hI : α markers[i.val] ≠ true := by
      intro hTrue
      have hi' : i.val ≠ j.val := fun hEq => e (Fin.ext hEq)
      rcases Nat.lt_or_gt_of_ne hi' with hLt | hGt
      · exact (h j).2 ⟨(hEq j.val j.isLt.le).mpr ⟨i,hLt,hTrue⟩,hJT⟩
      · exact (h i).2 ⟨(hEq i.val i.isLt.le).mpr ⟨j,hGt,hJT⟩,hTrue⟩
    cases he : α markers[i.val] <;> simp_all

def cutPrefix (α : Assignment) (markers : List ℕ) (i : ℕ) : Bool :=
  (markers.take i).any α

theorem cutPrefix_true (α : Assignment) (markers : List ℕ) (i : ℕ) :
    cutPrefix α markers i = true ↔
      ∃ k : Fin markers.length, k.val < i ∧ α markers[k.val]=true := by
  unfold cutPrefix
  rw [List.any_eq_true]
  constructor
  · rintro ⟨v,hv,hT⟩
    obtain ⟨j,hj,rfl⟩ := List.mem_iff_getElem.mp hv
    have hi : j < i := by rw [List.length_take] at hj; omega
    have hLength : j < markers.length := by rw [List.length_take] at hj; omega
    exact ⟨⟨j,hLength⟩,hi, by simpa using hT⟩
  · rintro ⟨j,hi,hT⟩
    have hj : j.val < (markers.take i).length := by
      rw [List.length_take]; exact lt_min hi j.isLt
    exact ⟨(markers.take i)[j.val]'hj,List.getElem_mem hj,by simpa using hT⟩

theorem cutMarkerGates_complete (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
    (h : OneCut α markers)
    (hAcc : ∀ i ≤ markers.length, α (acc i)=cutPrefix α markers i) :
    ∀ g ∈ cutMarkerGates markers acc, g.Holds α := by
  obtain ⟨j,h⟩ := h
  apply (cutMarkerGates_local markers acc α).mpr
  refine ⟨(hAcc 0 (by omega)).trans rfl,?_,?_⟩
  · rw [hAcc _ le_rfl,cutPrefix_true]
    exact ⟨j,j.isLt, by simp [h j]⟩
  · intro i
    refine ⟨?_,?_⟩
    · rw [hAcc (i.val+1) (by omega),hAcc i.val i.isLt.le]
      unfold cutPrefix
      rw [List.take_succ_eq_append_getElem i.isLt,List.any_append]
      simp
    · rintro ⟨hPrev,hTrue⟩
      rw [hAcc i.val i.isLt.le,cutPrefix_true] at hPrev
      obtain ⟨k,hlt,hK⟩ := hPrev
      have e : k=j := of_decide_eq_true ((h k).symm.trans hK)
      have f : i=j := of_decide_eq_true ((h i).symm.trans hTrue)
      rw [e,f] at hlt
      exact (Nat.lt_irrefl _ hlt)

end CNFEncComplexity.RobsonCNF

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- A candidate lane consists of an enable bit and a fixed-width payload. -/
abbrev GatherCandidate (w : ℕ) := ℕ × (Fin w → ℕ)

def guardEqual (guard src dest : ℕ) : List Gate :=
  [.assert [.Neg guard,.Neg src,.Pos dest],
   .assert [.Neg guard,.Pos src,.Neg dest]]

theorem guardEqual_exact (a : Assignment) (guard src dest : ℕ) :
    (∀ g ∈ guardEqual guard src dest, g.Holds a) ↔
      (a guard=true → a src=a dest) := by
  cases hc : a guard <;> cases hs : a src <;> cases hd : a dest <;>
    simp [guardEqual,Gate.Holds,satisfiesClause,satisfiesLiteral,hc,hs,hd]

def gatherEntry {w : ℕ} (acc : ℕ → ℕ) (out : Fin w → ℕ)
    (j : ℕ) (candidate : GatherCandidate w) : List Gate :=
  .disj (acc (j+1)) (acc j) candidate.1 ::
    .assert [.Neg (acc j), .Neg candidate.1] ::
    (List.finRange w).flatMap (fun i => guardEqual candidate.1 (candidate.2 i) (out i))

def gatherGates {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (candidates : List (GatherCandidate w)) : List Gate :=
  .pin (acc 0) false :: .copy active (acc candidates.length) ::
    (List.finRange candidates.length).flatMap (fun j => gatherEntry acc out j.val candidates[j.val])

private theorem gatherEntry_exact (a : Assignment) {w : ℕ} (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (j : ℕ) (c : GatherCandidate w) :
    (∀ g ∈ gatherEntry acc out j c, g.Holds a) ↔
      a (acc (j+1)) = (a (acc j) || a c.1) ∧
      ¬(a (acc j)=true ∧ a c.1=true) ∧
      (a c.1=true → ∀ i, a (c.2 i) = a (out i)) := by
  have hn : Gate.Holds a (.assert [.Neg (acc j),.Neg c.1]) ↔ ¬(a (acc j)=true ∧ a c.1=true) := by
    cases hP : a (acc j) <;> cases hC : a c.1 <;>
      simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hP,hC]
  constructor
  · intro h
    refine ⟨h (.disj (acc (j+1)) (acc j) c.1) (by simp [gatherEntry]),hn.mp (h _ (by simp [gatherEntry])),?_⟩
    intro hg i
    apply (guardEqual_exact a c.1 (c.2 i) (out i)).mp _ hg
    intro g hG
    exact h g (List.mem_cons_of_mem _ (List.mem_cons_of_mem _
      (List.mem_flatMap.mpr ⟨i,List.mem_finRange _,hG⟩)))
  · rintro ⟨hOr,hA,hEq⟩ g hg
    simp only [gatherEntry,List.mem_cons] at hg
    rcases hg with rfl | rfl | hg
    · exact hOr
    · exact hn.mpr hA
    · obtain ⟨i,_,hG⟩ := List.mem_flatMap.mp hg
      exact (guardEqual_exact _ _ _ _).mpr (fun h => hEq h i) _ hG

theorem gatherGates_local (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (candidates : List (GatherCandidate w)) :
    (∀ g ∈ gatherGates active acc out candidates, g.Holds a) ↔
      a (acc 0)=false ∧ a active=a (acc candidates.length) ∧
      ∀ j : Fin candidates.length,
        a (acc (j.val+1)) = (a (acc j.val) || a candidates[j.val].1) ∧
        ¬(a (acc j.val)=true ∧ a candidates[j.val].1=true) ∧
        (a candidates[j.val].1=true → ∀ i, a (candidates[j.val].2 i) = a (out i)) := by
  constructor
  · intro h
    refine ⟨h (.pin (acc 0) false) (by simp [gatherGates]),
      h (.copy active (acc candidates.length)) (by simp [gatherGates]),?_⟩
    intro j
    apply (gatherEntry_exact a acc out j.val candidates[j.val]).mp
    intro g hG
    exact h g (List.mem_cons_of_mem _ (List.mem_cons_of_mem _
      (List.mem_flatMap.mpr ⟨j,List.mem_finRange _,hG⟩)))
  · rintro ⟨hPin,hCopy,hLocal⟩ g hg
    simp only [gatherGates,List.mem_cons] at hg
    rcases hg with rfl | rfl | hg
    · exact hPin
    · exact hCopy
    · obtain ⟨j,_,hG⟩ := List.mem_flatMap.mp hg
      exact (gatherEntry_exact a acc out j.val candidates[j.val]).mpr (hLocal j) g hG

/-- The prefix oracle can see exactly whether some prior candidate is enabled. -/
def GatherSeen (a : Assignment) {w : ℕ} (cs : List (GatherCandidate w)) (j : ℕ) : Prop :=
  ∃ k : Fin cs.length, k.val < j ∧ a cs[k.val].1=true

private theorem GatherSeen_succ (a : Assignment) {w : ℕ} (cs : List (GatherCandidate w))
    (i : Fin cs.length) :
    GatherSeen a cs (i.val+1) ↔ GatherSeen a cs i.val ∨ a cs[i.val].1=true := by
  constructor
  · rintro ⟨k,hk,hK⟩
    by_cases h : k=i
    · subst k
      exact Or.inr hK
    · have hh : k.val ≠ i.val := fun he => h (Fin.ext he)
      exact Or.inl ⟨k,by omega,hK⟩
  · rintro (⟨k,hK,hQ⟩ | hQ)
    · exact ⟨k,by omega,hQ⟩
    · exact ⟨i,by omega,hQ⟩

private theorem gather_prefix_sound (a : Assignment) {w : ℕ} (acc : ℕ → ℕ)
    (cs : List (GatherCandidate w)) (h₀ : a (acc 0)=false)
    (hS : ∀ j : Fin cs.length,
      a (acc (j.val+1)) = (a (acc j.val) || a cs[j.val].1)) :
    ∀ j ≤ cs.length, a (acc j)=true ↔ GatherSeen a cs j := by
  intro j
  induction j with
  | zero => simp [h₀,GatherSeen]
  | succ j ih =>
    intro hj
    let i : Fin cs.length := ⟨j,by omega⟩
    change a (acc (i.val+1))=true ↔ GatherSeen a cs (i.val+1)
    rw [hS i,GatherSeen_succ,Bool.or_eq_true,ih (by omega)]

theorem gatherGates_sound (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (cs : List (GatherCandidate w))
    (h : ∀ g ∈ gatherGates active acc out cs, g.Holds a) :
    (a active=true ↔ ∃ i : Fin cs.length, a cs[i.val].1=true) ∧
    (∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j) ∧
    (∀ i : Fin cs.length, a cs[i.val].1=true → ∀ k, a (cs[i.val].2 k)=a (out k)) := by
  obtain ⟨h₀,hLast,hStep⟩ := (gatherGates_local a active acc out cs).mp h
  have hSeen := gather_prefix_sound a acc cs h₀ (fun i => (hStep i).1)
  refine ⟨?_,?_,fun i => (hStep i).2.2⟩
  · rw [hLast,hSeen _ le_rfl]
    exact ⟨fun ⟨i,_,hI⟩ => ⟨i,hI⟩,fun ⟨i,hI⟩ => ⟨i,i.isLt,hI⟩⟩
  · intro i j hI hJ
    rcases lt_trichotomy i.val j.val with hlt | he | hgt
    · exact False.elim ((hStep j).2.1 ⟨(hSeen _ j.isLt.le).2 ⟨i,hlt,hI⟩,hJ⟩)
    · exact Fin.ext he
    · exact False.elim ((hStep i).2.1 ⟨(hSeen _ i.isLt.le).2 ⟨j,hgt,hJ⟩,hI⟩)

theorem gatherGates_complete (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (cs : List (GatherCandidate w))
    (hA : a active=true ↔ ∃ i : Fin cs.length, a cs[i.val].1=true)
    (hU : ∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j)
    (hV : ∀ i : Fin cs.length, a cs[i.val].1=true → ∀ k, a (cs[i.val].2 k)=a (out k))
    (hP : ∀ j ≤ cs.length, a (acc j)=true ↔ GatherSeen a cs j) :
    ∀ g ∈ gatherGates active acc out cs, g.Holds a := by
  refine (gatherGates_local a active acc out cs).mpr ⟨?_,?_,?_⟩
  · have h := hP 0 (by omega)
    simp [GatherSeen] at h
    cases he : a (acc 0) <;> simp_all
  · apply Bool.eq_iff_iff.mpr
    rw [hA,hP _ le_rfl]
    exact ⟨fun ⟨i,hI⟩ => ⟨i,i.isLt,hI⟩,fun ⟨i,_,hI⟩ => ⟨i,hI⟩⟩
  · intro i
    refine ⟨?_,?_,hV i⟩
    · apply Bool.eq_iff_iff.mpr
      rw [Bool.or_eq_true,hP _ (by omega),hP _ i.isLt.le]
      exact GatherSeen_succ a cs i
    · rintro ⟨hI,hJ⟩
      obtain ⟨j,hJlt,hE⟩ := (hP _ i.isLt.le).mp hI
      exact (Nat.ne_of_lt hJlt) (congrArg Fin.val (hU j i hE hJ))

private theorem constantFlatMapLength {α β : Type} (f : α → List β) (k : ℕ)
    (hf : ∀ x, (f x).length=k) (l : List α) :
    (l.flatMap f).length = k*l.length := by
  induction l with
  | nil => simp
  | cons x xs ih => simp [hf,ih,Nat.mul_succ,Nat.add_comm]

theorem gatherGates_length {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (cs : List (GatherCandidate w)) :
    (gatherGates active acc out cs).length = 2+(2+2*w)*cs.length := by
  have hEntry (j : Fin cs.length) : (gatherEntry acc out j.val cs[j.val]).length=2+2*w := by
    simp only [gatherEntry,List.length_cons]
    rw [constantFlatMapLength _ 2 (fun _ => rfl),List.length_finRange]
    omega
  simp only [gatherGates,List.length_cons]
  rw [constantFlatMapLength _ (2+2*w) hEntry,List.length_finRange]
  omega

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Toggle the second channel of a pair exactly when its control is true. -/
def pairSwitch {A : Type} (controls : A → Bool) : A × Bool ≃ A × Bool where
  toFun p := (p.1, if controls p.1 then !p.2 else p.2)
  invFun p := (p.1, if controls p.1 then !p.2 else p.2)
  left_inv := by rintro ⟨a,b⟩; by_cases h : controls a <;> simp [h]
  right_inv := by rintro ⟨a,b⟩; by_cases h : controls a <;> simp [h]

private theorem pairSwitch_fst {A : Type} (c : A → Bool) (q : A × Bool) :
    (pairSwitch c q).1 = q.1 := rfl

private theorem route_one_side {A : Type} [Finite A] (σ : A × Bool ≃ A × Bool) :
    ∃ (e : A ≃ A) (left right : A → Bool),
      ∀ a, σ (a,left a) = (e a,right (e a)) := by
  classical
  let N (a : A) : Finset A := {(σ (a,false)).1, (σ (a,true)).1}
  have hall (s : Finset A) : s.card ≤ (s.biUnion N).card := by
    have hs : (s ×ˢ (Finset.univ : Finset Bool)).map σ.toEmbedding ⊆
        (s.biUnion N) ×ˢ Finset.univ := by
      intro x hx
      obtain ⟨⟨a,b⟩,hi,rfl⟩ := Finset.mem_map.mp hx
      refine Finset.mem_product.mpr ⟨?_,Finset.mem_univ _⟩
      apply Finset.mem_biUnion.mpr
      exact ⟨a,(Finset.mem_product.mp hi).1,by cases b <;> simp [N]⟩
    have h := Finset.card_le_card hs
    simp only [Finset.card_map,Finset.card_product,Finset.card_univ,Fintype.card_bool] at h
    omega
  obtain ⟨f,hf,hm⟩ := (Finset.all_card_le_biUnion_card_iff_existsInjective' N).mp hall
  let e := Equiv.ofBijective f ⟨hf, Finite.surjective_of_injective hf⟩
  have hex (a : A) : ∃ b : Bool, (σ (a,b)).1 = e a := by
    have h := hm a
    change f a ∈ N a at h
    simp only [N, Finset.mem_insert, Finset.mem_singleton] at h
    rcases h with h | h
    · exact ⟨false,h.symm⟩
    · exact ⟨true,h.symm⟩
  choose left hleft using hex
  let right (a : A) := (σ (e.symm a,left (e.symm a))).2
  refine ⟨e,left,right,?_⟩
  intro a
  exact Prod.ext (hleft a) (by simp [right])

/-- Any permutation of paired wires splits into one column of pair switches, then
independent permutations of the two channels, then one more column of switches. -/
theorem split_pair_permutation {A : Type} [Finite A] (σ : A × Bool ≃ A × Bool) :
    ∃ (entry exit : A → Bool) (middle : Bool → A ≃ A),
      ∀ p, let x := pairSwitch entry p
        σ p = pairSwitch exit (middle x.2 x.1, x.2) := by
  classical
  obtain ⟨e,l,r,hr⟩ := route_one_side σ
  let σ' := ((pairSwitch l).trans σ).trans (pairSwitch r).symm
  have hzero (a : A) : σ' (a,false) = (e a,false) := by
    change (pairSwitch r).symm (σ (pairSwitch l (a,false))) = _
    have h : pairSwitch l (a,false) = (a,l a) := by cases h : l a <;> simp [pairSwitch,h]
    rw [h,hr]
    cases h : r (e a) <;> simp [pairSwitch,h]
  have hone (a : A) : (σ' (a,true)).2 = true := by
    cases h : (σ' (a,true)).2
    · have h' : σ' (a,true) = σ' (e.symm (σ' (a,true)).1,false) := by
        rw [hzero,e.apply_symm_apply]
        exact Prod.ext rfl h
      have h'' := congrArg Prod.snd (σ'.injective h')
      exact Bool.noConfusion h''
    · rfl
  let f (a : A) := (σ' (a,true)).1
  have hinj : Function.Injective f := by
    intro x y hxy
    have h : σ' (x,true) = σ' (y,true) := Prod.ext hxy ((hone x).trans (hone y).symm)
    exact congrArg Prod.fst (σ'.injective h)
  let e₁ := Equiv.ofBijective f ⟨hinj,Finite.surjective_of_injective hinj⟩
  let middle (b : Bool) := if b then e₁ else e
  have hs (p : A × Bool) : σ' p = (middle p.2 p.1,p.2) := by
    obtain ⟨a,b⟩ := p
    cases b
    · exact hzero a
    · exact Prod.ext rfl (hone a)
  refine ⟨l,r,middle,?_⟩
  intro p
  let x := pairSwitch l p
  have hx : pairSwitch l x = p := (pairSwitch l).symm_apply_apply p
  have f := hs x
  change (pairSwitch r).symm (σ (pairSwitch l x)) = _ at f
  rw [hx] at f
  exact (Equiv.symm_apply_eq _).mp f

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Wires are numbered recursively in pairs. -/
def Wire : ℕ → Type
  | 0 => Unit
  | h+1 => Wire h × Bool

instance (h : ℕ) : Fintype (Wire h) := by
  induction h with
  | zero => exact inferInstanceAs (Fintype Unit)
  | succ h inst =>
    letI := inst
    exact inferInstanceAs (Fintype (Wire h × Bool))

theorem wire_card (h : ℕ) : Fintype.card (Wire h) = 2^h := by
  induction h with
  | zero => rfl
  | succ h ih =>
    change Fintype.card (Wire h × Bool) = _
    rw [Fintype.card_prod, Fintype.card_bool, ih, pow_succ]

/-- Switch settings for a recursive permutation network. Each nontrivial level adds
one entry column and one exit column, and recursively routes both channels. -/
def Setting : ℕ → Type
  | 0 => Unit
  | h+1 => (Wire h → Bool) × (Bool → Setting h) × (Wire h → Bool)

/-- Every switch setting induces a permutation of wires. -/
def routing : (h : ℕ) → Setting h → (Wire h ≃ Wire h)
  | 0, _ => Equiv.refl _
  | h+1, (entry,mid,exit) =>
    let interior : Wire h × Bool ≃ Wire h × Bool :=
      { toFun := fun q => (routing h (mid q.2) q.1,q.2)
        invFun := fun q => ((routing h (mid q.2)).symm q.1,q.2)
        left_inv := by rintro ⟨x,b⟩; simp
        right_inv := by rintro ⟨x,b⟩; simp }
    ((pairSwitch entry).trans interior).trans (pairSwitch exit)

theorem routing_succ {h : ℕ} (entry : Wire h → Bool) (mid : Bool → Setting h)
    (exit : Wire h → Bool) (x : Wire h × Bool) :
    routing (h+1) (entry,mid,exit) x =
      pairSwitch exit (routing h (mid (pairSwitch entry x).2) (pairSwitch entry x).1,
        (pairSwitch entry x).2) := rfl

/-- A network of height h routes every permutation of its two-to-the-h wires. -/
theorem routing_universal (h : ℕ) (σ : Wire h ≃ Wire h) :
    ∃ setting : Setting h, routing h setting = σ := by
  induction h with
  | zero =>
    refine ⟨(),Equiv.ext fun _ => ?_⟩
    apply Subsingleton.elim (α := Unit)
  | succ h ih =>
    obtain ⟨entry,exit,mid,hσ⟩ := split_pair_permutation (A := Wire h) σ
    choose c hc using fun b => ih (mid b)
    refine ⟨(entry,c,exit), Equiv.ext fun q => ?_⟩
    let q' : Wire h × Bool := q
    let z := pairSwitch entry q'
    have h₁ := routing_succ entry c exit q'
    have h₂ : pairSwitch exit (routing h (c z.2) z.1,z.2) = σ q' := by
      rw [hc]
      exact (hσ q').symm
    exact h₁.trans h₂

/-- The network has two columns of half as many switches as there are wires and
two copies of the preceding network. -/
def switchCount : ℕ → ℕ
  | 0 => 0
  | h+1 => 2^h+2*switchCount h+2^h

theorem switchCount_exact (h : ℕ) : switchCount h = h*2^h := by
  induction h with
  | zero => rfl
  | succ h ih => rw [switchCount,ih,pow_succ]; ring

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

private def wires : (h : ℕ) → List (Wire h)
  | 0 => [()]
  | h+1 => (wires h).flatMap fun x => [(x,false),(x,true)]

private theorem wires_length (h : ℕ) : (wires h).length = 2^h := by
  induction h with
  | zero => rfl
  | succ h ih =>
    change ((wires h).flatMap (fun x => [(x,false),(x,true)])).length = 2^(h+1)
    rw [List.length_flatMap]
    change ((wires h).map (Function.const _ 2)).sum = _
    rw [List.map_const,List.sum_replicate,ih,pow_succ]
    exact nsmul_eq_mul _ _

private theorem wires_mem (h : ℕ) (x : Wire h) : x ∈ wires h := by
  induction h with
  | zero =>
    change x ∈ ([()] : List Unit)
    cases x
    exact List.mem_cons_self
  | succ h ih =>
    let y : Wire h × Bool := x
    change y ∈ (wires h).flatMap fun a => [(a,false),(a,true)]
    apply List.mem_flatMap.mpr
    refine ⟨y.1,ih _,?_⟩
    rcases y with ⟨a,b⟩
    cases b <;> simp

/-- Labels for all internal variables. Two endpoint arrays and the switches for the
outer columns are local to a node. The remaining variables belong to the two child networks. -/
def RouteAux (B : Type) : ℕ → Type
  | 0 => Empty
  | h+1 => (Bool × Wire h) ⊕ ((Bool × (Wire (h+1) × B)) ⊕ (Bool × RouteAux B h))

inductive RouteVar (h : ℕ) (B : Type) where
  | input (wire : Wire h) (bit : B)
  | output (wire : Wire h) (bit : B)
  | aux (name : RouteAux B h)

def RouteVar.control {h : ℕ} {B : Type} (side : Bool) (wire : Wire h) : RouteVar (h+1) B :=
  .aux (.inl (side,wire))

def RouteVar.internal {h : ℕ} {B : Type} (side : Bool) (wire : Wire (h+1)) (bit : B) :
    RouteVar (h+1) B := .aux (.inr (.inl (side,wire,bit)))

def RouteVar.embed {h : ℕ} {B : Type} (channel : Bool) : RouteVar h B → RouteVar (h+1) B
  | .input wire bit => .internal false (wire,channel) bit
  | .output wire bit => .internal true (wire,channel) bit
  | .aux name => .aux (.inr (.inr (channel,name)))

/-- Copy and conditional move are the only elementary gates needed for routing. -/
inductive RouteGate (V : Type) where
  | copy (out src : V)
  | mux (out selector crossed straight : V)

def RouteGate.rename {V W : Type} (f : V → W) : RouteGate V → RouteGate W
  | .copy out src => .copy (f out) (f src)
  | .mux out s yes no => .mux (f out) (f s) (f yes) (f no)

def RouteGate.Valid {V : Type} (val : V → Bool) : RouteGate V → Prop
  | .copy out src => val out = val src
  | .mux out s yes no => val out = (if val s then val yes else val no)

theorem RouteGate.valid_rename {V W : Type} (f : V → W) (val : W → Bool) (g : RouteGate V) :
    (g.rename f).Valid val ↔ g.Valid (val ∘ f) := by cases g <;> rfl

private def column {h : ℕ} {B : Type} (bits : List B) (exit : Bool) :
    List (RouteGate (RouteVar (h+1) B)) :=
  (wires h).flatMap fun a =>
    [false,true].flatMap fun b =>
      bits.map fun j =>
        (if exit then
          .mux (.output (a,b) j) (.control true a) (.internal true (a,!b) j) (.internal true (a,b) j)
        else .mux (.internal false (a,b) j) (.control false a) (.input (a,!b) j) (.input (a,b) j))

/-- Explicit replicated gate list with a constant number of gates per bit at each level. -/
def routeGates {B : Type} (bits : List B) :
    (h : ℕ) → List (RouteGate (RouteVar h B))
  | 0 => bits.map fun j => .copy (.output () j) (.input () j)
  | h+1 => column bits false ++
    (routeGates bits h).map (RouteGate.rename (RouteVar.embed false)) ++
    (routeGates bits h).map (RouteGate.rename (RouteVar.embed true)) ++ column bits true

private theorem column_length {h : ℕ} {B : Type} (bits : List B) (side : Bool) :
    (column (h:=h) bits side).length = 2^(h+1)*bits.length := by
  unfold column
  rw [List.length_flatMap]
  simp only [List.length_map, List.length_flatMap, List.map_cons, List.map_nil, List.sum_cons,
    List.sum_nil, Nat.add_zero]
  change ((wires h).map (Function.const _ (bits.length+bits.length))).sum = _
  rw [List.map_const,List.sum_replicate,wires_length,pow_succ]
  ring

theorem routeGates_length {B : Type} (bits : List B) (h : ℕ) :
    (routeGates bits h).length = (2*h+1)*2^h*bits.length := by
  induction h with
  | zero => simp [routeGates]
  | succ h ih =>
    simp only [routeGates,List.length_append,List.length_map,column_length,ih,pow_succ]
    ring

private theorem match_column {h : ℕ} {B : Type} {bits : List B}
    (v : RouteVar (h+1) B → Bool) (side : Bool)
    (hv : ∀ g ∈ column bits side, g.Valid v)
    (a : Wire h) (b : Bool) {j : B} (hj : j ∈ bits) :
    (if side then v (.output (a,b) j) else v (.internal false (a,b) j)) =
      (if v (.control side a) then
        if side then v (.internal true (a,!b) j) else v (.input (a,!b) j)
       else if side then v (.internal true (a,b) j) else v (.input (a,b) j)) := by
  have he : (if side then
        RouteGate.mux (.output (a,b) j) (.control true a) (.internal true (a,!b) j) (.internal true (a,b) j)
      else .mux (.internal false (a,b) j) (.control false a) (.input (a,!b) j) (.input (a,b) j))
      ∈ column bits side := by
    unfold column
    apply List.mem_flatMap.mpr
    refine ⟨a,wires_mem h a,?_⟩
    apply List.mem_flatMap.mpr
    exact ⟨b,by cases b <;> simp,List.mem_map.mpr ⟨j,hj,rfl⟩⟩
  have hh := hv _ he
  cases side <;> exact hh

/-- Every satisfying assignment to the routing gates realizes a permutation on records. -/
theorem routeGates_sound {B : Type} {bits : List B} (h : ℕ)
    (v : RouteVar h B → Bool) (hG : ∀ g ∈ routeGates bits h, g.Valid v) :
    ∃ setting : Setting h, ∀ x j, j ∈ bits →
      v (.output (routing h setting x) j) = v (.input x j) := by
  induction h with
  | zero =>
    refine ⟨(),?_⟩
    intro x j hj
    cases x
    exact hG _ (List.mem_map.mpr ⟨j,hj,rfl⟩)
  | succ h ih =>
    let entry (i : Wire h) := v (.control false i)
    let exit (i : Wire h) := v (.control true i)
    let child (b : Bool) (x : RouteVar h B) := v (RouteVar.embed b x)
    have left (g) (hg : g ∈ column bits false) : g.Valid v :=
      hG g (by simp [routeGates,hg])
    have right (g) (hg : g ∈ column bits true) : g.Valid v :=
      hG g (by simp [routeGates,hg])
    have hc (b : Bool) : ∀ g ∈ routeGates bits h, g.Valid (child b) := by
      intro g hg
      apply (g.valid_rename (RouteVar.embed b) v).mp
      have hm : g.rename (RouteVar.embed b) ∈ (routeGates bits h).map
          (RouteGate.rename (RouteVar.embed b)) := List.mem_map.mpr ⟨g,hg,rfl⟩
      cases b <;> exact hG _ (by simp [routeGates,hm])
    choose mid hm using fun b => ih (child b) (hc b)
    refine ⟨(entry,mid,exit),?_⟩
    intro x j hj
    let q : Wire h × Bool := x
    let z := pairSwitch entry q
    let a := routing h (mid z.2) z.1
    let y := pairSwitch exit (a,z.2)
    have he : routing (h+1) (entry,mid,exit) x = y := routing_succ entry mid exit q
    rw [he]
    have hin : v (.internal false z j) = v (.input q j) := by
      rcases q with ⟨b,u⟩
      have hh := match_column v false left b (if entry b then !u else u) hj
      change v (.internal false (b,if entry b then !u else u) j) =
        (if entry b then v (.input (b,!(if entry b then !u else u)) j)
          else v (.input (b,if entry b then !u else u) j)) at hh
      dsimp only [z,pairSwitch,Equiv.coe_fn_mk]
      by_cases he : entry b <;> simpa [he] using hh
    have hout : v (.output y j) = v (.internal true (a,z.2) j) := by
      have hh := match_column v true right a (if exit a then !z.2 else z.2) hj
      change v (.output (a,if exit a then !z.2 else z.2) j) =
        (if exit a then v (.internal true (a,!(if exit a then !z.2 else z.2)) j)
          else v (.internal true (a,if exit a then !z.2 else z.2) j)) at hh
      dsimp only [y,pairSwitch,Equiv.coe_fn_mk]
      by_cases he : exit a <;> simpa [he] using hh
    exact hout.trans ((hm z.2 z.1 j hj).trans hin)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

private theorem pairSwitch_involutive {A : Type} (c : A → Bool) (p : A × Bool) :
    pairSwitch c (pairSwitch c p) = p := (pairSwitch c).symm_apply_apply p

/-- All routing permutations can be realized with arbitrarily prescribed input records. -/
theorem routeGates_complete {B : Type} (bits : List B) (h : ℕ) (s : Setting h)
    (input : Wire h → B → Bool) :
    ∃ v : RouteVar h B → Bool, (∀ g ∈ routeGates bits h, g.Valid v) ∧
      (∀ x j, v (.input x j) = input x j) ∧
      ∀ x j, j ∈ bits → v (.output (routing h s x) j) = input x j := by
  induction h with
  | zero =>
    let v : RouteVar 0 B → Bool
      | .input a b | .output a b => input a b
      | .aux e => Empty.elim e
    refine ⟨v,?_,fun _ _ => rfl,fun _ _ _ => rfl⟩
    intro g hg
    obtain ⟨j,_,rfl⟩ := List.mem_map.mp hg
    rfl
  | succ h ih =>
    let ss : (Wire h → Bool) × (Bool → Setting h) × (Wire h → Bool) := s
    let entry := ss.1
    let mid := ss.2.1
    let exit := ss.2.2
    let childInput (b : Bool) (a : Wire h) (j : B) := input (pairSwitch entry (a,b)) j
    choose cv hcv hcin hcout using fun b => ih (mid b) (childInput b)
    let v : RouteVar (h+1) B → Bool
      | .input x j => input x j
      | .output x j =>
        let y := pairSwitch exit x
        cv y.2 (.output y.1 j)
      | .aux (.inl (b,x)) => if b then exit x else entry x
      | .aux (.inr (.inl (b,x,j))) =>
        if b then cv x.2 (.output x.1 j) else cv x.2 (.input x.1 j)
      | .aux (.inr (.inr (b,x))) => cv b (.aux x)
    have hv (b : Bool) : v ∘ RouteVar.embed b = cv b := by
      funext x
      cases x <;> rfl
    have hleft : ∀ g ∈ column bits false, g.Valid v := by
      intro g hg
      obtain ⟨a,ha,h⟩ := List.mem_flatMap.mp hg
      obtain ⟨b,hb,hh⟩ := List.mem_flatMap.mp h
      obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hh
      change cv b (.input a j) = (if entry a then input (a,!b) j else input (a,b) j)
      rw [hcin b a j]
      unfold childInput
      by_cases he : entry a <;> simp [pairSwitch,he]
    have hright : ∀ g ∈ column bits true, g.Valid v := by
      intro g hg
      obtain ⟨a,ha,h⟩ := List.mem_flatMap.mp hg
      obtain ⟨b,hb,hh⟩ := List.mem_flatMap.mp h
      obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hh
      change cv (pairSwitch exit (a,b)).2 (.output (pairSwitch exit (a,b)).1 j) =
        (if exit a then cv (!b) (.output a j) else cv b (.output a j))
      by_cases he : exit a <;> simp [pairSwitch,he]
    refine ⟨v,?_,fun _ _ => rfl,?_⟩
    · intro g hg
      simp only [routeGates,List.mem_append] at hg
      rcases hg with ((hg|hg)|hg)|hg
      · exact hleft _ hg
      · obtain ⟨g0,hg0,rfl⟩ := List.mem_map.mp hg
        exact (g0.valid_rename _ _).mpr (by rw [hv]; exact hcv false g0 hg0)
      · obtain ⟨g0,hg0,rfl⟩ := List.mem_map.mp hg
        exact (g0.valid_rename _ _).mpr (by rw [hv]; exact hcv true g0 hg0)
      · exact hright _ hg
    · intro x j hj
      let q : Wire h × Bool := x
      let z := pairSwitch entry q
      have he : routing (h+1) s x = pairSwitch exit (routing h (mid z.2) z.1,z.2) := by
        have hx : (entry,mid,exit) = s := by cases ss; rfl
        exact hx ▸ routing_succ entry mid exit q
      change cv (pairSwitch exit (routing (h+1) s x)).2
        (.output (pairSwitch exit (routing (h+1) s x)).1 j) = input q j
      rw [he,pairSwitch_involutive]
      have hh := hcout z.2 z.1 j hj
      change _ = input (pairSwitch entry z) j at hh
      rw [show pairSwitch entry z = q from pairSwitch_involutive entry q] at hh
      exact hh

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- Translate symbolic routing constraints into the mission's local gate language. -/
def RouteGate.named {V : Type} (name : V → ℕ) : RouteGate V → Gate
  | .copy out src => .copy (name out) (name src)
  | .mux out sel crossed straight => .mux (name out) (name sel) (name crossed) (name straight)

theorem RouteGate.named_correct {V : Type} (name : V → ℕ) (α : Assignment)
    (g : RouteGate V) : (g.named name).Holds α ↔ g.Valid (α ∘ name) := by cases g <;> rfl

def routeCNF (height width : ℕ) (name : RouteVar height (Fin width) → ℕ) : Formula :=
  RobsonCNF.compile ((routeGates (List.finRange width) height).map (RouteGate.named name))

theorem routeCNF_size (height width : ℕ) (name : RouteVar height (Fin width) → ℕ) :
    (routeCNF height width name).length ≤ 4*((2*height+1)*2^height*width) := by
  unfold routeCNF
  apply (length_compile _).trans
  rw [List.length_map, routeGates_length]
  simp

/-- The endpoint assignments extend to a satisfying assignment of the network if and
only if the output records are a permutation of the input records. -/
theorem routeCNF_spec (height width : ℕ) (name : RouteVar height (Fin width) → ℕ)
    (hname : Function.Injective name) (input output : Wire height → Fin width → Bool) :
    (∃ α : Assignment, Satisfies α (routeCNF height width name) ∧
        (∀ i j, α (name (.input i j)) = input i j) ∧
        ∀ i j, α (name (.output i j)) = output i j) ↔
      ∃ σ : Wire height ≃ Wire height, ∀ i j, output (σ i) j = input i j := by
  constructor
  · rintro ⟨α,hα,hin,hout⟩
    have hg : ∀ g ∈ routeGates (List.finRange width) height, g.Valid (α ∘ name) := by
      intro g hm
      have h := (compile_correct _ _).mp hα (g.named name) (List.mem_map.mpr ⟨g,hm,rfl⟩)
      exact (g.named_correct name α).mp h
    obtain ⟨s,hs⟩ := routeGates_sound height (α ∘ name) hg
    refine ⟨routing height s,fun i j => ?_⟩
    exact (hout _ _).symm.trans ((hs _ _ (by simp)).trans (hin _ _))
  · rintro ⟨σ,hσ⟩
    obtain ⟨s,hs⟩ := routing_universal height σ
    obtain ⟨v,hg,hI,hO⟩ := routeGates_complete (List.finRange width) height s input
    classical
    let α := Function.extend name v (fun _ => false)
    have ha : α ∘ name = v := Function.extend_comp hname _ _
    refine ⟨α,?_,?_,?_⟩
    · apply (compile_correct _ _).mpr
      intro g hm
      obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hm
      apply (r.named_correct name α).mpr
      rw [ha]
      exact hg r hr
    · intro i j
      exact (congrFun ha (.input i j)).trans (hI i j)
    · intro i j
      have hh := hO (σ.symm i) j (by simp)
      rw [hs,σ.apply_symm_apply] at hh
      have ho := hσ (σ.symm i) j
      rw [σ.apply_symm_apply] at ho
      exact (congrFun ha (.output i j)).trans (hh.trans ho.symm)

/-- Wires have an explicit position label. -/
def wireLabel : (h : ℕ) → Wire h ≃ Fin (2^h)
  | 0 => {toFun := fun _ => 0, invFun := fun _ => (),
          left_inv := by intro x; cases x; rfl, right_inv := by intro i; apply Fin.ext; omega}
  | h+1 => ((wireLabel h).prodCongr finTwoEquiv.symm).trans
      (finProdFinEquiv.trans (finCongr (by rw [pow_succ])))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

def auxCount (w : ℕ) : ℕ → ℕ
  | 0 => 0
  | h+1 => 2 * 2^h + (2 * (2^(h+1)*w) + 2*auxCount w h)

def auxLabel (w : ℕ) : (h : ℕ) → RouteAux (Fin w) h ≃ Fin (auxCount w h)
  | 0 => {toFun := Empty.elim, invFun := Fin.elim0, left_inv := fun x => Empty.elim x, right_inv := fun x => Fin.elim0 x}
  | h+1 =>
    (Equiv.sumCongr
      ((finTwoEquiv.symm.prodCongr (wireLabel h)).trans finProdFinEquiv)
      ((Equiv.sumCongr
        ((finTwoEquiv.symm.prodCongr (((wireLabel (h+1)).prodCongr (Equiv.refl _)).trans
          finProdFinEquiv)).trans finProdFinEquiv)
        ((finTwoEquiv.symm.prodCongr (auxLabel w h)).trans finProdFinEquiv)).trans
        finSumFinEquiv)).trans finSumFinEquiv

/-- Computable numeric labels with an input block, an output block, and distinct
internal variables. -/
def routeLabel (h w : ℕ) : RouteVar h (Fin w) ≃
    Fin (2^h*w+(2^h*w+auxCount w h)) := by
  let split : RouteVar h (Fin w) ≃
      ((Wire h × Fin w) ⊕ ((Wire h × Fin w) ⊕ RouteAux (Fin w) h)) :=
    { toFun := fun v => match v with
        | .input i j => .inl (i,j)
        | .output i j => .inr (.inl (i,j))
        | .aux v => .inr (.inr v)
      invFun := fun v => match v with
        | .inl (i,j) => .input i j
        | .inr (.inl (i,j)) => .output i j
        | .inr (.inr v) => .aux v
      left_inv := by intro v; cases v <;> rfl
      right_inv := by rintro (⟨i,j⟩|⟨i,j⟩|v) <;> rfl }
  let endpoint := ((wireLabel h).prodCongr (Equiv.refl (Fin w))).trans finProdFinEquiv
  exact split.trans ((Equiv.sumCongr endpoint
    ((Equiv.sumCongr endpoint (auxLabel w h)).trans finSumFinEquiv)).trans finSumFinEquiv)

theorem auxCount_exact (h w : ℕ) : auxCount w h = h*2^h*(1+2*w) := by
  induction h with
  | zero => simp [auxCount]
  | succ h ih => rw [auxCount, ih, pow_succ]; ring

def concreteRouteCNF (base h w : ℕ) : CookLevin.Formula :=
  routeCNF h w (fun i => base+(routeLabel h w i).val)

theorem concreteRouteCNF_spec (base h w : ℕ) (input output : Wire h → Fin w → Bool) :
    (∃ α : CookLevin.Assignment, CookLevin.Satisfies α (concreteRouteCNF base h w) ∧
        (∀ i j, α (base+(routeLabel h w (.input i j)).val) = input i j) ∧
        ∀ i j, α (base+(routeLabel h w (.output i j)).val) = output i j) ↔
      ∃ σ : Wire h ≃ Wire h, ∀ i j, output (σ i) j = input i j :=
  routeCNF_spec h w _ (fun _ _ he =>
    (routeLabel h w).injective (Fin.ext (Nat.add_left_cancel he))) input output

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

/-- Ceiling division gives the number of consecutive groups of at most 2^b records. -/
def groupCount (b n : ℕ) : ℕ := (n+2^b-1)/2^b

/-- Two boundary snapshots of 2^b records each and 2^b event slots fit in 2^(b+2)
wires. A single group has no internal boundaries, so it only pads its event slots. -/
def groupHeight (b n : ℕ) : ℕ := if n ≤ 2^b then slotLevel n else b+2

theorem groupHeight_le (b n : ℕ) : groupHeight b n ≤ b+2 := by
  unfold groupHeight
  split
  · rename_i h
    have hs : n-1 < 2^b := by
      have hp : 0 < (2:ℕ)^b := Nat.pow_pos (by decide)
      omega
    exact (Nat.size_le.mpr hs).trans (by omega)
  · exact le_rfl

theorem group_capacity (b n : ℕ) (hN : 0 < n) :
    n ≤ groupCount b n * 2^groupHeight b n := by
  let B := (2:ℕ)^b
  have hB : 0 < B := Nat.pow_pos (by decide)
  have hAlign : n ≤ groupCount b n * B := alignedStart_lower hB
  by_cases hn : n ≤ B
  · have hone : groupCount b n = 1 := by
      apply Nat.div_eq_of_lt_le
      · simp [groupCount,B]
        omega
      · simp [groupCount,B,two_mul] at *
        omega
    simp only [groupHeight,show n ≤ 2^b from hn,if_true,hone,one_mul]
    exact le_slotWidth n
  · have hcap : B ≤ 2^groupHeight b n := by
      rw [groupHeight,if_neg hn]
      exact Nat.pow_le_pow_right (by decide) (by omega)
    exact hAlign.trans (Nat.mul_le_mul_left _ hcap)

theorem grouped_wire_budget (b n : ℕ) (hN : 0 < n) :
    groupCount b n * 2^groupHeight b n ≤ 8*n := by
  let B := (2:ℕ)^b
  have hB : 0 < B := Nat.pow_pos (by decide)
  have hAlign : groupCount b n * B < n+B := alignedStart_upper hB
  by_cases hn : n ≤ B
  · have hONE : groupCount b n = 1 := by
      change (n+B-1)/B = 1
      apply Nat.div_eq_of_lt_le <;> omega
    simp only [groupHeight,show n ≤ 2^b from hn,if_true,hONE,one_mul]
    exact (slotWidth_le_double hN).trans (by omega)
  · have hpow : (2:ℕ)^groupHeight b n = 4*B := by
      rw [groupHeight,if_neg hn,pow_add]
      unfold B
      ring
    rw [hpow]
    have hEq : groupCount b n*(4*B) = 4*(groupCount b n*B) := by ring
    rw [hEq]
    omega

/-- A bound for one width tier. Timestamps are local to each group, so each record
spends O(b) bits on its address, its value, and that timestamp. -/
theorem grouped_routing_budget (b n word : ℕ) (hN : 0 < n) :
    groupCount b n * (2*groupHeight b n+1) * 2^groupHeight b n * word ≤
      8*n*(2*b+5)*word := by
  have hh := groupHeight_le b n
  have hg := grouped_wire_budget b n hN
  have hh' : 2*groupHeight b n+1 ≤ 2*b+5 := by omega
  calc
    _ = (groupCount b n * 2^groupHeight b n) * (2*groupHeight b n+1) * word := by ring
    _ ≤ _ := Nat.mul_le_mul_right _ (Nat.mul_le_mul hg hh')

/-- Sum of the widths of every tier through level h. -/
theorem tierWidths_sum (h : ℕ) :
    ∑ j ∈ Finset.range (h+1), (2:ℕ)^j = 2^(h+1)-1 := by
  induction h with
  | zero => simp
  | succ h ih =>
    rw [Finset.sum_range_succ,ih,pow_succ (2:ℕ) (h+1)]
    have hP : 0 < (2:ℕ)^(h+1) := Nat.pow_pos (by decide)
    omega

/-- Summing a per-tier cost linear in the dyadic width costs only twice the largest
width. In particular bounded-word routing does not spend a second logarithmic
factor on all the tiers simultaneously. -/
theorem sum_tier_costs (T C h : ℕ) (cost : ℕ → ℕ)
    (hc : ∀ j < h+1, cost j ≤ C*T*2^j) :
    (∑ j ∈ Finset.range (h+1),cost j) ≤ 2*C*T*2^h := by
  calc
    _ ≤ ∑ j ∈ Finset.range (h+1), C*T*2^j :=
      Finset.sum_le_sum fun j hj => hc j (Finset.mem_range.mp hj)
    _ = C*T*(2^(h+1)-1) := by rw [← Finset.mul_sum,tierWidths_sum]
    _ ≤ _ := by
      rw [pow_succ]
      have hEq : C*T*(2^h*2) = 2*C*T*2^h := by ring
      exact (Nat.mul_le_mul_left _ (Nat.sub_le _ _)).trans_eq hEq

end CNFEncComplexity.Robson

/- router numeric interface -/

namespace CNFEncComplexity.Robson

abbrev routeWireList (h : ℕ) : List (Wire h) := wires h

abbrev routeSide {h : ℕ} {B : Type} (bits : List B) (b : Bool) :
    List (RouteGate (RouteVar (h+1) B)) := column bits b

theorem routeGates_succ_eq {B : Type} (bits : List B) (h : ℕ) :
    routeGates bits (h+1) = routeSide bits false ++
      (routeGates bits h).map (RouteGate.rename (RouteVar.embed false)) ++
      (routeGates bits h).map (RouteGate.rename (RouteVar.embed true)) ++ routeSide bits true := rfl

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