Polynomial-time generation of the RAM tier-emission circuit
DefinitionCNFEncComplexity_RobsonMemoryTierEmitterNativecomplexity-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).