Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform generation of the RAM trie dictionary

Definition
CNFEncComplexity_RobsonMemoryTrieDictionary

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

complexity-theorysatisfiability

Polynomial-time generation of the routing, pooled trie, word-label dictionary, and normalization gate lists.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieDictionarySoundness
import Definitions.Def_CNFEncComplexity_RobsonMemoryParameters

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonTrieDictNative -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section
variable {A : Type} {e : A ↪ List Bool}

private theorem posNegLit_poly (positive : Bool) {name : A → ℕ}
    (h : ComputableTidilyInPolyTime name e encUnary) :
    ComputableTidilyInPolyTime (fun x => literalN (if positive then .Pos (name x) else .Neg (name x)))
      e encUnary := by
  cases positive
  · exact unary_mul.comp ((const 2).prod h)
  · exact unary_add.comp ((unary_mul.comp ((const 2).prod h)).prod (const 1))

private theorem pairAssert₂ (s₁ s₂ : Bool) {x y : A → ℕ}
    (hx : ComputableTidilyInPolyTime x e encUnary) (hy : ComputableTidilyInPolyTime y e encUnary) :
    ComputableTidilyInPolyTime (fun p => .assert [if s₁ then .Pos (x p) else .Neg (x p),
      if s₂ then .Pos (y p) else .Neg (y p)] : A → Gate) e gateEnc := by
  exact gate_assert (cons' (posNegLit_poly s₁ hx) (cons' (posNegLit_poly s₂ hy) (const [])))

private theorem pairAssert₃ (s₁ s₂ s₃ : Bool) {x y z : A → ℕ}
    (hx : ComputableTidilyInPolyTime x e encUnary) (hy : ComputableTidilyInPolyTime y e encUnary)
    (hz : ComputableTidilyInPolyTime z e encUnary) :
    ComputableTidilyInPolyTime (fun p => .assert [if s₁ then .Pos (x p) else .Neg (x p),
      if s₂ then .Pos (y p) else .Neg (y p),if s₃ then .Pos (z p) else .Neg (z p)] : A → Gate) e gateEnc :=
  gate_assert (cons' (posNegLit_poly s₁ hx) (cons' (posNegLit_poly s₂ hy)
    (cons' (posNegLit_poly s₃ hz) (const []))))

private theorem trieSortWidth_poly (c : Bool) {B : A → ℕ}
    (hB : ComputableTidilyInPolyTime B e encUnary) :
    ComputableTidilyInPolyTime (fun x => trieSortWidth (B x) c) e encUnary := by
  cases c
  · exact unary_add.comp (hB.prod hB)
  · exact hB

private theorem trieSortWire_poly (c : Bool) {B : A → ℕ} {src : A → ℕ → ℕ}
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hSrc : ComputableTidilyInPolyTime (fun p : A×ℕ => src p.1 p.2) (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime
      (fun p : A×ℕ => trieSortWire (B p.1) c (trieRowFromNat (B p.1) (src p.1)) p.2)
      (encPair e encUnary) encUnary := by
  let X := fst e encUnary
  let I := snd e encUnary
  have hBB := hB.comp X
  have hsP : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+(p.2-B p.1))
      (encPair e encUnary) encUnary := by fun_prop
  have hsD : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+B p.1+p.2)
      (encPair e encUnary) encUnary := by fun_prop
  have hsC : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+2*B p.1+p.2)
      (encPair e encUnary) encUnary := by fun_prop
  cases c
  · have hp := hSrc.comp (X.prod hsP)
    have hd := hSrc.comp (X.prod hsD)
    have ht := (unary_lt' I hBB).ite' hd hp
    simpa only [trieSortWire,trieRowFromNat,joinKey,Function.comp_def,decide_eq_true_eq,
      Bool.false_eq_true,if_false] using ht
  · exact hSrc.comp (X.prod hsC)

private theorem trieRowPair_poly (c : Bool) {base B : A → ℕ} {l r : A → ℕ → ℕ}
    (hq : ComputableTidilyInPolyTime base e encUnary)
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hL : ComputableTidilyInPolyTime (fun p : A×ℕ => l p.1 p.2) (encPair e encUnary) encUnary)
    (hR : ComputableTidilyInPolyTime (fun p : A×ℕ => r p.1 p.2) (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => trieRowPair (base a) (B a) c
      (trieRowFromNat (B a) (l a)) (trieRowFromNat (B a) (r a))) e (encList gateEnc) := by
  let n := fun x => trieSortWidth (B x) c
  let m := fun x => trieSortWidth (B x) (!c)
  let next := fun x => base x+4*(n x+1)
  let PL := fun x => trieSortWire (B x) c (trieRowFromNat (B x) (l x))
  let PR := fun x => trieSortWire (B x) c (trieRowFromNat (B x) (r x))
  let QL := fun x => trieSortWire (B x) (!c) (trieRowFromNat (B x) (l x))
  let QR := fun x => trieSortWire (B x) (!c) (trieRowFromNat (B x) (r x))
  have hn : ComputableTidilyInPolyTime n e encUnary := trieSortWidth_poly c hB
  have hm : ComputableTidilyInPolyTime m e encUnary := trieSortWidth_poly (!c) hB
  have hnxt : ComputableTidilyInPolyTime next e encUnary := by unfold next; fun_prop
  have hP := compareCircuit_polytime (lhs := PL) (rhs := PR) hq hn
    (trieSortWire_poly c hB hL) (trieSortWire_poly c hB hR)
  have hQ := compareCircuit_polytime (lhs := QL) (rhs := QR) hnxt hm
    (trieSortWire_poly (!c) hB hL) (trieSortWire_poly (!c) hB hR)
  have hl := hL.comp ((id' (encIn := e)).prod (const 0))
  have hr := hR.comp ((id' (encIn := e)).prod (const 0))
  have ht : ComputableTidilyInPolyTime (fun x => ltWire (base x) (n x)) e encUnary := by
    unfold ltWire; fun_prop
  have he : ComputableTidilyInPolyTime (fun x => eqWire (base x) (n x)) e encUnary := by
    unfold eqWire; fun_prop
  have he₂ : ComputableTidilyInPolyTime (fun x => eqWire (next x) (m x)) e encUnary := by
    unfold eqWire; fun_prop
  exact listAppend' (listAppend' hP hQ)
    (cons' (pairAssert₂ true false hl hr) (cons' (pairAssert₃ false true true hr ht he)
      (cons' (pairAssert₃ false false true hr he he₂) (const []))))

end
end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

private theorem trieSortCheckOfFn (base B : ℕ) (c : Bool) (n : ℕ) (row : ℕ → TrieRowPort) :
    trieSortCheckGates B c base (List.ofFn fun i : Fin n => row i.val) =
      (List.range (n-1)).flatMap fun i => trieRowPair (base+i*triePairSpan B) B c (row i) (row (i+1)) := by
  induction n generalizing base row with
  | zero => simp [trieSortCheckGates]
  | succ m ih =>
    cases m with
    | zero => simp [List.ofFn_succ,trieSortCheckGates]
    | succ k =>
      rw [List.ofFn_succ]
      have hh : List.ofFn (fun i : Fin (k+1) => row (i.val+1)) =
          row 1 :: List.ofFn (fun i : Fin k => row (i.val+1+1)) := by
        rw [List.ofFn_succ]
        rfl
      change trieSortCheckGates B c base (row 0::List.ofFn (fun i : Fin (k+1) => row (i.val+1))) = _
      rw [hh,trieSortCheckGates]
      have ih' := ih (base+triePairSpan B) (fun j => row (j+1))
      simp only [List.ofFn_succ,Fin.val_zero,Fin.val_succ,Nat.zero_add] at ih'
      rw [ih']
      simp only [Nat.add_sub_cancel, List.range_succ_eq_map,List.flatMap_cons,List.flatMap_map,
        Function.comp_def,Nat.zero_mul,Nat.add_zero]
      congr 1
      apply List.flatMap_congr
      intro j hj
      have eq : base+triePairSpan B+j*triePairSpan B = base+(j+1)*triePairSpan B := by ring
      rw [eq]

section
variable {A : Type} {e : A ↪ List Bool}

private theorem trieRouteEnd_poly {base B h : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hH : ComputableTidilyInPolyTime h e encUnary)
    (hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary) :
    ComputableTidilyInPolyTime (fun x => trieRouteEnd (base x) (B x) (h x)) e encUnary := by
  unfold trieRouteEnd trieRowWidth
  simp only [auxCount_exact]
  fun_prop

theorem trieSortPassEnd_poly {base B h : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hH : ComputableTidilyInPolyTime h e encUnary)
    (hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary) :
    ComputableTidilyInPolyTime (fun x => trieSortPassEnd (base x) (B x) (h x)) e encUnary := by
  have hE := trieRouteEnd_poly hBase hB hH hN
  unfold trieSortPassEnd triePairSpan
  fun_prop

set_option maxHeartbeats 1000000 in
theorem trieSortPass_polytime (c : Bool) {base B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hH : ComputableTidilyInPolyTime h e encUnary)
    (hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
    (hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => trieSortPass (base x) (B x) (h x) c (src x))
      e (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  let X := fst e encUnary
  let Q := snd e encUnary
  let Y := fst e₁ encUnary
  let I := snd e₁ encUnary
  let D := fun x => trieRowWidth (B x)
  have hD : ComputableTidilyInPolyTime D e encUnary := by unfold D trieRowWidth; fun_prop
  have hX2 := X.comp Y
  have hQ2 := Q.comp Y
  have hStart := unary_add.comp (((hBase.comp hX2)).prod
    (unary_mul.comp (hQ2.prod (hD.comp hX2))))
  have hIn : ComputableTidilyInPolyTime
      (fun p : (A×ℕ)×ℕ => trieRouteIn (base p.1.1) (B p.1.1) p.1.2 p.2) e₂ encUnary :=
    unary_add.comp (hStart.prod I)
  have hLines := mapWithInput (f := fun (p : A×ℕ) i =>
      Gate.copy (trieRouteIn (base p.1) (B p.1) p.2 i) (src p.1 p.2 i))
    (range.comp (hD.comp X)) (gate_copy hIn hSrc)
  have hAttach := flatMapWithInput (f := fun x q => wordCopy (D x) (trieRouteIn (base x) (B x) q) (src x q))
    (range.comp hN) hLines
  have hRoute' := boundedRouteGates_poly.comp (hD.prod (hH.prod (hBase.prod hN)))
  have hRoute : ComputableTidilyInPolyTime (fun x => routeNamedGates (trieRouteName (base x) (B x) (h x)))
      e (encList gateEnc) := by
    convert hRoute' using 1
    funext x
    change routeNamedGates (fun v => base x+(routeLabel (h x) (D x) v).val) = _
    exact (boundedRouteGates_eq (D x) (h x) (base x) (2^h x) le_rfl).symm
  have hEnd := trieRouteEnd_poly hBase hB hH hN
  have hSpan : ComputableTidilyInPolyTime (fun x => triePairSpan (B x)) e encUnary := by unfold triePairSpan; fun_prop
  have hScratch : ComputableTidilyInPolyTime
      (fun p : A×ℕ => trieRouteEnd (base p.1) (B p.1) (h p.1)+p.2*triePairSpan (B p.1)) e₁ encUnary :=
    unary_add.comp ((hEnd.comp X).prod (unary_mul.comp (Q.prod (hSpan.comp X))))
  have hOutBase := unary_add.comp ((hBase.comp hX2).prod ((unary_mul.comp (hN.prod hD)).comp hX2))
  have hL : ComputableTidilyInPolyTime
      (fun p : (A×ℕ)×ℕ => trieRouteOut (base p.1.1) (B p.1.1) (h p.1.1) p.1.2 p.2) e₂ encUnary :=
    unary_add.comp ((unary_add.comp (hOutBase.prod
      (unary_mul.comp (hQ2.prod (hD.comp hX2))))).prod I)
  have hQsucc := unary_add.comp (hQ2.prod (const 1))
  have hR : ComputableTidilyInPolyTime
      (fun p : (A×ℕ)×ℕ => trieRouteOut (base p.1.1) (B p.1.1) (h p.1.1) (p.1.2+1) p.2) e₂ encUnary :=
    unary_add.comp ((unary_add.comp (hOutBase.prod
      (unary_mul.comp (hQsucc.prod (hD.comp hX2))))).prod I)
  have hPairs := trieRowPair_poly c
    (l := fun p i => trieRouteOut (base p.1) (B p.1) (h p.1) p.2 i)
    (r := fun p i => trieRouteOut (base p.1) (B p.1) (h p.1) (p.2+1) i)
    hScratch (hB.comp X) hL hR
  have hN1 := unary_sub.comp (hN.prod (const 1))
  have hCheck := flatMapWithInput (f := fun x i => trieRowPair
      (trieRouteEnd (base x) (B x) (h x)+i*triePairSpan (B x)) (B x) c
      (trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) i))
      (trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) (i+1))))
    (range.comp hN1) hPairs
  have hAll := listAppend' (listAppend' hAttach hRoute) hCheck
  convert hAll using 1
  funext x
  simp only [trieSortPass,trieRouteCopy,trieRouteRows,Function.comp_def,D]
  rw [trieSortCheckOfFn (trieRouteEnd (base x) (B x) (h x)) (B x) c (2^h x)
    (fun q => trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) q))]

set_option maxHeartbeats 1000000 in
private theorem trieNonzeroList_poly {B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
    (hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => trieNonzeroList (B x) (h x) (src x))
      e (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  let X := fst e encUnary
  let Y := fst e₁ encUnary
  have hOn := hSrc.comp ((id' (encIn := e₁)).prod (const 0))
  have hi : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => 1+2*B p.1.1+p.2) e₂ encUnary := by
    unfold e₂ e₁
    fun_prop
  have hChild := hSrc.comp (Y.prod hi)
  have hNeg := posNegLit_poly false hOn
  have hPos := posNegLit_poly true hChild
  have hBits := mapWithInput
    (f := fun (p : A×ℕ) i => literalN (.Pos (src p.1 p.2 (1+2*B p.1+i))))
    (range.comp (hB.comp X)) hPos
  have hGate := gate_assert (c := fun p : A×ℕ => .Neg (src p.1 p.2 0) ::
    (List.range (B p.1)).map (fun i => .Pos (src p.1 p.2 (1+2*B p.1+i)))) (by
    simpa [clauseN,List.map_map,Function.comp_def] using cons' hNeg hBits)
  have hClause := cons' hGate (const [])
  exact flatMapWithInput (f := fun x q => trieNonzeroGates (B x) (trieRowFromNat (B x) (src x q)))
    (range.comp hN) hClause

theorem trieDictionaryGates_polytime {base B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hB : ComputableTidilyInPolyTime B e encUnary)
    (hH : ComputableTidilyInPolyTime h e encUnary)
    (hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
    (hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => trieDictionaryGates (base x) (B x) (h x) (src x))
      e (encList gateEnc) := by
  have hBase' := trieSortPassEnd_poly hBase hB hH hN
  exact listAppend' (listAppend' (trieNonzeroList_poly (src := src) hB hN hSrc)
    (trieSortPass_polytime (src := src) false hBase hB hH hN hSrc))
    (trieSortPass_polytime (src := src) true hBase' hB hH hN hSrc)

end
end CNFEncComplexity.Robson

/- RobsonTriePoolNative -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section
variable {A : Type} {e : A ↪ List Bool}

theorem triePoolLanes_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary) :
    ComputableTidilyInPolyTime (fun x => triePoolLanes (t x) (b x)) e encUnary :=
  unary_pow2_of_bound (unary_sub.comp ((layoutHeight_poly.comp hT).prod hB))
    (layoutHorizon_poly.comp hT) (fun _ => Nat.pow_le_pow_right (by decide) (Nat.sub_le ..))

theorem triePoolHeight_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary) :
    ComputableTidilyInPolyTime (fun x => triePoolHeight (t x) (b x)) e encUnary :=
  unary_add.comp ((unary_sub.comp ((layoutHeight_poly.comp hT).prod hB)).prod (const 4))

theorem triePoolRows_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary) :
    ComputableTidilyInPolyTime (fun x => 2^triePoolHeight (t x) (b x)) e encUnary := by
  convert unary_mul.comp ((triePoolLanes_poly hT hB).prod (const 16)) using 1
  funext x
  exact pow_add (2:ℕ) _ _

theorem triePoolLevels_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary) :
    ComputableTidilyInPolyTime (fun x => triePoolLevels (t x) (b x)) e encUnary :=
  unary_sub.comp ((unary_add.comp ((layoutHeight_poly.comp hT).prod (const 1))).prod hB)

theorem triePoolCount_poly {t b q : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hQ : ComputableTidilyInPolyTime q e encUnary) :
    ComputableTidilyInPolyTime (fun x => triePoolCount (t x) (b x) (q x)) e encUnary := by
  have hp := unary_div_poly.comp (hQ.prod (triePoolLanes_poly hT hB))
  have ht := (unary_lt' hp (const 9)).ite' (triePoolLevels_poly hT hB) (const 0)
  simpa only [triePoolCount,decide_eq_true_eq,Function.comp_def] using ht

private theorem triePoolPower_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => 2^b x) e encUnary :=
  unary_pow2_of_bound hB (layoutHorizon_poly.comp hT) (fun x => Nat.pow_le_pow_right (by decide) (hBnd x))

theorem triePoolWidth_poly {t b : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolWidth (b x)) e encUnary :=
  unary_mul.comp ((const 3).prod (triePoolPower_poly hT hB hBnd))

theorem triePoolAfter_poly {pool t b : A → ℕ}
    (hP : ComputableTidilyInPolyTime pool e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolAfter (pool x) (t x) (b x)) e encUnary := by
  have hW := triePoolWidth_poly hT hB hBnd
  have hL := triePoolLevels_poly hT hB
  have hN := triePoolRows_poly hT hB
  unfold triePoolAfter triePoolStride
  fun_prop

private def trieCapLevel (t b j : ℕ) : ℕ := min j (layoutHeight t-b)

private theorem trieCapLevel_eq {t b q j : ℕ} (hb : b ≤ layoutHeight t)
    (hj : j < triePoolCount t b q) : trieCapLevel t b j = j := by
  have hN : triePoolCount t b q ≤ triePoolLevels t b := by
    unfold triePoolCount
    split <;> omega
  unfold trieCapLevel triePoolLevels at *
  apply min_eq_left
  omega

set_option maxHeartbeats 2000000 in
private theorem triePoolWordScalars_poly {base n t b q j : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hQ : ComputableTidilyInPolyTime q e encUnary)
    (hJ : ComputableTidilyInPolyTime j e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x))
    (hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
    let src : A → (ℕ×ℕ) × ℕ × ℕ × ℕ := fun x => triePoolSource (t x) (b x) (q x) (j x)
    ∃ hS : ComputableTidilyInPolyTime (fun x => (src x).1.1) e encUnary,
      ∃ hD : ComputableTidilyInPolyTime (fun x => (src x).1.2) e encUnary,
        ∃ hR : ComputableTidilyInPolyTime (fun x => (src x).2.1) e encUnary,
          ∃ hF : ComputableTidilyInPolyTime (fun x => (src x).2.2.1) e encUnary,
            ∃ hI : ComputableTidilyInPolyTime (fun x => (src x).2.2.2) e encUnary,
              ComputableTidilyInPolyTime (fun x => normalizeWordBase (base x) (t x)
                (src x).1 (src x).2.1 (src x).2.2.1) e encUnary := by
  dsimp only
  let N := fun x => triePoolLanes (t x) (b x)
  let K := fun x => (2:ℕ)^j x
  let W := fun x => (2:ℕ)^(b x+j x)
  have hp := triePoolLanes_poly hT hB
  have hH := layoutHeight_poly.comp hT
  have hW' := layoutHorizon_poly.comp hT
  have hK : ComputableTidilyInPolyTime K e encUnary :=
    unary_pow2_of_bound hJ hW' (fun x => Nat.pow_le_pow_right (by decide)
      ((Nat.le_add_left _ _).trans (hJnd x)))
  have hW : ComputableTidilyInPolyTime W e encUnary :=
    unary_pow2_of_bound (unary_add.comp (hB.prod hJ)) hW' (fun x =>
      Nat.pow_le_pow_right (by decide) (hJnd x))
  have hDiv := unary_div_poly.comp (hQ.prod hp)
  have hMod := unary_mod_poly.comp (hQ.prod hp)
  have hR := unary_div_poly.comp (hDiv.prod (const 3))
  have hF := unary_mod_poly.comp (hDiv.prod (const 3))
  have hS := unary_mul.comp ((unary_div_poly.comp (hMod.prod hK)).prod hW)
  have hD := unary_add.comp (hB.prod hJ)
  have hI := unary_mod_poly.comp (hMod.prod hK)
  have hS' : ComputableTidilyInPolyTime (fun x => (triePoolSource (t x) (b x) (q x) (j x)).1.1) e encUnary := by
    apply hS.of_enc_eq
    intro x
    apply congrArg encUnary
    simp only [triePoolSource,chunkLaneSource,Nat.add_sub_cancel_left,Function.comp_def,W,K]
  have hI' : ComputableTidilyInPolyTime (fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.2) e encUnary := by
    apply hI.of_enc_eq
    intro x
    apply congrArg encUnary
    simp only [triePoolSource,chunkLaneSource,Nat.add_sub_cancel_left,Function.comp_def,K]
  refine ⟨hS',hD,hR,hF,hI',?_⟩
  have hStride : ComputableTidilyInPolyTime (fun x => normalizeStride (t x)) e encUnary :=
    unary_add.comp ((unary_mul.comp ((const 6).prod hW')).prod (const 4))
  have hHeight1 := unary_add.comp (hH.prod (const 1))
  have hSlot := unary_add.comp ((unary_mul.comp (hS'.prod hHeight1)).prod hD)
  have hRow := unary_add.comp ((unary_mul.comp (hSlot.prod (const 3))).prod hR)
  have hField := unary_add.comp ((unary_mul.comp (hRow.prod (const 3))).prod hF)
  exact unary_add.comp (hBase.prod (unary_mul.comp (hField.prod hStride)))

private theorem triePoolEnable_poly {base n t b q j : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hQ : ComputableTidilyInPolyTime q e encUnary)
    (hJ : ComputableTidilyInPolyTime j e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x))
    (hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolEnable (base x) (n x) (t x) (b x) (q x) (j x))
      e encUnary := by
  obtain ⟨hs,hd,hr,hf,hi,hL⟩ :=
    triePoolWordScalars_poly hBase hN hT hB hQ hJ hBnd hJnd
  have hW := unary_pow2_of_bound hd (layoutHorizon_poly.comp hT)
    (fun x => Nat.pow_le_pow_right (by decide) (hJnd x))
  exact unary_add.comp ((unary_add.comp ((unary_add.comp (hL.prod hW)).prod (const 2))).prod hi)

private theorem triePoolPayload_poly {base n t b q j i : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hQ : ComputableTidilyInPolyTime q e encUnary)
    (hJ : ComputableTidilyInPolyTime j e encUnary)
    (hI : ComputableTidilyInPolyTime i e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x))
    (hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolPayload (base x) (n x) (t x) (b x) (q x) (j x) (i x))
      e encUnary := by
  let s := fun x => (triePoolSource (t x) (b x) (q x) (j x)).1
  let r := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.1
  let f := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.1
  let k := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.2
  let L := fun x => normalizeWordBase (base x) (t x) (s x) (r x) (f x)
  let W := fun x => (2:ℕ)^(s x).2
  let K := fun x => (2:ℕ)^((s x).2-b x)
  let B := fun x => (2:ℕ)^b x
  obtain ⟨hs,hd,hr,hf,hk,hL⟩ :=
    triePoolWordScalars_poly hBase hN hT hB hQ hJ hBnd hJnd
  have hL' : ComputableTidilyInPolyTime L e encUnary := hL
  have hK : ComputableTidilyInPolyTime K e encUnary :=
    unary_pow2_of_bound (unary_sub.comp (hd.prod hB)) (layoutHorizon_poly.comp hT)
      (fun x => Nat.pow_le_pow_right (by decide) ((Nat.sub_le ..).trans (hJnd x)))
  have hW : ComputableTidilyInPolyTime W e encUnary :=
    unary_pow2_of_bound hd (layoutHorizon_poly.comp hT)
      (fun x => Nat.pow_le_pow_right (by decide) (hJnd x))
  have hBP : ComputableTidilyInPolyTime B e encUnary := triePoolPower_poly hT hB hBnd
  have hk' : ComputableTidilyInPolyTime k e encUnary := hk
  have hr' : ComputableTidilyInPolyTime r e encUnary := hr
  have hf' : ComputableTidilyInPolyTime f e encUnary := hf
  have hTwoW := unary_mul.comp ((const 2).prod hW)
  have hTwoB := unary_mul.comp ((const 2).prod hBP)
  have hKB := unary_mul.comp (hk'.prod hBP)
  have hField := unary_add.comp ((unary_add.comp ((const 5).prod
    (unary_mul.comp ((const 5).prod hr')))).prod hf')
  have hParent : ComputableTidilyInPolyTime (fun x => L x+W x+2+K x+k x*B x+i x) e encUnary :=
    unary_add.comp ((unary_add.comp ((unary_add.comp ((unary_add.comp
      ((unary_add.comp (hL'.prod hW)).prod (const 2))).prod hK)).prod hKB)).prod hI)
  have hChild : ComputableTidilyInPolyTime
      (fun x => L x+2*W x+2+K x+k x*B x+(i x-2*B x)) e encUnary :=
    unary_add.comp ((unary_add.comp ((unary_add.comp ((unary_add.comp
      ((unary_add.comp (hL'.prod hTwoW)).prod (const 2))).prod hK)).prod hKB)).prod
      (unary_sub.comp (hI.prod hTwoB)))
  have hRaw : ComputableTidilyInPolyTime (fun x => port (n x) (t x)
      ((s x).1,(s x).2) (5+5*r x+f x) (k x*B x+(i x-B x))) e encUnary :=
    slotPort_poly hN hT hs hd hField (unary_add.comp (hKB.prod (unary_sub.comp (hI.prod hBP))))
  have hTest := unary_lt' hI hBP
  have hTest' := unary_lt' hI (unary_mul.comp ((const 2).prod hBP))
  have h := hTest.ite' hParent (hTest'.ite' hRaw hChild)
  simpa only [triePoolPayload,triePoolWire,normalizeSlotWires,trieWiresAt,s,r,f,k,L,W,K,B,
    Function.comp_def,decide_eq_true_eq] using h

end
end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section
variable {A : Type} {e : A ↪ List Bool}

set_option maxHeartbeats 2000000 in
private theorem triePoolLaneGates_poly {base pool n t b q : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hPool : ComputableTidilyInPolyTime pool e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hQ : ComputableTidilyInPolyTime q e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolLaneGates (base x) (pool x) (n x) (t x) (b x) (q x))
      e (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  let jCap := fun x j => trieCapLevel (t x) (b x) j
  let enable := fun x j => triePoolEnable (base x) (n x) (t x) (b x) (q x) (jCap x j)
  let payload := fun x j i => triePoolPayload (base x) (n x) (t x) (b x) (q x) (jCap x j) i
  have hX := fst e encUnary
  have hJ := snd e encUnary
  have hY := fst e₁ encUnary
  have hI := snd e₁ encUnary
  have hW := triePoolWidth_poly hT hB hBnd
  have hM := triePoolCount_poly hT hB hQ
  have hLev := triePoolLevels_poly hT hB
  have hStride := unary_add.comp ((unary_add.comp (hW.prod hLev)).prod (const 2))
  have hAcc0 : ComputableTidilyInPolyTime (fun x => triePoolRowBase (pool x) (t x) (b x) (q x))
      e encUnary := unary_add.comp (hPool.prod (unary_mul.comp (hQ.prod hStride)))
  have hArr := unary_add.comp ((hAcc0.comp hX).prod (const 1))
  have hAcc : ComputableTidilyInPolyTime (fun x : A×ℕ => triePoolAcc (pool x.1) (t x.1) (b x.1) (q x.1) x.2)
      e₁ encUnary := unary_add.comp ((unary_add.comp (hArr.prod (hW.comp hX))).prod hJ)
  have hOut : ComputableTidilyInPolyTime (fun x : A×ℕ => triePoolBit (pool x.1) (t x.1) (b x.1) (q x.1) x.2)
      e₁ encUnary := unary_add.comp (hArr.prod hJ)
  have hCap : ComputableTidilyInPolyTime (fun x : A×ℕ => jCap x.1 x.2) e₁ encUnary :=
    unary_min.comp (hJ.prod (unary_sub.comp ((layoutHeight_poly.comp (hT.comp hX)).prod (hB.comp hX))))
  have hCapBnd (x : A) (j : ℕ) : b x+jCap x j ≤ layoutHeight (t x) := by
    have hh : jCap x j ≤ layoutHeight (t x)-b x := min_le_right ..
    have hb := hBnd x
    omega
  have hEnable : ComputableTidilyInPolyTime (fun x : A×ℕ => enable x.1 x.2) e₁ encUnary :=
    triePoolEnable_poly (hBase.comp hX) (hN.comp hX) (hT.comp hX) (hB.comp hX)
      (hQ.comp hX) hCap (fun x => hBnd x.1) (fun x => hCapBnd x.1 x.2)
  have hX' := hX.comp hY
  have hPayload : ComputableTidilyInPolyTime (fun x : (A×ℕ)×ℕ => payload x.1.1 x.1.2 x.2) e₂ encUnary :=
    triePoolPayload_poly (hBase.comp hX') (hN.comp hX') (hT.comp hX') (hB.comp hX')
      (hQ.comp hX') (hCap.comp hY) hI (fun x => hBnd x.1.1) (fun x => hCapBnd x.1.1 x.1.2)
  have hAll := gatherArray_poly
    (acc := fun x i => triePoolAcc (pool x) (t x) (b x) (q x) i)
    (out := fun x i => triePoolBit (pool x) (t x) (b x) (q x) i)
    (enable := enable) (payload := payload) hW hM hAcc0 hAcc hOut hEnable hPayload
  convert hAll using 1
  funext x
  unfold triePoolLaneGates gatherArray
  congr 1
  apply List.flatMap_congr
  intro j hj
  have hex := trieCapLevel_eq (hBnd x) (List.mem_range.mp hj)
  simp [enable,payload,jCap,hex]

theorem triePoolGateList_polytime {base pool n t b : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hPool : ComputableTidilyInPolyTime pool e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => triePoolGateList (base x) (pool x) (n x) (t x) (b x))
      e (encList gateEnc) := by
  let hX := fst e encUnary
  exact flatMapWithInput (f := fun x q => triePoolLaneGates (base x) (pool x) (n x) (t x) (b x) q)
    (range.comp (triePoolRows_poly hT hB))
    (triePoolLaneGates_poly (hBase.comp hX) (hPool.comp hX) (hN.comp hX) (hT.comp hX)
      (hB.comp hX) (snd e encUnary) (fun x => hBnd x.1))

end
end CNFEncComplexity.Robson

/- RobsonMemPackedLocal -/

namespace CNFEncComplexity.Robson
open CookLevin

def rawOptions (α : Assignment) (n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
  (List.range 3).map (portMemory α n t s)

theorem rawOptions_filter (α : Assignment) (n t : ℕ) (s : ℕ×ℕ) :
    (rawOptions α n t s).filterMap id = slotRows α n t s := by
  simp [rawOptions,slotRows,List.filterMap_map,Function.comp_def]

def relabelOptions (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
    List (Option ObservedAccess) := (rawOptions α n t s).map (Option.map (compactRow label))

private theorem map_opt_filter {A B : Type} (f : A → B) (l : List (Option A)) :
    ((l.map (Option.map f)).filterMap id) = (l.filterMap id).map f := by
  induction l with
  | nil => rfl
  | cons x xs ih =>
    cases x
    · exact ih
    · rename_i x
      exact congrArg (List.cons (f x)) ih

theorem relabelOptions_filter (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
    (relabelOptions α n t label s).filterMap id = (slotRows α n t s).map (compactRow label) := by
  rw [relabelOptions,map_opt_filter,rawOptions_filter]

theorem relabelOptions_length (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
    (relabelOptions α n t label s).length = 3 := by simp [relabelOptions,rawOptions]

private theorem observationWords_in {α : Assignment} {n t : ℕ} {s : ℕ×ℕ}
    (hs : s ∈ layoutSlots t) {x : ℕ} (hx : x ∈ observationWords (slotRows α n t s)) :
    x ∈ observationWords (memoryStream α n t) := by
  obtain ⟨r,hr,hval⟩ := List.mem_flatMap.mp hx
  exact List.mem_flatMap.mpr ⟨r,List.mem_flatMap.mpr ⟨s,hs,hr⟩,hval⟩

private theorem memoryWord_fits {α : Assignment} {n t : ℕ} {x : ℕ}
    (hx : x ∈ observationWords (memoryStream α n t)) : x.size ≤ layoutHorizon t := by
  obtain ⟨e,he,hword⟩ := List.mem_flatMap.mp hx
  obtain ⟨s,hs,he'⟩ := List.mem_flatMap.mp he
  obtain ⟨i,_,he'⟩ := List.mem_filterMap.mp he'
  obtain ⟨ha,hv,ho⟩ := portMemory_sizes he'
  rcases s with ⟨start,k⟩
  obtain ⟨_,hk,_⟩ := layout_mem.mp hs
  have hW : 2^k ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hk
  simp only [List.mem_cons,List.mem_nil_iff,or_false] at hword
  rcases hword with rfl|rfl|rfl
  · exact ha.trans hW
  · exact hv.trans hW
  · exact ho.trans hW

theorem memoryPacking_exists {α : Assignment} {n t b : ℕ} (h : SlotsWellFormed α n t)
    (hb : 0 < b) (hAllow : layoutHorizon t ≤ b ∨ 18*layoutHorizon t < 2^b) :
    ∃ (dict : List WordEdge) (label : ℕ → ℕ),
      WordEdge.Interned dict ∧ label 0=0 ∧
      (∀ e ∈ dict, max e.parent e.child < 2^b) ∧
      b*dict.length ≤ 18*layoutHorizon t ∧
      (∀ x ∈ observationWords (memoryStream α n t), WordLabel b dict x (label x)) ∧
      PackedSlots α n t b dict (fun s => (relabelOptions α n t label s).filterMap id) := by
  have hCore : ∃ (dict : List WordEdge) (label : ℕ → ℕ),
      WordEdge.Interned dict ∧ label 0=0 ∧
      (∀ e ∈ dict, max e.parent e.child < 2^b) ∧
      b*dict.length ≤ 18*layoutHorizon t ∧
      (∀ x ∈ observationWords (memoryStream α n t), WordLabel b dict x (label x)) := by
    rcases hAllow with hAll|hIds
    · refine ⟨[],fun x => 2*x,?_,by simp,by simp,by simp,?_⟩
      · exact ⟨by simp,by simp,by simp⟩
      · intro x hx
        exact .small ((memoryWord_fits hx).trans hAll)
    · have hw := memoryStream_word_budget h
      have h2 : 2*(9*layoutHorizon t) < 2^b := by omega
      obtain ⟨d,l,hG,hZero,hNum,hBound,hWords⟩ := wordLabels_exist_bounded _ hw b hb h2
      have hSize := (Nat.mul_le_mul_left b hNum).trans ((labelEntries_budget hb _).trans
        (Nat.mul_le_mul_left 2 hw))
      exact ⟨d,l,hG,hZero,hBound,by omega,fun x hx => (hWords x hx).1⟩
  obtain ⟨d,l,hG,hZero,hId,hCount,hWord⟩ := hCore
  refine ⟨d,l,hG,hZero,hId,hCount,hWord,⟨?_,?_⟩⟩
  · intro s hs
    rw [relabelOptions_filter]
    exact compactRows_labels (fun x hx => hWord x (observationWords_in hs hx))
  · intro s hs row hr
    rw [relabelOptions_filter] at hr
    obtain ⟨raw,hRaw,rfl⟩ := List.mem_map.mp hr
    obtain ⟨i,_,hm⟩ := List.mem_filterMap.mp hRaw
    obtain ⟨ha,hv,ho⟩ := portMemory_sizes hm
    have hx (x : ℕ) (hx : x ∈ [raw.action.address,raw.action.value,raw.old]) :
        (l x).size ≤ b+1 ∧ (l x).size ≤ x.size+1 :=
      (hWord x (observationWords_in hs (List.mem_flatMap.mpr ⟨raw,hRaw,hx⟩))).size_le
        (fun e he => (le_max_right ..).trans_lt (hId e he))
    have hl (x : ℕ) (hx' : x ∈ [raw.action.address,raw.action.value,raw.old]) (hw : x.size ≤ 2^s.2) :
        (l x).size ≤ min (2^s.2) b+1 := by
      obtain ⟨hb,hc⟩ := hx x hx'
      calc
        _ ≤ min (2^s.2+1) (b+1) :=
          le_min ((hc.trans (Nat.add_le_add_right hw _))) hb
        _ = _ := by rw [Nat.add_min_add_right]
    exact ⟨hl _ (by simp) ha,hl _ (by simp) hv,hl _ (by simp) ho⟩

end CNFEncComplexity.Robson

/- RobsonTrieComponentNative -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section
variable {A : Type} {e : A ↪ List Bool}

theorem normalizeAfter_polytime {base t : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary) :
    ComputableTidilyInPolyTime (fun x => normalizeAfter (base x) (t x)) e encUnary := by
  have hH := layoutHorizon_poly.comp hT
  have hJ := unary_add.comp ((layoutHeight_poly.comp hT).prod (const 1))
  have hSlots := unary_mul.comp ((unary_mul.comp (hH.prod hJ)).prod (const 9))
  have hStride := unary_add.comp ((unary_mul.comp ((const 6).prod hH)).prod (const 4))
  exact unary_add.comp (hBase.prod (unary_mul.comp (hSlots.prod hStride)))

theorem triePoolSourceWire_polytime {pool t b : A → ℕ}
    (hP : ComputableTidilyInPolyTime pool e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hCap : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun p : (A × ℕ) × ℕ =>
      triePoolSourceWire (pool p.1.1) (t p.1.1) (b p.1.1) p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary := by
  let ep := encPair e encUnary
  have hA := fst e encUnary
  have hQ := snd e encUnary
  have hP' := hP.comp hA
  have hW := triePoolWidth_poly (hT.comp hA) (hB.comp hA) (fun p => hCap p.1)
  have hL := triePoolLevels_poly (hT.comp hA) (hB.comp hA)
  have hStride := unary_add.comp ((unary_add.comp (hW.prod hL)).prod (const 2))
  have hRow : ComputableTidilyInPolyTime (fun p : A × ℕ =>
      triePoolRowBase (pool p.1) (t p.1) (b p.1) p.2) ep encUnary :=
    unary_add.comp (hP'.prod (unary_mul.comp (hQ.prod hStride)))
  exact unary_add.comp ((hRow.comp (fst ep encUnary)).prod (snd ep encUnary))

set_option maxHeartbeats 2000000 in
theorem normalizeMemoryGates_polytime {base n t b : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hN : ComputableTidilyInPolyTime n e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hCap : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => normalizeMemoryGates (base x) (n x) (t x) (b x))
      e (encList gateEnc) := by
  have hP := normalizeAfter_polytime hBase hT
  have hLayout := normalizeLayoutGates_polytime hBase hN hT hB hCap
  have hPool := triePoolGateList_polytime hBase hP hN hT hB hCap
  have hDictionaryBase := triePoolAfter_poly hP hT hB hCap
  have hWidth := unary_pow2_of_bound hB (layoutHorizon_poly.comp hT)
    (fun x => Nat.pow_le_pow_right (by decide) (hCap x))
  let src := fun x => triePoolSourceWire (normalizeAfter (base x) (t x)) (t x) (b x)
  have hDictionary := trieDictionaryGates_polytime (src := src) hDictionaryBase hWidth
    (triePoolHeight_poly hT hB) (triePoolRows_poly hT hB)
    (triePoolSourceWire_polytime hP hT hB hCap)
  exact listAppend' (listAppend' hLayout hPool) hDictionary

theorem normalizeMemoryEnd_polytime {base t b : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e encUnary)
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hB : ComputableTidilyInPolyTime b e encUnary)
    (hCap : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => normalizeMemoryEnd (base x) (t x) (b x))
      e encUnary := by
  have hP := normalizeAfter_polytime hBase hT
  have hDictionaryBase := triePoolAfter_poly hP hT hB hCap
  have hWidth := unary_pow2_of_bound hB (layoutHorizon_poly.comp hT)
    (fun x => Nat.pow_le_pow_right (by decide) (hCap x))
  have hHeight := triePoolHeight_poly hT hB
  have hCount := triePoolRows_poly hT hB
  exact trieSortPassEnd_poly (trieSortPassEnd_poly hDictionaryBase hWidth hHeight hCount) hWidth hHeight hCount

end

theorem normalizeMemoryGates_extend_layout (a : Assignment) (base n t : ℕ)
    (hBase : sharedLimit n t ≤ base) (hShape : SlotsWellFormed a n t) :
    ∃ α : Assignment,
      (∀ i, i < base ∨ normalizeMemoryEnd base t (trieLevel t) ≤ i → α i = a i) ∧
      ∀ g ∈ normalizeMemoryGates base n t (trieLevel t), g.Holds α := by
  have hWidth : 0 < trieWidth t := Nat.two_pow_pos _
  obtain ⟨dict,lab,hGood,_,hIds,_,hLab,_⟩ :=
    memoryPacking_exists hShape hWidth (trieWidth_allow t)
  obtain ⟨α,hFr,hG,_⟩ := normalizeMemoryGates_complete a base n t (trieLevel t)
    hBase (trieLevel_cap t) hShape dict lab hGood
    (fun x hx => (le_max_right _ _).trans_lt (hIds x hx)) hLab
  exact ⟨α,hFr,hG⟩

end CNFEncComplexity.Robson

/- RobsonTrieComponentGeometry -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

private theorem trieRouteCopy_length (base B h : ℕ) (src : ℕ → ℕ → ℕ) :
    (trieRouteCopy base B h src).length = 2^h*trieRowWidth B := by
  have hL (qs : List ℕ) : (qs.flatMap (fun q =>
      wordCopy (trieRowWidth B) (trieRouteIn base B q) (src q))).length = qs.length*trieRowWidth B := by
    induction qs with
    | nil => simp
    | cons q qs ih =>
      rw [List.flatMap_cons,List.length_append,ih]
      simp only [wordCopy,List.length_map,List.length_range,List.length_cons,Nat.add_mul,Nat.one_mul] <;> omega
  exact (hL _).trans (congrArg (fun q => q*trieRowWidth B) List.length_range)

private theorem trieSortPass_length (base B h : ℕ) (hB : 0 < B)
    (byChild : Bool) (src : ℕ → ℕ → ℕ) :
    (trieSortPass base B h byChild src).length ≤ 27*(h+1)*(2^h*B) := by
  have hRows : (trieRouteRows base B h).length = 2^h := by simp [trieRouteRows]
  have hCheck := trieSortCheckGates_length B byChild (trieRouteEnd base B h) (trieRouteRows base B h)
  rw [hRows] at hCheck
  have hWidth : trieRowWidth B ≤ 4*B := by unfold trieRowWidth; omega
  have hPair : 12*B+7 ≤ 19*B := by omega
  simp only [trieSortPass,List.length_append,trieRouteCopy_length,routeNamedGates_length]
  calc
    _ ≤ 2^h*trieRowWidth B+(2*h+1)*2^h*trieRowWidth B+2^h*(12*B+7) := Nat.add_le_add_left hCheck _
    _ = 2^h*((2*h+2)*trieRowWidth B+(12*B+7)) := by ring
    _ ≤ 2^h*((2*h+2)*(4*B)+19*B) := Nat.mul_le_mul_left _
      (Nat.add_le_add (Nat.mul_le_mul_left _ hWidth) hPair)
    _ = (2^h*B)*(8*(h+1)+19) := by ring
    _ ≤ (2^h*B)*(27*(h+1)) := Nat.mul_le_mul_left _ (by omega)
    _ = 27*(h+1)*(2^h*B) := by ring

private theorem trieNonzeroList_length (B h : ℕ) (src : ℕ → ℕ → ℕ) :
    (trieNonzeroList B h src).length = 2^h := by
  have hL (qs : List ℕ) : (qs.flatMap fun q => trieNonzeroGates B (trieRowFromNat B (src q))).length =
      qs.length := by
    induction qs with
    | nil => rfl
    | cons q qs ih => simp [List.flatMap_cons,trieNonzeroGates,ih,Nat.add_comm]
  exact (hL _).trans List.length_range

private theorem trieDictionaryGates_length (base B h : ℕ) (hB : 0 < B) (src : ℕ → ℕ → ℕ) :
    (trieDictionaryGates base B h src).length ≤ 55*(h+1)*(2^h*B) := by
  have first := trieSortPass_length base B h hB false src
  have second := trieSortPass_length (trieSortPassEnd base B h) B h hB true src
  have hNonzero : 2^h ≤ (h+1)*(2^h*B) := by
    have hB' : 2^h ≤ 2^h*B := by simpa using Nat.mul_le_mul_left (2^h) hB
    apply hB'.trans
    simpa using Nat.mul_le_mul_right (2^h*B) (Nat.succ_pos h)
  simp only [trieDictionaryGates,List.length_append,trieNonzeroList_length]
  calc
    _ ≤ (h+1)*(2^h*B) + 27*(h+1)*(2^h*B) + 27*(h+1)*(2^h*B) :=
      Nat.add_le_add (Nat.add_le_add hNonzero first) second
    _ = 55*(h+1)*(2^h*B) := by ring

/-- Word normalization, gathering, and the two dictionary passes fit the layout budget. -/
theorem normalizeMemoryGates_length (base n t b : ℕ) (hb : b ≤ layoutHeight t) :
    (normalizeMemoryGates base n t b).length ≤ 5000*(layoutHorizon t*(layoutHeight t+1)) := by
  let Q := triePoolHeight t b
  have hGeometry : 2^Q * 2^b = 16*layoutHorizon t := by
    have he : Q+b = layoutHeight t+4 := by dsimp [Q,triePoolHeight]; omega
    rw [← pow_add,he,pow_add]
    exact Nat.mul_comm _ _
  have hHeight : Q+1 ≤ 5*(layoutHeight t+1) := by dsimp [Q,triePoolHeight]; omega
  have hLayout := normalizeLayoutGates_length base n t b
  have hPool := triePoolGateList_length base (normalizeAfter base t) n t b hb
  have hDictionary := trieDictionaryGates_length
    (triePoolAfter (normalizeAfter base t) t b) (2^b) Q (Nat.two_pow_pos b)
    (triePoolSourceWire (normalizeAfter base t) t b)
  change (trieDictionaryGates _ (2^b) Q _).length ≤ 55*(Q+1)*(2^Q*2^b) at hDictionary
  rw [hGeometry] at hDictionary
  have hD : (trieDictionaryGates (triePoolAfter (normalizeAfter base t) t b) (2^b) Q
      (triePoolSourceWire (normalizeAfter base t) t b)).length ≤
      4400*(layoutHorizon t*(layoutHeight t+1)) := by
    calc
      _ ≤ 55*(Q+1)*(16*layoutHorizon t) := hDictionary
      _ ≤ 55*(5*(layoutHeight t+1))*(16*layoutHorizon t) :=
        Nat.mul_le_mul_right _ (Nat.mul_le_mul_left _ hHeight)
      _ = _ := by ring
  simp only [normalizeMemoryGates,List.length_append]
  change _ + _ + (trieDictionaryGates _ _ Q _).length ≤ _
  apply (Nat.add_le_add (Nat.add_le_add hLayout hPool) hD).trans
  omega

private theorem triePoolAfter_le_normalizeMemoryEnd (base t b : ℕ) :
    triePoolAfter (normalizeAfter base t) t b ≤ normalizeMemoryEnd base t b := by
  unfold normalizeMemoryEnd trieDictionaryEnd trieSortPassEnd trieRouteEnd
  omega

theorem normalizeAfter_le_end (base t b : ℕ) : normalizeAfter base t ≤ normalizeMemoryEnd base t b :=
  (Nat.le_add_right _ _).trans (triePoolAfter_le_normalizeMemoryEnd base t b)

/-- Changes above the end of the reserved region preserve all normalization checks. -/
theorem normalizeMemoryGates_frame (a α : Assignment) (base n t b : ℕ)
    (hBase : sharedLimit n t ≤ base) (hb : b ≤ layoutHeight t)
    (hFr : ∀ i < normalizeMemoryEnd base t b, α i = a i)
    (h : ∀ g ∈ normalizeMemoryGates base n t b, g.Holds a) :
    ∀ g ∈ normalizeMemoryGates base n t b, g.Holds α := by
  let pool := normalizeAfter base t
  let top := triePoolAfter pool t b
  have hTop : top ≤ normalizeMemoryEnd base t b := triePoolAfter_le_normalizeMemoryEnd base t b
  simp only [normalizeMemoryGates,List.forall_mem_append] at h ⊢
  obtain ⟨⟨hLayout,hPool⟩,hDict⟩ := h
  refine ⟨⟨?_,normalizePoolGates_frame a α base pool n t b hBase le_rfl hb
    (fun i hi => hFr _ (hi.trans_le hTop)) hPool⟩,?_⟩
  · intro g hg
    obtain ⟨s,hs,hm⟩ := List.mem_flatMap.mp hg
    obtain ⟨r,hr,hm⟩ := List.mem_flatMap.mp hm
    obtain ⟨f,hf,hm⟩ := List.mem_flatMap.mp hm
    apply (gate_congr g (fun i hi => hFr _ ((normalizeWord_name_below hBase hs
      (List.mem_range.mp hr) (List.mem_range.mp hf)
      (normalizeWordGates_frame base n t b s r f hs (List.mem_range.mp hr)
        (List.mem_range.mp hf) g hm i hi)).trans_le (normalizeAfter_le_end base t b)))).mpr
    exact hLayout g hg
  · intro g hg
    apply (gate_congr g (fun i hi => hFr i (trieDictionaryGates_names_lt top (2^b) (triePoolHeight t b)
      (triePoolSourceWire pool t b) (triePoolSourceWire_below pool t b) g hg i hi))).mpr
    exact hDict g hg

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