Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time generation of the RAM tier-emission circuit

Definition
CNFEncComplexity_RobsonMemoryTierEmitterNative

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

complexity-theorysatisfiability

Encodes the slot descriptors, fixed-width rows, source lookup and gate lists in polynomial time on the prescribed unary dimensions and wire numbers.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierRowAssembly

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonEmitNative -/

namespace CNFEncComplexity.Robson

set_option maxHeartbeats 4000000

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section EmitNative
variable {A : Type} {e : A ↪ List Bool}
private abbrev EU := encUnary
private abbrev EG := encList gateEnc

private theorem emitAdd {f g : A → ℕ}
    (a : ComputableTidilyInPolyTime f e EU) (b : ComputableTidilyInPolyTime g e EU) :
    ComputableTidilyInPolyTime (fun x => f x+g x) e EU := unary_add.comp (a.prod b)

private theorem emitSub {f g : A → ℕ}
    (a : ComputableTidilyInPolyTime f e EU) (b : ComputableTidilyInPolyTime g e EU) :
    ComputableTidilyInPolyTime (fun x => f x-g x) e EU := unary_sub.comp (a.prod b)

private theorem emitMul {f g : A → ℕ}
    (a : ComputableTidilyInPolyTime f e EU) (b : ComputableTidilyInPolyTime g e EU) :
    ComputableTidilyInPolyTime (fun x => f x*g x) e EU := unary_mul.comp (a.prod b)

/-- A family of emission inputs supplied by six tidy wire accessors. -/
structure NativeEmitInput (e : A ↪ List Bool) (u : A → EmitInput) : Prop where
  width : ComputableTidilyInPolyTime (fun a => (u a).width) e EU
  live : ComputableTidilyInPolyTime (fun a => (u a).live) e EU
  writes : ComputableTidilyInPolyTime (fun a => (u a).writes) e EU
  address : ComputableTidilyInPolyTime (fun p : A×ℕ => (u p.1).address p.2) (encPair e EU) EU
  value : ComputableTidilyInPolyTime (fun p : A×ℕ => (u p.1).value p.2) (encPair e EU) EU
  old : ComputableTidilyInPolyTime (fun p : A×ℕ => (u p.1).old p.2) (encPair e EU) EU

theorem tierAbove_poly {n base k : A → ℕ}
    (hn : ComputableTidilyInPolyTime n e EU) (hb : ComputableTidilyInPolyTime base e EU)
    (hk : ComputableTidilyInPolyTime k e EU) :
    ComputableTidilyInPolyTime (fun a => tierAbove (n a) (base a) (k a)) e EU :=
  emitAdd hb (unary_min.comp (hn.prod hk))

theorem tierTestGates_poly {j x y n base : A → ℕ}
    (hj : ComputableTidilyInPolyTime j e EU)
    (hx : ComputableTidilyInPolyTime x e EU) (hy : ComputableTidilyInPolyTime y e EU)
    (hn : ComputableTidilyInPolyTime n e EU) (hb : ComputableTidilyInPolyTime base e EU)
    (hw : ComputableTidilyInPolyTime (fun a => 2^(j a)) e EU) :
    ComputableTidilyInPolyTime (fun a => tierTestGates (j a) (x a) (y a) (n a) (base a)) e EG := by
  have hhi := emitSub hw (const 1)
  have hlo := emitSub (unary_pow2_of_bound (emitSub hj (const 1)) hw (fun _ =>
    Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _))) (const 1)
  have g0 := gate_disj hb (tierAbove_poly hn hx hhi) (tierAbove_poly hn hy hhi)
  have g1 := gate_inv (emitAdd hb (const 1)) hb
  have g2 := gate_disj (emitAdd hb (const 2)) (tierAbove_poly hn hx hlo) (tierAbove_poly hn hy hlo)
  have g3 := gate_conj (emitAdd hb (const 3)) (emitAdd hb (const 1)) (emitAdd hb (const 2))
  have h := (unary_beq hj (const 0)).cond (cons' g0 (cons' g1 (const [])))
    (cons' g0 (cons' g1 (cons' g2 (cons' g3 (const [])))))
  convert h using 1
  funext a
  by_cases he : j a = 0 <;> simp [tierTestGates,he]

theorem tierTestOutput_poly {j out : A → ℕ}
    (hj : ComputableTidilyInPolyTime j e EU) (ho : ComputableTidilyInPolyTime out e EU) :
    ComputableTidilyInPolyTime (fun a => tierTestOutput (j a) (out a)) e EU := by
  have h := (unary_beq hj (const 0)).cond (emitAdd ho (const 1)) (emitAdd ho (const 3))
  convert h using 1
  funext a
  by_cases he : j a = 0 <;> simp [tierTestOutput,he]

theorem emissionControl_poly {base live writes src dst : A → ℕ}
    (hb : ComputableTidilyInPolyTime base e EU) (hl : ComputableTidilyInPolyTime live e EU)
    (hw : ComputableTidilyInPolyTime writes e EU) (hs : ComputableTidilyInPolyTime src e EU)
    (hd : ComputableTidilyInPolyTime dst e EU) :
    ComputableTidilyInPolyTime
      (fun a => emissionControl (base a) (live a) (writes a) (src a) (dst a)) e EG := by
  have hh (i : ℕ) := emitAdd hb (const i)
  exact cons' (gate_mux hb hw hs hd) (cons' (gate_conj (hh 1) hl hb)
    (cons' (gate_inv (hh 2) hs) (cons' (gate_conj (hh 3) hw hd)
    (cons' (gate_conj (hh 4) (hh 2) (hh 3)) (cons' (gate_conj (hh 5) hl (hh 4))
    (cons' (gate_inv (hh 6) hw) (cons' (gate_disj (hh 7) (hh 6) hd) (const []))))))))

theorem emissionMux_poly {base w writes : A → ℕ} {old value : A → ℕ → ℕ}
    (hb : ComputableTidilyInPolyTime base e EU) (hw : ComputableTidilyInPolyTime w e EU)
    (hr : ComputableTidilyInPolyTime writes e EU)
    (ho : ComputableTidilyInPolyTime (fun p : A×ℕ => old p.1 p.2) (encPair e EU) EU)
    (hv : ComputableTidilyInPolyTime (fun p : A×ℕ => value p.1 p.2) (encPair e EU) EU) :
    ComputableTidilyInPolyTime
      (fun a => emissionMux (base a) (w a) (writes a) (old a) (value a)) e EG := by
  have hBase := emitAdd ((emitAdd hb (const 8)).comp (fst e EU)) (snd e EU)
  exact mapWithInput (f:=fun a i => Gate.mux (base a+8+i) (writes a) (old a i) (value a i))
    (range.comp hw) (gate_mux hBase (hr.comp (fst e EU)) ho hv)

theorem emissionRow_poly {w z active beforeFlag afterFlag k : A → ℕ}
    {addr before after : A → ℕ → ℕ}
    (hw : ComputableTidilyInPolyTime w e EU) (hz : ComputableTidilyInPolyTime z e EU)
    (hl : ComputableTidilyInPolyTime active e EU)
    (hb : ComputableTidilyInPolyTime beforeFlag e EU)
    (hf : ComputableTidilyInPolyTime afterFlag e EU)
    (ha : ComputableTidilyInPolyTime (fun p : A×ℕ => addr p.1 p.2) (encPair e EU) EU)
    (hv : ComputableTidilyInPolyTime (fun p : A×ℕ => before p.1 p.2) (encPair e EU) EU)
    (hx : ComputableTidilyInPolyTime (fun p : A×ℕ => after p.1 p.2) (encPair e EU) EU)
    (hk : ComputableTidilyInPolyTime k e EU) :
    ComputableTidilyInPolyTime
      (fun a => emissionRow (w a) (z a) (active a) (beforeFlag a) (afterFlag a)
        (addr a) (before a) (after a) (k a)) e EU := by
  let idA := id' (encIn:=e)
  have h1 := emitAdd (const 1) hw
  have h2 := emitAdd (const 2) (emitMul (const 2) hw)
  have h3 := emitAdd (const 3) (emitMul (const 3) hw)
  have hi := ha.comp (idA.prod (emitSub hk (const 1)))
  have hj := hv.comp (idA.prod (emitSub hk (emitAdd (const 2) hw)))
  have hs := hx.comp (idA.prod (emitSub hk (emitAdd (const 3) (emitMul (const 2) hw))))
  have h := (unary_beq hk (const 0)).cond hl
    ((unary_lt' hk h1).cond hi ((unary_beq hk h1).cond hb
      ((unary_lt' hk h2).cond hj ((unary_beq hk h2).cond hf ((unary_lt' hk h3).cond hs hz)))))
  simpa only [emissionRow,beq_iff_eq,decide_eq_true_eq,Function.comp_def,id_eq] using h

theorem emitFirstRow_poly {u : A → EmitInput} {w z o base : A → ℕ}
    (hu : NativeEmitInput e u)
    (hw : ComputableTidilyInPolyTime w e EU) (hz : ComputableTidilyInPolyTime z e EU)
    (ho : ComputableTidilyInPolyTime o e EU) (hb : ComputableTidilyInPolyTime base e EU) :
    ComputableTidilyInPolyTime (fun p : A×ℕ => emitFirstRow (u p.1)
      (w p.1) (z p.1) (o p.1) (base p.1) p.2) (encPair e EU) EU := by
  let left := fst e EU
  let idx := snd e EU
  let lift := (left.comp (fst (encPair e EU) EU)).prod (snd (encPair e EU) EU)
  have hAddr := (paddedKey_poly (n:=fun a => (u a).width) (z:=z) (k:=fun a => (u a).address) hu.width hz hu.address).comp lift
  have hVal := (paddedKey_poly (n:=fun a => (u a).width) (z:=z) (k:=fun a => (u a).value) hu.width hz hu.value).comp lift
  have hBefore := emitAdd ((emitAdd hb (const 8)).comp (left.comp (fst (encPair e EU) EU)))
    (snd (encPair e EU) EU)
  exact emissionRow_poly (A := A×ℕ) (e := encPair e EU)
    (addr := fun p => paddedKey (u p.1).width (z p.1) (u p.1).address)
    (before := fun p i => base p.1+8+i)
    (after := fun p => paddedKey (u p.1).width (z p.1) (u p.1).value)
    (hw.comp left) (hz.comp left) ((emitAdd hb (const 1)).comp left)
    (ho.comp left) ((emitAdd hb (const 7)).comp left) hAddr hBefore hVal idx

theorem emitSecondRow_poly {u : A → EmitInput} {w z o base : A → ℕ}
    (hu : NativeEmitInput e u)
    (hw : ComputableTidilyInPolyTime w e EU) (hz : ComputableTidilyInPolyTime z e EU)
    (ho : ComputableTidilyInPolyTime o e EU) (hb : ComputableTidilyInPolyTime base e EU) :
    ComputableTidilyInPolyTime (fun p : A×ℕ => emitSecondRow (u p.1)
      (w p.1) (z p.1) (o p.1) (base p.1) p.2) (encPair e EU) EU := by
  let left := fst e EU
  let idx := snd e EU
  let lift := (left.comp (fst (encPair e EU) EU)).prod (snd (encPair e EU) EU)
  have hAddr := (paddedKey_poly (n:=fun a => (u a).width) (z:=z) (k:=fun a => (u a).address) hu.width hz hu.address).comp lift
  have hVal := (paddedKey_poly (n:=fun a => (u a).width) (z:=z) (k:=fun a => (u a).value) hu.width hz hu.value).comp lift
  have hBefore := hz.comp (left.comp (fst (encPair e EU) EU))
  exact emissionRow_poly (A := A×ℕ) (e := encPair e EU)
    (addr := fun p => paddedKey (u p.1).width (z p.1) (u p.1).address)
    (before := fun p _ => z p.1)
    (after := fun p => paddedKey (u p.1).width (z p.1) (u p.1).value)
    (hw.comp left) (hz.comp left) ((emitAdd hb (const 5)).comp left)
    (hz.comp left) (ho.comp left) hAddr hBefore hVal idx

theorem EmitInput.coreGates_poly {u : A → EmitInput} {f : A → EmitFlags} {j z b : A → ℕ}
    (hu : NativeEmitInput e u)
    (hAddr : ComputableTidilyInPolyTime (fun a => (f a).addr) e EU)
    (hValue : ComputableTidilyInPolyTime (fun a => (f a).value) e EU)
    (hOld : ComputableTidilyInPolyTime (fun a => (f a).old) e EU)
    (hj : ComputableTidilyInPolyTime j e EU) (hz : ComputableTidilyInPolyTime z e EU)
    (hb : ComputableTidilyInPolyTime b e EU)
    (hw : ComputableTidilyInPolyTime (fun a => 2^(j a)) e EU) :
    ComputableTidilyInPolyTime (fun a => (u a).coreGates (f a) (j a) (z a) (b a)) e EG := by
  have hB4 := emitAdd hb (const 4)
  have hB8 := emitAdd hb (const 8)
  have hF := tierTestGates_poly hj hAddr hOld hu.width hb hw
  have hG := tierTestGates_poly hj hAddr hValue hu.width hB4 hw
  have hControl := emissionControl_poly hB8 hu.live hu.writes
    (tierTestOutput_poly hj hb) (tierTestOutput_poly hj hB4)
  have hMux := emissionMux_poly
    (old := fun a => paddedKey (u a).width (z a) (u a).old)
    (value := fun a => paddedKey (u a).width (z a) (u a).value)
    hB8 hw hu.writes
    (paddedKey_poly (k := fun a => (u a).old) hu.width hz hu.old)
    (paddedKey_poly (k := fun a => (u a).value) hu.width hz hu.value)
  exact listAppend' (listAppend' (listAppend' hF hG) hControl) hMux

end EmitNative

end CNFEncComplexity.Robson

/- RobsonMemoryEmitNative -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

set_option maxHeartbeats 3500000

private abbrev EmitNatEnc := encUnary
private abbrev EmitGateListEnc := encList gateEnc
private abbrev EmitSlotEnc := encPair encUnary encUnary
private abbrev EmitLaneEnc := encPair EmitSlotEnc (encPair encUnary encBool)

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

theorem emitLevels_poly : ComputableTidilyInPolyTime emitLevels encUnary encUnary := by
  have h := unary_size_poly.comp (unary_add.comp (trieWidth_poly.prod (const 1)))
  exact unary_add.comp (h.prod (const 1))

private theorem emitTierWidthBound_poly :
    ComputableTidilyInPolyTime (fun t => 2*(layoutHorizon t+1)+17) encUnary encUnary := by
  have h := layoutHorizon_poly
  fun_prop

private theorem emitTierWidth_poly {t j : A → ℕ} (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hj : ComputableTidilyInPolyTime j e EmitNatEnc) (hb : ∀ x, j x < emitLevels (t x)) :
    ComputableTidilyInPolyTime (fun x => 2^(j x)) e EmitNatEnc := by
  apply unary_pow2_of_bound hj (emitTierWidthBound_poly.comp ht)
  intro x
  have h := emitBlockWidth_bound (hb x)
  unfold emitBlockStride at h
  change 2^(j x) ≤ 2*(layoutHorizon (t x)+1)+17
  omega

private theorem emitFlagBase_poly {region t a j r f : A → ℕ}
    (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (ha : ComputableTidilyInPolyTime a e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc)
    (hr : ComputableTidilyInPolyTime r e EmitNatEnc) (hf : ComputableTidilyInPolyTime f e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => emitFlagBase (region x) (t x) (a x,j x) (r x) (f x)) e EmitNatEnc := by
  have hH := layoutHorizon_poly.comp ht
  have hh := layoutHeight_poly.comp ht
  unfold emitFlagBase emitFlagIndex emitSlotIndex emitFlagStride
  dsimp
  fun_prop

theorem emitBlockTop_poly {region t : A → ℕ}
    (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => emitBlockTop (region x) (t x)) e EmitNatEnc := by
  have hH := layoutHorizon_poly.comp ht
  have hh := layoutHeight_poly.comp ht
  have hE := emitLevels_poly.comp ht
  unfold emitBlockTop emitFlagTop emitFlagStride emitSlotSpan emitBlockStride
  fun_prop

private theorem emitBlockBase_poly {region t tier a j r : A → ℕ}
    (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hJ : ComputableTidilyInPolyTime tier e EmitNatEnc)
    (ha : ComputableTidilyInPolyTime a e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc)
    (hr : ComputableTidilyInPolyTime r e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => emitBlockBase (region x) (t x) (tier x) (a x,j x) (r x)) e EmitNatEnc := by
  have hH := layoutHorizon_poly.comp ht
  have hh := layoutHeight_poly.comp ht
  have hP := unary_add.comp (hh.prod (const 1))
  have hSpan := unary_mul.comp (hH.prod hP)
  have hFStride := unary_add.comp (hH.prod (const 2))
  have hFCount := unary_mul.comp ((const 9).prod hSpan)
  have hF := unary_add.comp (hRegion.prod (unary_mul.comp (hFCount.prod hFStride)))
  have hBStride := emitTierWidthBound_poly.comp ht
  have hSlot := unary_add.comp ((unary_mul.comp (ha.prod hP)).prod hj)
  have hII := unary_add.comp ((unary_mul.comp (hJ.prod hSpan)).prod hSlot)
  have hIndex := unary_add.comp ((unary_mul.comp ((const 3).prod hII)).prod hr)
  exact unary_add.comp (hF.prod (unary_mul.comp (hIndex.prod hBStride)))

private theorem emitNormalizeWidth_poly {t j : A → ℕ}
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc)
    (hJL : ∀ x, j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => normalizeWidth (trieLevel (t x)) (0,j x)) e EmitNatEnc := by
  have hW := unary_pow2_of_bound hj (layoutHorizon_poly.comp ht)
    (fun x => Nat.pow_le_pow_right (by decide) (hJL x))
  have hT := trieWidth_poly.comp ht
  unfold normalizeWidth
  dsimp
  exact unary_add.comp ((unary_min.comp (hW.prod hT)).prod (const 1))

private theorem emitNormalizeLabel_poly {base n t a j r f i : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (ha : ComputableTidilyInPolyTime a e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc)
    (hr : ComputableTidilyInPolyTime r e EmitNatEnc) (hf : ComputableTidilyInPolyTime f e EmitNatEnc)
    (hi : ComputableTidilyInPolyTime i e EmitNatEnc) (hJL : ∀ x, j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x =>
      (normalizeSlotWires (base x) (n x) (t x) (trieLevel (t x)) (a x,j x) (r x) (f x)).label (i x)) e EmitNatEnc := by
  have hW := layoutHorizon_poly.comp ht
  have hH := layoutHeight_poly.comp ht
  have hB := trieLevel_poly.comp ht
  have hP := unary_pow2_of_bound hj hW (fun x => Nat.pow_le_pow_right (by decide) (hJL x))
  have hK := unary_pow2_of_bound (unary_sub.comp (hj.prod hB)) hW
    (fun x => Nat.pow_le_pow_right (by decide) ((Nat.sub_le (j x) (trieLevel (t x))).trans (hJL x)))
  unfold normalizeSlotWires normalizeWordBase normalizeStride trieWiresAt
  dsimp
  fun_prop

private theorem emitInputAccess_poly {base n t a j r : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hn : ComputableTidilyInPolyTime n e EmitNatEnc)
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) (ha : ComputableTidilyInPolyTime a e EmitNatEnc)
    (hj : ComputableTidilyInPolyTime j e EmitNatEnc) (hr : ComputableTidilyInPolyTime r e EmitNatEnc)
    (hJL : ∀ x, j x ≤ layoutHeight (t x)) :
    NativeEmitInput e (fun x => emitInputs (base x) (n x) (t x) (a x,j x) (r x)) := by
  let l := fst e EmitNatEnc
  let i := snd e EmitNatEnc
  have hL (f : ℕ) := emitNormalizeLabel_poly (n:=fun p => n p.1) (hBase.comp l)
    (ht.comp l) (ha.comp l) (hj.comp l) (hr.comp l) (const f) i (fun p => hJL p.1)
  refine ⟨emitNormalizeWidth_poly ht hj hJL,?_,?_,hL 0,hL 1,hL 2⟩
  · exact slotPort_poly hn ht ha hj (by fun_prop) (const 0)
  · exact slotPort_poly hn ht ha hj (by fun_prop) (const 0)

private theorem emitOne_poly {base region n t tier z a j r : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hJ : ComputableTidilyInPolyTime tier e EmitNatEnc) (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (ha : ComputableTidilyInPolyTime a e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc)
    (hr : ComputableTidilyInPolyTime r e EmitNatEnc) (hJT : ∀ x, tier x < emitLevels (t x))
    (hJL : ∀ x, j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => emitOne (base x) (region x) (n x) (t x) (tier x) (z x)
      (a x,j x) (r x)) e EmitGateListEnc := by
  exact EmitInput.coreGates_poly (f:=fun x => emitFlags (region x) (t x) (a x,j x) (r x))
    (emitInputAccess_poly hBase hn ht ha hj hr hJL)
    (emitFlagBase_poly hRegion ht ha hj hr (const 0))
    (emitFlagBase_poly hRegion ht ha hj hr (const 1))
    (emitFlagBase_poly hRegion ht ha hj hr (const 2))
    hJ hz (emitBlockBase_poly hRegion ht hJ ha hj hr) (emitTierWidth_poly ht hJ hJT)

theorem emitTierGateList_poly {base region n t tier z : A → ℕ} {slots : A → List (ℕ×ℕ)}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hJ : ComputableTidilyInPolyTime tier e EmitNatEnc) (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (hSlots : ComputableTidilyInPolyTime slots e (encList EmitSlotEnc))
    (hsub : ∀ x, slots x ⊆ layoutSlots (t x)) (hJT : ∀ x, tier x < emitLevels (t x)) :
    ComputableTidilyInPolyTime (fun x => emitTierGateList (base x) (region x) (n x) (t x) (tier x) (z x)
      (slots x)) e EmitGateListEnc := by
  let p := encPair e EmitSlotEnc
  let l := fst e EmitSlotEnc
  let s := snd e EmitSlotEnc
  let a := (fst EmitNatEnc EmitNatEnc).comp s
  let j := (snd EmitNatEnc EmitNatEnc).comp s
  let q := fst p EmitNatEnc
  let r := snd p EmitNatEnc
  let x := l.comp q
  have hMin := unary_min.comp ((j.comp q).prod (layoutHeight_poly.comp (ht.comp x)))
  have hOne := emitOne_poly (hBase.comp x) (hRegion.comp x) (hn.comp x) (ht.comp x)
    (hJ.comp x) (hz.comp x) (a.comp q) hMin r (fun p => hJT p.1.1) (fun _ => min_le_right ..)
  have hOuter := flatMapWithInput (f := fun x (s : ℕ×ℕ) => (List.range 3).flatMap fun r =>
    emitOne (base x) (region x) (n x) (t x) (tier x) (z x) (s.1,min s.2 (layoutHeight (t x))) r)
    hSlots (flatMapWithInput (const (List.range 3)) hOne)
  convert hOuter using 1
  funext x
  apply List.flatMap_congr
  intro s hs
  rw [min_eq_left (layout_mem.mp (hsub x hs)).2.1]

private theorem emitWidthGates_poly {base region n t a j r f : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) (ha : ComputableTidilyInPolyTime a e EmitNatEnc)
    (hj : ComputableTidilyInPolyTime j e EmitNatEnc) (hr : ComputableTidilyInPolyTime r e EmitNatEnc)
    (hf : ComputableTidilyInPolyTime f e EmitNatEnc) (hJL : ∀ x, j x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => emitWidthGates (base x) (region x) (n x) (t x)
      (a x,j x) (r x) (f x)) e EmitGateListEnc := by
  let l := fst e EmitNatEnc
  let i := snd e EmitNatEnc
  exact widthCircuit_polytime (emitFlagBase_poly hRegion ht ha hj hr hf)
    (emitNormalizeWidth_poly ht hj hJL)
    (emitNormalizeLabel_poly (n:=fun p => n p.1) (hBase.comp l) (ht.comp l) (ha.comp l)
      (hj.comp l) (hr.comp l) (hf.comp l) i (fun p => hJL p.1))

theorem emitWidthLayout_poly {base region n t : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => emitWidthLayoutGates (base x) (region x) (n x) (t x)) e EmitGateListEnc := by
  let p := encPair e EmitSlotEnc
  let q := encPair p EmitNatEnc
  let l := fst e EmitSlotEnc
  let s := snd e EmitSlotEnc
  let a := (fst EmitNatEnc EmitNatEnc).comp s
  let j := (snd EmitNatEnc EmitNatEnc).comp s
  let l' := fst p EmitNatEnc
  let r := snd p EmitNatEnc
  let l'' := fst q EmitNatEnc
  let f := snd q EmitNatEnc
  let x := l.comp (l'.comp l'')
  have hMin := unary_min.comp ((j.comp (l'.comp l'')).prod (layoutHeight_poly.comp (ht.comp x)))
  have hg := emitWidthGates_poly (n:=fun p => n p.1.1.1) (hBase.comp x) (hRegion.comp x) (ht.comp x)
    (a.comp (l'.comp l'')) hMin (r.comp l'') f (fun _ => min_le_right ..)
  have hOuter := flatMapWithInput (f := fun x (s : ℕ×ℕ) => (List.range 3).flatMap fun r =>
    (List.range 3).flatMap fun f =>
      emitWidthGates (base x) (region x) (n x) (t x) (s.1,min s.2 (layoutHeight (t x))) r f)
    (layoutSlots_poly.comp ht) (flatMapWithInput (const (List.range 3))
      (flatMapWithInput (const (List.range 3)) hg))
  convert hOuter using 1
  funext x
  apply List.flatMap_congr
  intro s hs
  rw [min_eq_left (layout_mem.mp hs).2.1]

theorem emitCoreLayout_poly {base region n t z : A → ℕ} {slots : A → ℕ → List (ℕ×ℕ)}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (hSlots : ComputableTidilyInPolyTime (fun p : A×ℕ => slots p.1 p.2) (encPair e EmitNatEnc) (encList EmitSlotEnc))
    (hsub : ∀ x j, slots x j ⊆ layoutSlots (t x)) :
    ComputableTidilyInPolyTime (fun x => emitCoreLayoutGates (base x) (region x) (n x) (t x) (z x)
      (slots x)) e EmitGateListEnc := by
  let l := fst e EmitNatEnc
  let j := snd e EmitNatEnc
  have hLevels := emitLevels_poly.comp ht
  have hjmax := unary_sub.comp ((hLevels.comp l).prod (const 1))
  have hj := unary_min.comp (j.prod hjmax)
  have hJL (x : A×ℕ) : min x.2 (emitLevels (t x.1)-1) < emitLevels (t x.1) := by
    have hp : 0 < emitLevels (t x.1) := by unfold emitLevels; omega
    exact (min_le_right _ _).trans_lt (by omega)
  have hGate := emitTierGateList_poly (hBase.comp l) (hRegion.comp l) (hn.comp l) (ht.comp l)
    hj (hz.comp l) hSlots (fun p => hsub p.1 p.2) hJL
  have hOuter := flatMapWithInput (f := fun x j =>
    emitTierGateList (base x) (region x) (n x) (t x) (min j (emitLevels (t x)-1)) (z x) (slots x j))
    (range.comp hLevels) hGate
  convert hOuter using 1
  funext x
  apply List.flatMap_congr
  intro j hj
  rw [min_eq_left (by have h := List.mem_range.mp hj; omega)]

theorem emitAllGates_poly {base region n t z : A → ℕ} {slots : A → ℕ → List (ℕ×ℕ)}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (hSlots : ComputableTidilyInPolyTime (fun p : A×ℕ => slots p.1 p.2) (encPair e EmitNatEnc) (encList EmitSlotEnc))
    (hsub : ∀ x j, slots x j ⊆ layoutSlots (t x)) :
    ComputableTidilyInPolyTime (fun x => emitAllGates (base x) (region x) (n x) (t x) (z x) (slots x)) e EmitGateListEnc :=
  listAppend' (emitWidthLayout_poly (n:=n) hBase hRegion ht)
    (emitCoreLayout_poly hBase hRegion hn ht hz hSlots hsub)

private theorem emitLaneList_poly :
    ComputableTidilyInPolyTime emitLaneList (encList EmitSlotEnc) (encList EmitLaneEnc) := by
  let unit := encList EmitSlotEnc
  let p := encPair unit EmitSlotEnc
  let q := encPair p EmitNatEnc
  let s := snd unit EmitSlotEnc
  let ql := fst p EmitNatEnc
  let r := snd p EmitNatEnc
  have hTail : ComputableTidilyInPolyTime
      (fun (x : (List (ℕ×ℕ)×(ℕ×ℕ))×ℕ) => [(x.1.2,x.2,false),(x.1.2,x.2,true)]) q (encList EmitLaneEnc) :=
    cons' ((s.comp ql).prod (r.prod (const false)))
      (cons' ((s.comp ql).prod (r.prod (const true))) (const []))
  exact flatMapWithInput (f := fun (_ : List (ℕ×ℕ)) s =>
    (List.range 3).flatMap fun r => [(s,r,false),(s,r,true)]) (id' (encIn:=unit))
      (flatMapWithInput (const (List.range 3)) hTail)

private theorem emitLaneKey_poly {base region n t tier z o : A → ℕ} {desc : A → EmitLane} {bit : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hJ : ComputableTidilyInPolyTime tier e EmitNatEnc) (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (ho : ComputableTidilyInPolyTime o e EmitNatEnc) (hd : ComputableTidilyInPolyTime desc e EmitLaneEnc)
    (hb : ComputableTidilyInPolyTime bit e EmitNatEnc)
    (hJT : ∀ x, tier x < emitLevels (t x)) :
    ComputableTidilyInPolyTime (fun x =>
      let d := desc x
      emitLaneKey (base x) (region x) (n x) (t x) (tier x) (z x) (o x)
        ((d.1.1,min d.1.2 (layoutHeight (t x))),d.2) (bit x)) e EmitNatEnc := by
  let s := (fst EmitSlotEnc (encPair EmitNatEnc encBool)).comp hd
  let p := (snd EmitSlotEnc (encPair EmitNatEnc encBool)).comp hd
  let r := (fst EmitNatEnc encBool).comp p
  let f := (snd EmitNatEnc encBool).comp p
  have ha := (fst EmitNatEnc EmitNatEnc).comp s
  have hj := (snd EmitNatEnc EmitNatEnc).comp s
  have hmin := unary_min.comp (hj.prod (layoutHeight_poly.comp ht))
  have hU := emitInputAccess_poly hBase hn ht ha hmin r (fun _ => min_le_right ..)
  have hStart := unary_add.comp ((emitBlockBase_poly hRegion ht hJ ha hmin r).prod (const 8))
  have hw := emitTierWidth_poly ht hJ hJT
  have hctx := (id' (encIn:=e)).prod hb
  have hg := f.cond ((emitSecondRow_poly hU hw hz ho hStart).comp hctx)
    ((emitFirstRow_poly hU hw hz ho hStart).comp hctx)
  convert hg using 1
  funext x
  by_cases hf : (desc x).2.2 = true <;> simp [emitLaneKey,Function.comp_def,hf]

theorem emitSource_poly {base region n t tier z o lane bit : A → ℕ} {slots : A → List (ℕ×ℕ)}
    (hBase : ComputableTidilyInPolyTime base e EmitNatEnc) (hRegion : ComputableTidilyInPolyTime region e EmitNatEnc)
    (hn : ComputableTidilyInPolyTime n e EmitNatEnc) (ht : ComputableTidilyInPolyTime t e EmitNatEnc)
    (hJ : ComputableTidilyInPolyTime tier e EmitNatEnc) (hz : ComputableTidilyInPolyTime z e EmitNatEnc)
    (ho : ComputableTidilyInPolyTime o e EmitNatEnc) (hl : ComputableTidilyInPolyTime lane e EmitNatEnc)
    (hb : ComputableTidilyInPolyTime bit e EmitNatEnc)
    (hSlots : ComputableTidilyInPolyTime slots e (encList EmitSlotEnc))
    (hsub : ∀ x, slots x ⊆ layoutSlots (t x)) (hJT : ∀ x, tier x < emitLevels (t x)) :
    ComputableTidilyInPolyTime (fun x => emitSource (base x) (region x) (n x) (t x) (tier x)
      (z x) (o x) (slots x) (lane x) (bit x)) e EmitNatEnc := by
  have hList := emitLaneList_poly.comp hSlots
  have hLen := (length EmitLaneEnc).comp hList
  have hDesc := (listGetD (encA:=EmitLaneEnc) ((0,0),0,false)).comp (hList.prod hl)
  have hRead := emitLaneKey_poly hBase hRegion hn ht hJ hz ho hDesc hb hJT
  have hg := (unary_lt' hl hLen).ite' hRead hz
  convert hg using 1
  funext x
  unfold emitSource
  cases hm : (emitLaneList (slots x))[lane x]? with
  | none =>
    have hge : ¬lane x < (emitLaneList (slots x)).length := by
      intro hi
      rw [List.getElem?_eq_getElem hi] at hm
      contradiction
    simp [Function.comp_def,hge,hm]
  | some d =>
    obtain ⟨hi,he⟩ := List.getElem?_eq_some_iff.mp hm
    have hp := List.mem_of_getElem? hm
    obtain ⟨s,r,f⟩ := d
    have hs := (emitLaneList_members hp).1
    have hj := (layout_mem.mp (hsub x hs)).2.1
    simp [Function.comp_def,hi,List.getD_eq_getElem?_getD,he,min_eq_left hj]

theorem memoryTierSlots_subset (t j : ℕ) : memoryTierSlots t j ⊆ layoutSlots t :=
  fun _ h => (List.mem_filter.mp h).1

theorem memoryTierSlots_poly {t j : A → ℕ}
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => memoryTierSlots (t x) (j x)) e (encList EmitSlotEnc) := by
  let l := fst e EmitSlotEnc
  let s := snd e EmitSlotEnc
  let k := (snd EmitNatEnc EmitNatEnc).comp s
  have hx := unary_sub.comp ((hj.comp l).prod (const 2))
  exact filterWithInput (layoutSlots_poly.comp ht) (unary_le' hx k)

theorem memoryTierRows_poly {t j : A → ℕ}
    (ht : ComputableTidilyInPolyTime t e EmitNatEnc) (hj : ComputableTidilyInPolyTime j e EmitNatEnc) :
    ComputableTidilyInPolyTime (fun x => memoryTierRows (t x) (j x)) e EmitNatEnc := by
  have h := (length EmitSlotEnc).comp (memoryTierSlots_poly ht hj)
  exact unary_mul.comp ((const 6).prod h)

end Arithmetic

theorem emitLevels_budget (t : ℕ) : emitLevels t ≤ 24*(t.size+1) := by
  unfold emitLevels
  have h := trieWidth_bound t
  have hsz : (trieWidth t+1).size ≤ trieWidth t+1 := Nat.size_le.mpr Nat.lt_two_pow_self
  omega

theorem emitAll_memoryLength (base region n t z : ℕ) :
    (emitAllGates base region n t z (memoryTierSlots t)).length ≤
      27*((layoutSlots t).map fun s => 2^s.2).sum + 408*(layoutHorizon t*emitLevels t) := by
  have hb (j : ℕ) : (memoryTierSlots t j).length*2^j ≤ 8*layoutHorizon t := by
    have h := memoryTierRows_width t j
    unfold memoryTierRows at h
    rw [Nat.mul_assoc] at h
    omega
  simp only [emitAllGates,List.length_append]
  exact Nat.add_le_add (emitWidthLayout_length _ _ _ _) (emitCoreLayout_length _ _ _ _ _ _ (fun j _ => hb j))

theorem emitAll_memoryExact {a : Assignment} {base region n t z o j : ℕ}
    (h : GateSat a (emitAllGates base region n t z (memoryTierSlots t)))
    (hj : j < emitLevels t) (hz : a z = false) (ho : a o = true) :
    rawMemoryRows a (2^j) (memoryTierRows t j)
      (emitSource base region n t j z o (memoryTierSlots t j)) =
        memoryEmitLanes t j (compactSlotOptions a base n t) :=
  emitAll_exact h (memoryTierSlots_subset t) hj hz ho

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