Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Word dimensions and uniform Boolean word gates for RAM memory

Definition
CNFEncComplexity_RobsonMemoryParameters

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

complexity-theorysatisfiability

Computes the trie chunk width and tier counts, and generates fixed-width word copies, padded wire access, and constant-word gates in polynomial time.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonMemoryDimensions -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

def trieLevel (t : ℕ) : ℕ :=
  min (layoutHeight t) (slotLevel (18*layoutHorizon t).size)

def trieWidth (t : ℕ) : ℕ := 2^trieLevel t

theorem trieLevel_cap (t : ℕ) : trieLevel t ≤ layoutHeight t := min_le_left _ _

theorem trieWidth_in_horizon (t : ℕ) : trieWidth t ≤ layoutHorizon t :=
  Nat.pow_le_pow_right (by decide) (trieLevel_cap t)

theorem trieWidth_allow (t : ℕ) :
    layoutHorizon t ≤ trieWidth t ∨ 18*layoutHorizon t < 2^trieWidth t := by
  let b := (18*layoutHorizon t).size
  by_cases h : layoutHeight t ≤ slotLevel b
  · left
    change layoutHorizon t ≤ 2^(min (layoutHeight t) (slotLevel b))
    rw [min_eq_left h]
    exact le_refl _
  · have h' : slotLevel b ≤ layoutHeight t := by omega
    right
    change 18*layoutHorizon t < 2^(2^min (layoutHeight t) (slotLevel b))
    rw [min_eq_right h']
    exact (Nat.lt_size_self _).trans_le (Nat.pow_le_pow_right (by decide) (le_slotWidth b))

theorem trieWidth_bound (t : ℕ) : trieWidth t ≤ 22*(t.size+1) := by
  let m := 18*layoutHorizon t
  have hm : m.size ≤ t.size+11 := by
    apply Nat.size_le.mpr
    have hHor : layoutHorizon t ≤ 8*(9*t+1) := by
      change slotWidth (4*(9*t+1)) ≤ _
      have h := slotWidth_le_double (cost:=4*(9*t+1)) (by omega)
      omega
    rw [pow_add]
    norm_num
    have ht := Nat.lt_size_self t
    unfold m
    omega
  have hb : 0 < m.size := Nat.size_pos.mpr (by
    dsimp [m,layoutHorizon]
    positivity)
  have hw := slotWidth_le_double hb
  have h' : trieWidth t ≤ slotWidth m.size :=
    Nat.pow_le_pow_right (by decide) (min_le_right _ _)
  omega

set_option maxHeartbeats 2000000 in
theorem trieLevel_poly : ComputableTidilyInPolyTime trieLevel encUnary encUnary := by
  have hx := unary_mul.comp ((const 18).prod layoutHorizon_poly)
  have hSize := unary_size_poly.comp hx
  have hLevel := unary_size_poly.comp (unary_sub.comp (hSize.prod (const 1)))
  exact unary_min.comp (layoutHeight_poly.prod hLevel)

theorem trieWidth_poly : ComputableTidilyInPolyTime trieWidth encUnary encUnary :=
  unary_pow2_of_bound trieLevel_poly layoutHorizon_poly trieWidth_in_horizon

end CNFEncComplexity.Robson

/- RobsonTraceBasicNative -/

namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime

theorem dynamic_pin_poly {A : Type} {e : A ↪ List Bool} {r : A → ℕ} {b : A → Bool}
    (hr : ComputableTidilyInPolyTime r e encUnary) (hb : ComputableTidilyInPolyTime b e encBool) :
    ComputableTidilyInPolyTime (fun a => Gate.pin (r a) (b a)) e gateEnc := by
  have hh := hb.ite' (gate_pin true hr) (gate_pin false hr)
  convert hh using 1
  funext a
  cases hb : b a <;> simp

theorem wordConst_poly {A : Type} {e : A ↪ List Bool} {w v : A → ℕ} {key : A → ℕ → ℕ}
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (hv : ComputableTidilyInPolyTime v e encNat)
    (hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2)
      (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => wordConst (w a) (key a) (v a)) e (encList gateEnc) := by
  have hBit := binary_testBit (hv.comp (fst e encUnary)) (snd e encUnary)
  exact mapWithInput (range.comp hw) (dynamic_pin_poly hk hBit)


theorem wordCopy_poly {A : Type} {e : A ↪ List Bool} {w : A → ℕ} {l r : A → ℕ→ℕ}
    (hw : ComputableTidilyInPolyTime w 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 => wordCopy (w a) (l a) (r a)) e (encList gateEnc) := by
  exact mapWithInput (range.comp hw) (gate_copy hl hr)

theorem boundedWordConst_poly {A : Type} {e : A ↪ List Bool} {w v : A → ℕ} {key : A → ℕ → ℕ}
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (hv : ComputableTidilyInPolyTime v e encNat)
    (hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2)
      (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => boundedWordConst (w a) (key a) (v a)) e (encList gateEnc) := by
  have hh := (ComputableTidilyInPolyTime.binary_lt' hv (binary_two_pow.comp hw)).ite'
    (wordConst_poly hw hv hk) (const [.assert []])
  simpa only [boundedWordConst,decide_eq_true_eq,Function.comp_def] using hh

theorem paddedKey_poly {A : Type} {e : A ↪ List Bool} {n z : A → ℕ} {k : A → ℕ → ℕ}
    (hn : ComputableTidilyInPolyTime n e encUnary)
    (hz : ComputableTidilyInPolyTime z e encUnary)
    (hk : ComputableTidilyInPolyTime (fun p : A×ℕ => k p.1 p.2) (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun p : A×ℕ => paddedKey (n p.1) (z p.1) (k p.1) p.2)
      (encPair e encUnary) encUnary := by
  have hDim := fst e encUnary
  have hIdx := snd e encUnary
  have hh := (unary_lt' hIdx (hn.comp hDim)).ite' hk (hz.comp hDim)
  simpa only [paddedKey,decide_eq_true_eq, Function.comp_def] using hh

theorem paddedWordCopy_poly {A : Type} {e : A ↪ List Bool} {w n m z : A → ℕ}
    {l r : A → ℕ→ℕ}
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (hn : ComputableTidilyInPolyTime n e encUnary)
    (hm : ComputableTidilyInPolyTime m e encUnary)
    (hz : ComputableTidilyInPolyTime z 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 => paddedWordCopy (w a) (n a) (m a) (z a) (l a) (r a))
      e (encList gateEnc) :=
  wordCopy_poly hw (paddedKey_poly hn hz hl) (paddedKey_poly hm hz hr)

theorem exactSumGates_poly {A : Type} {e : A ↪ List Bool} {base w : A → ℕ} {l r o : A → ℕ→ℕ}
    (hb : ComputableTidilyInPolyTime base e encUnary)
    (hw : ComputableTidilyInPolyTime w 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)
    (ho : ComputableTidilyInPolyTime (fun p : A×ℕ => o p.1 p.2) (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => exactSumGates (base a) (w a) (l a) (r a) (o a))
      e (encList gateEnc) := by
  have hp : ComputableTidilyInPolyTime (fun a => rippleCarryWire (base a) (w a)) e encUnary := by
    unfold rippleCarryWire
    fun_prop
  have hk : ComputableTidilyInPolyTime (fun p : A×ℕ => rippleBitWire (base p.1) p.2)
      (encPair e encUnary) encUnary := by
    have hb' := hb.comp (fst e encUnary)
    unfold rippleBitWire
    fun_prop
  exact listAppend' (rippleCircuit_polytime false hb hw hl hr)
    (cons' (gate_pin false hp) (wordCopy_poly hw ho hk))

theorem nonzeroWord_poly {A : Type} {e : A ↪ List Bool} {w : A → ℕ} {key : A → ℕ→ℕ}
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2) (encPair e encUnary) encUnary) :
    ComputableTidilyInPolyTime
      (fun a => CNFEncComplexity.Robson.BinaryPort.nonzeroGates ⟨w a,key a⟩) e (encList gateEnc) := by
  have hLiteral := unary_add.comp ((unary_mul.comp ((const 2).prod hk)).prod (const 1))
  have hFields := mapWithInput (f:=fun a i => 2*key a i+1) (range.comp hw) hLiteral
  have h := gate_assert (c:=fun a => (List.range (w a)).map (fun i => .Pos (key a i))) (by
    simpa only [clauseN,List.map_map,Function.comp_def,literalN] using hFields)
  exact cons' h (const [])

end CNFEncComplexity.RobsonCNF
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