Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The tier memory gate list from a uniform normalizer

Definition
CNFEncComplexity_RobsonMemoryTierGateList

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

complexity-theorysatisfiability

The gate list assembled from the supplied normalizer, tier emission, and sorted-window checks. The definitions identify the single gate family whose generation, exactness, and size are needed for the memory gate component.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierRowGates
import Definitions.Def_CNFEncComplexity_RobsonMemoryNormalizationInterface

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

/-- All tiers read the same low. Their scratch variables occupy distinct residue classes. -/
def memoryTierWire (low levels j r : ℕ) : ℕ :=
  if r < low then r else low+levels*(r-low)+j

def memoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (j : ℕ) : List Gate :=
  (tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j)).map
    (Gate.rename (memoryTierWire low (emitLevels t) j))

def allMemoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) : List Gate :=
  (List.range (emitLevels t)).flatMap (memoryTierGates t low z o src)

def boundedMemoryTierWidth (t j : ℕ) : ℕ := 2^(min j (emitLevels t-1))

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

abbrev EmitLane := (ℕ×ℕ)×ℕ×Bool

def emitLaneList (slots : List (ℕ×ℕ)) : List EmitLane :=
  slots.flatMap fun s => (List.range 3).flatMap (fun r => [(s,r,false),(s,r,true)])

def emitLaneKey (base region n t j z o : ℕ) (p : EmitLane) : ℕ→ℕ :=
  let u := emitInputs base n t p.1 p.2.1
  let start := emitBlockBase region t j p.1 p.2.1+8
  if p.2.2 then emitSecondRow u (2^j) z o start else emitFirstRow u (2^j) z o start

def emitSource (base region n t j z o : ℕ) (slots : List (ℕ×ℕ)) (k : ℕ) : ℕ→ℕ :=
  match (emitLaneList slots)[k]? with
  | none => fun _ => z
  | some p => emitLaneKey base region n t j z o p

def compactSlotOptions (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
  (List.range 3).map (slotCompactMemory a base n t (trieLevel t) s)

abbrev EmitWidthBlock (t : ℕ) := {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3

abbrev EmitCoreBlock (t : ℕ) := Fin (emitLevels t) × {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3

def emitCoreLayoutGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
  (List.range (emitLevels t)).flatMap fun j => emitTierGateList base region n t j z (slots j)

def emitAllGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
  emitWidthLayoutGates base region n t ++ emitCoreLayoutGates base region n t z slots

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin

def emitSlotTier (j : ℕ) (slots : List (Option ObservedAccess)) : List (Option LocalRecord) :=
  slots.flatMap (emitTier j)

def memoryEmitLanes (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
    List (Option LocalRecord) :=
  (memoryTierSlots t j).flatMap fun s => emitSlotTier j (packed s)

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

def memoryZero (n t : ℕ) : ℕ := sharedLimit n t
def memoryOne (n t : ℕ) : ℕ := sharedLimit n t+1
def memoryNormalizeBase (n t : ℕ) : ℕ := sharedLimit n t+2
def memorySortBase (stop : ℕ → ℕ → ℕ) (n t : ℕ) : ℕ := emitBlockTop (stop n t) t

def memoryConstants (n t : ℕ) : List Gate :=
  [.pin (memoryZero n t) false,.pin (memoryOne n t) true]

def memoryEmitter (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
  emitAllGates (memoryNormalizeBase n t) (stop n t) n t (memoryZero n t) (memoryTierSlots t)

def capMemoryTier (t j : ℕ) : ℕ := min j (emitLevels t-1)

theorem capMemoryTier_lt (t j : ℕ) : capMemoryTier t j < emitLevels t := by
  unfold capMemoryTier
  have hp : 0 < emitLevels t := Nat.succ_pos _
  exact (min_le_right _ _).trans_lt (by omega)

def memorySorterSource (stop : ℕ → ℕ → ℕ) (n t j : ℕ) : ℕ → ℕ → ℕ :=
  let k := capMemoryTier t j
  emitSource (memoryNormalizeBase n t) (stop n t) n t k
    (memoryZero n t) (memoryOne n t) (memoryTierSlots t k)

theorem memorySorterSource_eq (stop : ℕ → ℕ → ℕ) (n t j : ℕ) (hj : j < emitLevels t) :
    memorySorterSource stop n t j = emitSource (memoryNormalizeBase n t) (stop n t) n t j
      (memoryZero n t) (memoryOne n t) (memoryTierSlots t j) := by
  have hm : capMemoryTier t j = j := min_eq_left (by omega)
  simp [memorySorterSource, hm]

def memorySorter (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
  allMemoryTierGates t (memorySortBase stop n t) (memoryZero n t) (memoryOne n t) (memorySorterSource stop n t)

def rawMemoryGates (normalize : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
  ((memoryConstants n t++normalize n t)++memoryEmitter stop n t)++memorySorter stop n t

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