Assembling the tiered RAM rows and checks
DefinitionCNFEncComplexity_RobsonMemoryTierRowAssemblycomplexity-theorysatisfiability
Combines local emission gates over the dyadic layout and uses disjoint auxiliary names for the window checks of every tier.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierRowGates
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonAllTiers -/
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)
private theorem memoryTier_pull {low levels j : ℕ} (hj : j < levels)
(a : Assignment) (b : ℕ → Assignment)
(hKeep : ∀ j < levels, ∀ r < low, b j r = a r) :
(fun k => if k < low then a k
else b ((k-low)%levels) (low+(k-low)/levels)) ∘
memoryTierWire low levels j = b j := by
funext r
by_cases hr : r < low
· simp [memoryTierWire,Function.comp_def,hr,hKeep j hj r hr]
· have hpre : low ≤ r := by omega
have hn : ¬ low+levels*(r-low)+j < low := by omega
have hsub : low+levels*(r-low)+j-low = levels*(r-low)+j := by omega
have hm : (levels*(r-low)+j)%levels = j := by
rw [Nat.mul_add_mod, Nat.mod_eq_of_lt hj]
have hd : (levels*(r-low)+j)/levels = r-low := by
rw [Nat.mul_add_div (Nat.zero_lt_of_lt hj),Nat.div_eq_of_lt hj,Nat.add_zero]
simp [memoryTierWire,Function.comp_def,hr,hn,hsub,hm,hd,Nat.add_sub_of_le hpre]
theorem allMemoryTierGates_exact (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (a : Assignment)
(hzKey : z < low) (hoKey : o < low) (hz : a z = false) (ho : a o = true)
(hSrc : ∀ j < emitLevels t, ∀ i < memoryTierRows t j, ∀ k < memLaneWidth (2^j) 0,
src j i k < low) :
ExtendsWith low (allMemoryTierGates t low z o src) a ↔
∀ j < emitLevels t, TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j)
(rawMemoryRows a (2^j) (memoryTierRows t j) (src j)) (groupInitial (some j)) := by
classical
constructor
· rintro ⟨b,hKeep,hG⟩ j hj
let c := b ∘ memoryTierWire low (emitLevels t) j
have hPre (r : ℕ) (hr : r < low) : c r = a r := by simpa [c,Function.comp_def,memoryTierWire,hr] using hKeep r hr
have hSat : ∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j), g.Holds c := by
apply (renamedCircuit_correct _ _ _).1
intro g hg
exact hG g (List.mem_flatMap.mpr ⟨j,List.mem_range.mpr hj,hg⟩)
have hc := tierBatchGates_sound _ _ _ _ _ _ _ _
((hPre z hzKey).trans hz) ((hPre o hoKey).trans ho) (bitTier_initial_restricted j) hSat
apply (sorterTierCertificate_eq ..).1
unfold sorterTierCertificate at hc ⊢
rwa [sorterRawRows_congr _ _ _ c a (fun i hi k hk => hPre _ (hSrc j hj i hi k hk))] at hc
· intro h
have hExt (j : ℕ) :
∃ b : Assignment, (∀ r < low, b r = a r) ∧
(j < emitLevels t → ∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j), g.Holds b) := by
by_cases hj : j < emitLevels t
· obtain ⟨b,hKeep,hG⟩ := (tierBatch_mission_certificate t j low z o (src j) a
hzKey hoKey (hSrc j hj) hz ho).2 (h j hj)
exact ⟨b,fun r hr => hKeep r (.inl hr),fun _ => hG⟩
· exact ⟨a,fun _ _ => rfl,fun hj' => (hj hj').elim⟩
choose b hKeep hG using hExt
let c : Assignment := fun k => if k < low then a k
else b ((k-low)%emitLevels t) (low+(k-low)/emitLevels t)
refine ⟨c,fun r hr => by simp [c,hr],?_⟩
intro g hg
obtain ⟨j,hj,hg⟩ := List.mem_flatMap.mp hg
apply (renamedCircuit_correct _ _ _).2 _ g hg
rw [show c ∘ memoryTierWire low (emitLevels t) j = b j from
memoryTier_pull (List.mem_range.mp hj) a b (fun j _ => hKeep j)]
exact hG j (List.mem_range.mp hj)
theorem allMemoryTierGates_length (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) :
(allMemoryTierGates t low z o src).length ≤
1572864*layoutHorizon t*(trieWidth t+1)+786432*layoutHorizon t := by
have flatLength (xs : List ℕ) :
(xs.flatMap (memoryTierGates t low z o src)).length =
(xs.map (fun j => (tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j)).length)).sum := by
induction xs with
| nil => rfl
| cons j js ih => simp [ih, memoryTierGates, List.flatMap_cons]
unfold allMemoryTierGates
rw [flatLength]
have sumRange (f : ℕ → ℕ) (n : ℕ) :
((List.range n).map f).sum = ∑ j ∈ Finset.range n, f j := by
induction n with
| zero => simp
| succ n ih => rw [List.range_succ,List.map_append,List.sum_append,Finset.sum_range_succ,← ih]; simp
rw [sumRange]
exact tierBatchGates_total_budget t (trieWidth t) _ fun j _ =>
tierBatchGates_layout_budget _ _ _ _ _ _
section NativeTiers
variable {A : Type} {e : A ↪ List Bool}
private theorem memoryTierWire_poly {low levels j r : A → ℕ}
(hL : ComputableTidilyInPolyTime low e encUnary)
(hC : ComputableTidilyInPolyTime levels e encUnary)
(hJ : ComputableTidilyInPolyTime j e encUnary)
(hR : ComputableTidilyInPolyTime r e encUnary) :
ComputableTidilyInPolyTime (fun x => memoryTierWire (low x) (levels x) (j x) (r x)) e encUnary := by
have h1 := unary_sub.comp (hR.prod hL)
have h2 := unary_mul.comp (hC.prod h1)
have h3 := unary_add.comp (hL.prod h2)
have h4 := unary_add.comp (h3.prod hJ)
simpa only [memoryTierWire, decide_eq_true_eq, Function.comp_def] using (unary_lt' hR hL).ite' hR h4
def boundedMemoryTierWidth (t j : ℕ) : ℕ := 2^(min j (emitLevels t-1))
theorem boundedMemoryTierWidth_eq {t j : ℕ} (hj : j < emitLevels t) :
boundedMemoryTierWidth t j = 2^j := by
rw [boundedMemoryTierWidth, min_eq_left (by omega)]
private theorem memoryTierLevels_poly : ComputableTidilyInPolyTime emitLevels encUnary encUnary := by
have hB := unary_add.comp (trieWidth_poly.prod (const 1))
have hC := unary_size_poly.comp hB
exact unary_add.comp (hC.prod (const 1))
theorem boundedMemoryTierWidth_poly {t j : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hJ : ComputableTidilyInPolyTime j e encUnary) :
ComputableTidilyInPolyTime (fun a => boundedMemoryTierWidth (t a) (j a)) e encUnary := by
have hLim := unary_sub.comp ((memoryTierLevels_poly.comp hT).prod (const 1))
have hMin := unary_min.comp (hJ.prod hLim)
have hH := unary_add.comp ((layoutHorizon_poly.comp hT).prod (const 1))
have hB := unary_add.comp ((unary_mul.comp ((const 2).prod hH)).prod (const 17))
apply unary_pow2_of_bound hMin hB
intro a
have hPos : 0 < emitLevels (t a) := Nat.succ_pos _
have hm : min (j a) (emitLevels (t a)-1) < emitLevels (t a) :=
lt_of_le_of_lt (min_le_right _ _) (by omega)
have h := emitBlockWidth_bound hm
change 2^(min (j a) (emitLevels (t a)-1)) ≤ 2*(layoutHorizon (t a)+1)+17
unfold emitBlockStride at h
omega
private def boundedMemoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (j : ℕ) : List Gate :=
(tierBatchGates (memoryTierRows t j) (boundedMemoryTierWidth t j) j low z o (src j)).map
(Gate.rename (memoryTierWire low (emitLevels t) j))
theorem allMemoryTierGates_poly {t low z o : A → ℕ} {src : A → ℕ → ℕ → ℕ → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hL : ComputableTidilyInPolyTime low e encUnary)
(hZ : ComputableTidilyInPolyTime z e encUnary)
(hO : ComputableTidilyInPolyTime o e encUnary)
(hR : ComputableTidilyInPolyTime (fun q : A×ℕ => memoryTierRows (t q.1) q.2)
(encPair e encUnary) encUnary)
(hSrc : ComputableTidilyInPolyTime (fun q : ((A×ℕ)×ℕ)×ℕ => src q.1.1.1 q.1.1.2 q.1.2 q.2)
(encPair (encPair (encPair e encUnary) encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => allMemoryTierGates (t a) (low a) (z a) (o a) (src a))
e (encList gateEnc) := by
let ep := encPair e encUnary
have hA := fst e encUnary
have hJ := snd e encUnary
have hLv := memoryTierLevels_poly.comp hT
have hGs := tierBatchGates_polytime (A := A×ℕ) (e := ep)
(src := fun q => src q.1 q.2) hR (boundedMemoryTierWidth_poly (hT.comp hA) hJ) hJ
(hL.comp hA) (hZ.comp hA) (hO.comp hA) hSrc
have hPr := fst ep encUnary
have hName : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ =>
memoryTierWire (low p.1.1) (emitLevels (t p.1.1)) p.1.2 p.2) (encPair ep encUnary) encUnary :=
memoryTierWire_poly (hL.comp (hA.comp hPr)) (hLv.comp (hA.comp hPr))
(hJ.comp hPr) (snd ep encUnary)
have hMap : ComputableTidilyInPolyTime (fun q : A×ℕ =>
boundedMemoryTierGates (t q.1) (low q.1) (z q.1) (o q.1) (src q.1) q.2)
ep (encList gateEnc) :=
mapWithInput hGs (gateRename_poly (e:=ep)
(name:=fun p => memoryTierWire (low p.1) (emitLevels (t p.1)) p.2) hName)
have result := flatMapWithInput (f := fun a j =>
boundedMemoryTierGates (t a) (low a) (z a) (o a) (src a) j)
(range.comp hLv) hMap
convert result using 1
funext a
unfold allMemoryTierGates
apply List.flatMap_congr
intro j hj
rw [boundedMemoryTierGates,boundedMemoryTierWidth_eq (List.mem_range.mp hj),memoryTierGates]
end NativeTiers
end CNFEncComplexity.Robson
/- RobsonEmitBank -/
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)])
theorem emitLaneList_length (slots : List (ℕ×ℕ)) :
(emitLaneList slots).length = 6*slots.length := by
induction slots with
| nil => rfl
| cons s ss ih =>
simp only [emitLaneList,List.flatMap_cons,List.length_append,List.length_cons]
have ht : (List.flatMap (fun r => [(s,r,false),(s,r,true)]) (List.range 3)).length=6 := rfl
rw [ht,show (List.flatMap (fun s => List.flatMap (fun r => [(s,r,false),(s,r,true)]) (List.range 3))
ss).length = (emitLaneList ss).length from rfl,ih]
omega
theorem emitLaneList_members {xs : List (ℕ×ℕ)} {s : ℕ×ℕ} {i : ℕ} {k : Bool}
(h : (s,i,k) ∈ emitLaneList xs) : s∈xs ∧ i < 3 := by
obtain ⟨u,hu,ha⟩ := List.mem_flatMap.mp h
obtain ⟨b,hb,hc⟩ := List.mem_flatMap.mp ha
simp only [List.mem_cons,List.not_mem_nil,or_false,Prod.mk.injEq] at hc
rcases hc with ⟨rfl,rfl,rfl⟩|⟨rfl,rfl,rfl⟩
· exact ⟨hu,List.mem_range.mp hb⟩
· exact ⟨hu,List.mem_range.mp hb⟩
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
private theorem mapIndex_source {A B : Type} (l : List A) (f : A→B) (default : B) :
((List.range l.length).map (fun i => (l[i]?.map f).getD default)) = l.map f := by
apply List.ext_getElem
· simp
· intro i hi hj
have hi' : i < l.length := by simpa using hi
simp only [List.getElem_map,List.getElem_range,List.getElem?_eq_getElem hi',Option.map_some,Option.getD_some]
def compactSlotOptions (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
(List.range 3).map (slotCompactMemory a base n t (trieLevel t) s)
theorem compactSlotOptions_filter (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) :
(compactSlotOptions a base n t s).filterMap id =
slotCompactRows a base n t (trieLevel t) s := by
simp [compactSlotOptions,slotCompactRows,List.filterMap_map,Function.comp_def]
theorem emitBank_exact (a : Assignment) (base region n t j z o : ℕ) (slots : List (ℕ×ℕ))
(hz : a z=false) (ho : a o=true)
(hWidth : ∀ s ∈ slots, ∀ r < 3, (emitFlags region t s r).valid (emitInputs base n t s r) a)
(hCore : GateSat a (emitTierGateList base region n t j z slots)) :
rawMemoryRows a (2^j) (6*slots.length) (emitSource base region n t j z o slots) =
slots.flatMap (fun s => (compactSlotOptions a base n t s).flatMap (emitTier j)) := by
let ds := emitLaneList slots
let decode := fun p => laneRecord a (2^j) 0 (emitLaneKey base region n t j z o p)
have hLen : ds.length = 6*slots.length := emitLaneList_length slots
have he : rawMemoryRows a (2^j) (6*slots.length) (emitSource base region n t j z o slots) =
ds.map decode := by
unfold rawMemoryRows
rw [← hLen]
have hh : ∀ i : ℕ, laneRecord a (2^j) 0 (emitSource base region n t j z o slots i) =
((ds[i]?).map decode).getD none := by
intro i
unfold emitSource
change laneRecord a (2^j) 0 (match ds[i]? with
| none => fun _ => z | some p => emitLaneKey base region n t j z o p) = _
cases ds[i]? <;> simp [laneRecord,laneActive,hz,decode]
simp_rw [hh]
exact mapIndex_source ds decode _
rw [he]
unfold ds emitLaneList
rw [List.map_flatMap]
apply List.flatMap_congr
intro s hs
rw [List.map_flatMap,compactSlotOptions,List.flatMap_map]
apply List.flatMap_congr
intro r hr
have hr' := List.mem_range.mp hr
have hG : GateSat a (emitOne base region n t j z s r) := by
intro g hg
exact hCore g (List.mem_flatMap.mpr ⟨s,hs,List.mem_flatMap.mpr ⟨r,hr,hg⟩⟩)
have hql := EmitInput.coreGates_sound (emitInputs base n t s r) (emitFlags region t s r) a j z o
(emitBlockBase region t j s r) hz ho (hWidth s hs r hr') hG
simp only [List.map_cons,List.map_nil,Function.comp_apply]
rw [← emitInputs_eq a base n t s r]
exact hql
end CNFEncComplexity.Robson
/- RobsonMemoryEmitFrame -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- Install local assignments in separate, equally sized scratch intervals. -/
theorem emitBank_assembleBlocks {I : Type} (a : Assignment) (base top stride count : ℕ)
(index : I → ℕ) (hi : Function.Injective index) (hc : ∀ k, index k < count)
(ht : base+count*stride ≤ top) (gates : I → List Gate)
(frame : ∀ k, GateFrame (gates k) base
(base+index k*stride) (base+index k*stride+stride))
(extend : ∀ k, ∃ b, Keeps a b (base+index k*stride) (base+index k*stride+stride) ∧
GateSat b (gates k)) :
∃ b, Keeps a b base top ∧ ∀ k, GateSat b (gates k) := by
classical
choose witness hw hs using extend
let lower : I → ℕ := fun k => base+index k*stride
let upper : I → ℕ := fun k => lower k+stride
have hordered (k k' : I) (h : index k < index k') : upper k ≤ lower k' := by
have hm := Nat.mul_le_mul_right stride (Nat.succ_le_of_lt h)
rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
unfold upper lower
omega
have hbounds (k : I) : base ≤ lower k ∧ upper k ≤ top := by
refine ⟨Nat.le_add_right ..,?_⟩
have hm := Nat.mul_le_mul_right stride (Nat.succ_le_of_lt (hc k))
rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
exact (show upper k ≤ base+count*stride by
unfold upper lower
omega).trans ht
let covers (i : ℕ) (k : I) : Prop := lower k ≤ i ∧ i < upper k
have hunique {i : ℕ} {k k' : I} (hk : covers i k) (hk' : covers i k') : k=k' := by
apply hi
rcases lt_trichotomy (index k) (index k') with h|h|h
· exact False.elim (Nat.not_lt_of_ge ((hordered k k' h).trans hk'.1) hk.2)
· exact h
· exact False.elim (Nat.not_lt_of_ge ((hordered k' k h).trans hk.1) hk'.2)
let b : Assignment := fun i => if h : ∃ k, covers i k then witness h.choose i else a i
have hkeep : Keeps a b base top := by
intro i hi
have hnone : ¬∃ k, covers i k := by
rintro ⟨k,hk⟩
have ⟨hl,hu⟩ := hbounds k
have ⟨hki,hik⟩ := hk
omega
simp [b,hnone]
refine ⟨b,hkeep,fun k => (hs k).congr_framed (frame k) ?_⟩
intro i hi
rcases hi with hi|hi
· exact (hw k i (.inl (hi.trans_le (hbounds k).1))).trans (hkeep i (.inl hi)).symm
· have hEx : ∃ j, covers i j := ⟨k,hi⟩
have heq : hEx.choose = k := hunique hEx.choose_spec hi
simp [b,hEx,heq]
theorem emitWidthCircuit_frame (common lo w : ℕ) (key : ℕ → ℕ)
(hkey : ∀ i < w, key i < common) :
GateFrame (widthCircuit lo w key) common lo (lo+w+1) := by
intro g hg i hi
rcases List.mem_cons.mp hg with rfl|hg
· simp only [RobsonCNF.Gate.names,List.mem_singleton] at hi
subst i
exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩
· obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
have hj' := List.mem_range.mp hj
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hi
rcases hi with rfl|rfl|rfl
· exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩
· exact .inl (hkey _ hj')
· exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩
theorem emitNormalizeLabel_lt {base t region : ℕ} (n : ℕ)
(hregion : normalizeAfter base t ≤ region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r f : ℕ} (hr : r < 3) (hf : f < 3) {i : ℕ} (hi : i < normalizeWidth (trieLevel t) s) :
(normalizeSlotWires base n t (trieLevel t) s r f).label i < region := by
let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
exact (normalizeWordFrame_label base n t (trieLevel t) s r f hs i hi).2.trans_le
((normalizeKeyBase_range base t k).2.trans hregion)
abbrev EmitWidthBlock (t : ℕ) := {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3
theorem emitWidthLayout_frame {base region n t : ℕ} (hregion : normalizeAfter base t ≤ region) :
GateFrame (emitWidthLayoutGates base region n t) region region (emitFlagTop region t) := by
intro g hg i hi
obtain ⟨s,hs,r,hr,f,hf,hg⟩ := by
simpa only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range] using hg
have hb := emitFlagBlock_bounds (base:=region) hs hr hf
have hwidth := emitFlagWidth_bound hs
have hW := emitWidthCircuit_frame region (emitFlagBase region t s r f)
(normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label
(fun _ hi => emitNormalizeLabel_lt n hregion hs hr hf hi)
exact (hW.mono le_rfl hb.1 (by omega)) g hg i hi
theorem emitWidthLayout_extend {base region n t : ℕ} (a : Assignment)
(hregion : normalizeAfter base t ≤ region) :
∃ b, Keeps a b region (emitFlagTop region t) ∧ GateSat b (emitWidthLayoutGates base region n t) := by
let index : EmitWidthBlock t → ℕ := fun ⟨s,r,f⟩ => emitFlagIndex t s r f
let gates : EmitWidthBlock t → List Gate := fun ⟨s,r,f⟩ => emitWidthGates base region n t s r f
have hu : Function.Injective index := by
intro ⟨s,r,f⟩ ⟨s',r',f'⟩ h
obtain ⟨h₁,h₂,h₃⟩ := emitFlagIndex_injective s.property s'.property
r.isLt r'.isLt f.isLt f'.isLt h
exact Prod.ext (Subtype.ext h₁) (Prod.ext (Fin.ext h₂) (Fin.ext h₃))
have hc (k : EmitWidthBlock t) : index k < 9*emitSlotSpan t := by
rcases k with ⟨s,r,f⟩
have h := emitSlotIndex_bound s.property
have hr := r.isLt
have hf := f.isLt
change emitFlagIndex t s r f < _
unfold emitFlagIndex
omega
have frame (k : EmitWidthBlock t) :
GateFrame (gates k) region (region+index k*emitFlagStride t)
(region+index k*emitFlagStride t+emitFlagStride t) := by
rcases k with ⟨s,r,f⟩
have hwidth := emitFlagWidth_bound s.property
exact (emitWidthCircuit_frame region (emitFlagBase region t s r f)
(normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label
(fun _ hi => emitNormalizeLabel_lt n hregion s.property r.isLt f.isLt hi)).mono
le_rfl le_rfl (by
change emitFlagBase region t s r f+normalizeWidth (trieLevel t) s+1 ≤
emitFlagBase region t s r f+emitFlagStride t
omega)
have extend (k : EmitWidthBlock t) :
∃ b, Keeps a b (region+index k*emitFlagStride t)
(region+index k*emitFlagStride t+emitFlagStride t) ∧ GateSat b (gates k) := by
rcases k with ⟨s,r,f⟩
have hbounds := emitFlagBlock_bounds (base:=region) s.property r.isLt f.isLt
have hwidth := emitFlagWidth_bound s.property
obtain ⟨b,hb,hg⟩ := widthCircuit_extends_interval (emitFlagBase region t s r f)
(normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label a
(fun _ hi => (emitNormalizeLabel_lt n hregion s.property r.isLt f.isLt hi).trans_le hbounds.1)
refine ⟨b,fun i hi => hb i ?_,hg⟩
change i < emitFlagBase region t s r f ∨ emitFlagBase region t s r f+emitFlagStride t ≤ i at hi
omega
obtain ⟨b,hk,hb⟩ := emitBank_assembleBlocks a region (emitFlagTop region t) (emitFlagStride t)
(9*emitSlotSpan t) index hu hc (by rfl) gates frame extend
refine ⟨b,hk,fun g hg => ?_⟩
obtain ⟨s,hs,r,hr,f,hf,hg⟩ := by
simpa only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range] using hg
exact hb (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩) g hg
theorem emitWidthLayout_valid {a : Assignment} {base region n t : ℕ}
(h : GateSat a (emitWidthLayoutGates base region n t)) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r : ℕ} (hr : r < 3) :
(emitFlags region t s r).valid (emitInputs base n t s r) a := by
have hG (f : ℕ) (hf : f < 3) : GateSat a (emitWidthGates base region n t s r f) := by
intro g hg
apply h g
simp only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range]
exact ⟨s,hs,r,hr,f,hf,hg⟩
exact ⟨hG 0 (by decide),hG 1 (by decide),hG 2 (by decide)⟩
theorem emitFlagQuery_lt {region t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r f : ℕ} (hr : r < 3) (hf : f < 3) (k : ℕ) :
tierAbove (normalizeWidth (trieLevel t) s) (emitFlagBase region t s r f) k < emitFlagTop region t := by
have hp := emitFlagWidth_bound hs
have hb := (emitFlagBlock_bounds (base:=region) hs hr hf).2
have hk := min_le_left (normalizeWidth (trieLevel t) s) k
unfold tierAbove widthFlagWire
omega
theorem emitBlock_bounds {region t j r : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
(hj : j < emitLevels t) (hr : r < 3) :
emitFlagTop region t ≤ emitBlockBase region t j s r ∧
emitBlockBase region t j s r+emitBlockStride t ≤ emitBlockTop region t := by
have hm := Nat.mul_le_mul_right (emitBlockStride t)
(Nat.succ_le_of_lt (emitBlockIndex_bound hs hj hr))
rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
unfold emitBlockBase emitBlockTop
omega
theorem EmitInput.coreGates_frame (u : EmitInput) (f : EmitFlags) (j z common b : ℕ)
(_hc : common ≤ b) (hz : z < common) (hl : u.live < common) (hw : u.writes < common)
(ha : ∀ k, tierAbove u.width f.addr k < common)
(hv : ∀ k, tierAbove u.width f.value k < common)
(ho : ∀ k, tierAbove u.width f.old k < common)
(ho' : ∀ i < u.width, u.old i < common) (hv' : ∀ i < u.width, u.value i < common) :
GateFrame (u.coreGates f j z b) common b (b+16+2^j) := by
have hp := Nat.two_pow_pos j
have frame (d x y : ℕ) (hd : d ≤ 4)
(hx : ∀ k, tierAbove u.width x k < common) (hy : ∀ k, tierAbove u.width y k < common) :
GateFrame (tierTestGates j x y u.width (b+d)) common b (b+16+2^j) := by
intro g hg r hr
rcases tierTestGates_names j u.width x y (b+d) g hg r hr with hh|⟨k,rfl⟩|⟨k,rfl⟩
· exact .inr ⟨by omega,by omega⟩
· exact .inl (hx k)
· exact .inl (hy k)
have htest1 := frame 0 f.addr f.old (by decide) ha ho
have htest2 := frame 4 f.addr f.value (by decide) ha hv
let src := tierTestOutput j b
let dst := tierTestOutput j (b+4)
have hsrc : b ≤ src ∧ src < b+8 := by unfold src tierTestOutput; split <;> omega
have hdst : b ≤ dst ∧ dst < b+8 := by unfold dst tierTestOutput; split <;> omega
have hctrl : GateFrame (emissionControl (b+8) u.live u.writes src dst) common b (b+16+2^j) := by
intro g hg r hr
simp only [emissionControl,List.mem_cons,List.not_mem_nil,or_false] at hg
rcases hg with rfl|rfl|rfl|rfl|rfl|rfl|rfl|rfl <;>
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr <;> omega
have padded (f : ℕ→ℕ) (h : ∀ i < u.width, f i < common) (i : ℕ) :
paddedKey u.width z f i < common := by
unfold paddedKey
split
· exact h _ ‹_›
· exact hz
have hmux : GateFrame
(emissionMux (b+8) (2^j) u.writes (paddedKey u.width z u.old) (paddedKey u.width z u.value))
common b (b+16+2^j) := by
intro g hg r hr
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hi' := List.mem_range.mp hi
have hol := padded u.old ho' i
have hvl := padded u.value hv' i
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
omega
simp only [EmitInput.coreGates,GateFrame.append]
exact ⟨⟨⟨by simpa only [Nat.add_zero] using htest1,htest2⟩,hctrl⟩,hmux⟩
theorem emitInputs_flags_lt {base n t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r : ℕ} (hr : r < 3) :
(emitInputs base n t s r).live < sharedLimit n t ∧
(emitInputs base n t s r).writes < sharedLimit n t := by
rcases s with ⟨s,k⟩
obtain ⟨hs,hk,_⟩ := layout_mem.mp hs
exact ⟨port_lt_shared hs hk (by omega) (Nat.two_pow_pos _),
port_lt_shared hs hk (by omega) (Nat.two_pow_pos _)⟩
theorem emitInputs_label_lt {base region n t : ℕ}
(h : normalizeAfter base t ≤ region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r : ℕ} (hr : r < 3) :
let u := emitInputs base n t s r
(∀ i < u.width, u.address i < region) ∧ (∀ i < u.width, u.value i < region) ∧
(∀ i < u.width, u.old i < region) :=
⟨fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 0 < 3) hi,
fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 1 < 3) hi,
fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 2 < 3) hi⟩
theorem emitOne_local_frame {base region n t j z : ℕ}
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r : ℕ} (hr : r < 3) (hj : j < emitLevels t) :
GateFrame (emitOne base region n t j z s r) (emitFlagTop region t)
(emitBlockBase region t j s r) (emitBlockBase region t j s r+emitBlockStride t) := by
have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
obtain ⟨hl,hw⟩ := emitInputs_flags_lt (base:=base) (n:=n) hs hr
obtain ⟨ha,hv,ho⟩ := emitInputs_label_lt (n:=n) hreg hs hr
have hb := emitBlock_bounds (region:=region) hs hj hr
have h := EmitInput.coreGates_frame (emitInputs base n t s r) (emitFlags region t s r)
j z (emitFlagTop region t) (emitBlockBase region t j s r) hb.1 (hz.trans_le hreg')
((hl.trans_le hshared).trans_le hreg') ((hw.trans_le hshared).trans_le hreg')
(emitFlagQuery_lt (region:=region) hs hr (by decide : 0 < 3))
(emitFlagQuery_lt (region:=region) hs hr (by decide : 1 < 3))
(emitFlagQuery_lt (region:=region) hs hr (by decide : 2 < 3))
(fun i hi => (ho i hi).trans_le hreg') (fun i hi => (hv i hi).trans_le hreg')
exact h.mono le_rfl le_rfl (by have q := emitBlockWidth_bound hj; omega)
theorem emitOne_local_extend {base region n t j z : ℕ} (a : Assignment)
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
{r : ℕ} (hr : r < 3) (hj : j < emitLevels t) :
∃ b, Keeps a b (emitBlockBase region t j s r)
(emitBlockBase region t j s r+emitBlockStride t) ∧ GateSat b (emitOne base region n t j z s r) := by
have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
obtain ⟨hl,hw⟩ := emitInputs_flags_lt (base:=base) (n:=n) hs hr
obtain ⟨ha,hv,ho⟩ := emitInputs_label_lt (n:=n) hreg hs hr
have hb := emitBlock_bounds (region:=region) hs hj hr
have hp := hreg'.trans hb.1
let u := emitInputs base n t s r
let f := emitFlags region t s r
obtain ⟨b,hk,hg⟩ := u.coreGates_extend f a j z (emitBlockBase region t j s r)
((hl.trans_le hshared).trans_le hp) ((hw.trans_le hshared).trans_le hp) (hz.trans_le hp)
(fun i hi => (ho i hi).trans_le hp) (fun i hi => (hv i hi).trans_le hp)
(fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 0 < 3) i).trans_le hb.1)
(fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 1 < 3) i).trans_le hb.1)
(fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 2 < 3) i).trans_le hb.1)
have hlen := emitBlockWidth_bound hj
exact ⟨b,fun i hi => hk i (by omega),hg⟩
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)
theorem emitCoreLayout_frame {base region n t z : ℕ}
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
GateFrame (emitCoreLayoutGates base region n t z slots) (emitFlagTop region t)
(emitFlagTop region t) (emitBlockTop region t) := by
intro g hg i hi
obtain ⟨j,hj,s,hs,r,hr,hg⟩ := by
simpa only [emitCoreLayoutGates,emitTierGateList,List.mem_flatMap,List.mem_range] using hg
have hs' := hslots j hs
obtain ⟨hl,hh⟩ := emitBlock_bounds (region:=region) hs' hj hr
exact ((emitOne_local_frame hreg hshared hz hs' hr hj).mono le_rfl hl hh) g hg i hi
theorem emitCoreLayout_extend {base region n t z : ℕ} (a : Assignment)
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
∃ b, Keeps a b (emitFlagTop region t) (emitBlockTop region t) ∧
GateSat b (emitCoreLayoutGates base region n t z slots) := by
let index : EmitCoreBlock t → ℕ := fun ⟨j,s,r⟩ => emitBlockIndex t j s r
let gates : EmitCoreBlock t → List Gate := fun ⟨j,s,r⟩ => emitOne base region n t j z s r
have hu : Function.Injective index := by
intro ⟨j,s,r⟩ ⟨j',s',r'⟩ h
obtain ⟨h₁,h₂,h₃⟩ := emitBlockIndex_injective s.property s'.property r.isLt r'.isLt h
exact Prod.ext (Fin.ext h₁) (Prod.ext (Subtype.ext h₂) (Fin.ext h₃))
have hc (k : EmitCoreBlock t) : index k < 3*(emitLevels t*emitSlotSpan t) := by
rcases k with ⟨j,s,r⟩
exact emitBlockIndex_bound s.property j.isLt r.isLt
have frame (k : EmitCoreBlock t) :
GateFrame (gates k) (emitFlagTop region t)
(emitFlagTop region t+index k*emitBlockStride t)
(emitFlagTop region t+index k*emitBlockStride t+emitBlockStride t) := by
rcases k with ⟨j,s,r⟩
exact emitOne_local_frame hreg hshared hz s.property r.isLt j.isLt
have extend (k : EmitCoreBlock t) :
∃ b, Keeps a b (emitFlagTop region t+index k*emitBlockStride t)
(emitFlagTop region t+index k*emitBlockStride t+emitBlockStride t) ∧ GateSat b (gates k) := by
rcases k with ⟨j,s,r⟩
exact emitOne_local_extend a hreg hshared hz s.property r.isLt j.isLt
obtain ⟨b,hk,hb⟩ := emitBank_assembleBlocks a (emitFlagTop region t) (emitBlockTop region t)
(emitBlockStride t) (3*(emitLevels t*emitSlotSpan t)) index hu hc (by rfl) gates frame extend
refine ⟨b,hk,fun g hg => ?_⟩
obtain ⟨j,hj,s,hs,r,hr,hg⟩ := by
simpa only [emitCoreLayoutGates,emitTierGateList,List.mem_flatMap,List.mem_range] using hg
exact hb (⟨j,hj⟩,⟨s,hslots j hs⟩,⟨r,hr⟩) g hg
theorem emitCoreLayout_tier {a : Assignment} {base region n t z j : ℕ}
{slots : ℕ → List (ℕ×ℕ)} (h : GateSat a (emitCoreLayoutGates base region n t z slots))
(hj : j < emitLevels t) : GateSat a (emitTierGateList base region n t j z (slots j)) :=
fun g hg => h g (List.mem_flatMap.mpr ⟨j,List.mem_range.mpr hj,hg⟩)
theorem emissionRow_key_lt {w z active beforeFlag afterFlag bound : ℕ}
{addr before after : ℕ → ℕ} (hz : z < bound) (hact : active < bound)
(hb : beforeFlag < bound) (ha : afterFlag < bound)
(haddr : ∀ i < w, addr i < bound) (hbv : ∀ i < w, before i < bound)
(hav : ∀ i < w, after i < bound) (i : ℕ) :
emissionRow w z active beforeFlag afterFlag addr before after i < bound := by
unfold emissionRow
split
· exact hact
split
· exact haddr _ (by omega)
split
· exact hb
split
· exact hbv _ (by omega)
split
· exact ha
split
· exact hav _ (by omega)
· exact hz
theorem emitSource_lt {base region n t j z o : ℕ}
(hregion : normalizeAfter base t ≤ region)
(hz : z < region) (ho : o < region) (hj : j < emitLevels t)
{slots : List (ℕ×ℕ)} (hslots : slots ⊆ layoutSlots t) (lane bit : ℕ) :
emitSource base region n t j z o slots lane bit < emitBlockTop region t := by
have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
have hreg'' : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
have htop := hreg'.trans hreg''
unfold emitSource
cases hm : (emitLaneList slots)[lane]? with
| none => exact hz.trans_le htop
| some p =>
obtain ⟨s,r,f⟩ := p
obtain ⟨hs,hr⟩ := emitLaneList_members (List.mem_of_getElem? hm)
have hs' := hslots hs
let u := emitInputs base n t s r
let b := emitBlockBase region t j s r
have hb : b+emitBlockStride t ≤ emitBlockTop region t := (emitBlock_bounds hs' hj hr).2
have hw := emitBlockWidth_bound hj
have hp := Nat.two_pow_pos j
obtain ⟨had,hval,hold⟩ := emitInputs_label_lt (n:=n) hregion hs' hr
have padded (key : ℕ → ℕ) (h : ∀ i < u.width, key i < region) (i : ℕ) :
paddedKey u.width z key i < emitBlockTop region t := by
unfold paddedKey
split
· exact (h i ‹_›).trans_le htop
· exact hz.trans_le htop
cases f
· change emitFirstRow u (2^j) z o (b+8) bit < emitBlockTop region t
apply emissionRow_key_lt (hz.trans_le htop) (by omega) (ho.trans_le htop) (by omega)
(fun i _ => padded _ had i) (fun i hi => by omega) (fun i _ => padded _ hval i)
· change emitSecondRow u (2^j) z o (b+8) bit < emitBlockTop region t
apply emissionRow_key_lt (hz.trans_le htop) (by omega) (hz.trans_le htop) (ho.trans_le htop)
(fun i _ => padded _ had i) (fun _ _ => hz.trans_le htop) (fun i _ => padded _ hval i)
def emitAllGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
emitWidthLayoutGates base region n t ++ emitCoreLayoutGates base region n t z slots
theorem emitAll_frame {base region n t z : ℕ}
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
GateFrame (emitAllGates base region n t z slots) region region (emitBlockTop region t) := by
have hp : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
have hq : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
apply GateFrame.append.mpr
refine ⟨(emitWidthLayout_frame hreg).mono le_rfl le_rfl hq,?_⟩
intro g hg i hi
rcases emitCoreLayout_frame hreg hshared hz slots hslots g hg i hi with low|⟨hl,hh⟩
· by_cases ht : i < region
· exact .inl ht
· exact .inr ⟨by omega,low.trans_le hq⟩
· exact .inr ⟨hp.trans hl,hh⟩
theorem emitAll_extend {base region n t z : ℕ} (a : Assignment)
(hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
(hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
∃ b, Keeps a b region (emitBlockTop region t) ∧ GateSat b (emitAllGates base region n t z slots) := by
have hp : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
have hq : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
obtain ⟨b,hk,hWidth⟩ := emitWidthLayout_extend (n:=n) a hreg
obtain ⟨c,hk',hCore⟩ := emitCoreLayout_extend b hreg hshared hz slots hslots
refine ⟨c,hk.trans hk' hp hq,GateSat.append.mpr ⟨?_,hCore⟩⟩
apply hWidth.congr_framed (emitWidthLayout_frame hreg)
intro i hi
exact (hk' i (.inl (by omega))).symm
theorem emitAll_exact {a : Assignment} {base region n t z o j : ℕ} {slots : ℕ → List (ℕ×ℕ)}
(h : GateSat a (emitAllGates base region n t z slots))
(hslots : ∀ j, slots j ⊆ layoutSlots t) (hj : j < emitLevels t) (hz : a z = false) (ho : a o = true) :
rawMemoryRows a (2^j) (6*(slots j).length) (emitSource base region n t j z o (slots j)) =
(slots j).flatMap (fun s => (compactSlotOptions a base n t s).flatMap (emitTier j)) :=
emitBank_exact a base region n t j z o (slots j) hz ho
(fun s hs r hr => emitWidthLayout_valid (GateSat.append.mp h).1 (hslots j hs) hr)
(emitCoreLayout_tier (GateSat.append.mp h).2 hj)
private theorem emit_flatMap_length_uniform {I G : Type} (gates : I → List G) (xs : List I) (bound : ℕ)
(h : ∀ i ∈ xs, (gates i).length ≤ bound) : (xs.flatMap gates).length ≤ xs.length*bound := by
induction xs with
| nil => simp
| cons i is ih =>
have hi := h i (.head _)
have hh := ih (fun j hj => h j (.tail _ hj))
simp only [List.flatMap_cons,List.length_cons,List.length_append,Nat.add_mul,Nat.one_mul]
omega
theorem emitTierGateList_length (base region n t j z : ℕ) (slots : List (ℕ×ℕ)) :
(emitTierGateList base region n t j z slots).length ≤ 51*(slots.length*2^j) := by
have hl (s : ℕ×ℕ) : ((List.range 3).flatMap (emitOne base region n t j z s)).length ≤ 51*2^j := by
have h := emit_flatMap_length_uniform (emitOne base region n t j z s) (List.range 3)
(17*2^j) (fun r _ => EmitInput.coreGates_length _ _ _ _ _)
simpa only [List.length_range,← Nat.mul_assoc] using h
have h := emit_flatMap_length_uniform (fun s => (List.range 3).flatMap (emitOne base region n t j z s))
slots (51*2^j) (fun s _ => hl s)
unfold emitTierGateList
exact h.trans_eq (by ac_rfl)
theorem emitCoreLayout_length (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ))
(hb : ∀ j < emitLevels t, (slots j).length*2^j ≤ 8*layoutHorizon t) :
(emitCoreLayoutGates base region n t z slots).length ≤ 408*(layoutHorizon t*emitLevels t) := by
have h := emit_flatMap_length_uniform (fun j => emitTierGateList base region n t j z (slots j))
(List.range (emitLevels t)) (408*layoutHorizon t)
(fun j hj => (emitTierGateList_length base region n t j z (slots j)).trans
(by simpa only [← Nat.mul_assoc] using Nat.mul_le_mul_left 51 (hb j (List.mem_range.mp hj))))
unfold emitCoreLayoutGates
rw [List.length_range] at h
exact h.trans_eq (by ac_rfl)
theorem emitWidthLayout_length (base region n t : ℕ) :
(emitWidthLayoutGates base region n t).length ≤
27*((layoutSlots t).map fun s => 2^s.2).sum := by
let gates := fun s => (List.range 3).flatMap fun r =>
(List.range 3).flatMap (emitWidthGates base region n t s r)
have hg (s : ℕ×ℕ) : (gates s).length ≤ 27*2^s.2 := by
have hr (r : ℕ) : ((List.range 3).flatMap (emitWidthGates base region n t s r)).length ≤ 9*2^s.2 := by
have h := emit_flatMap_length_uniform (emitWidthGates base region n t s r) (List.range 3)
(3*2^s.2) (fun f _ => emitWidthGates_length base region n t s r f)
simpa only [List.length_range,← Nat.mul_assoc] using h
have h := emit_flatMap_length_uniform (fun r => (List.range 3).flatMap (emitWidthGates base region n t s r))
(List.range 3) (9*2^s.2) (fun r _ => hr r)
simpa only [List.length_range,← Nat.mul_assoc,gates] using h
have main (xs : List (ℕ×ℕ)) :
(xs.flatMap gates).length ≤ 27*(xs.map fun s => 2^s.2).sum := by
induction xs with
| nil => simp
| cons s ss ih =>
have hs := hg s
simp only [List.flatMap_cons,List.map_cons,List.sum_cons,List.length_append,Nat.mul_add]
omega
exact main (layoutSlots t)
end CNFEncComplexity.Robson
/- RobsonMemEmitLocal -/
namespace CNFEncComplexity.Robson
open CookLevin
private theorem memoryEmitAtTierAppend (j : ℕ) (us vs : List TierRecord) :
atTier j (us++vs) = atTier j us ++ atTier j vs := by
simp [atTier,List.filter_append]
private theorem memoryEmitTieredObsAppend (us vs : List ObservedAccess) :
tieredObservations bitTier (us++vs) = tieredObservations bitTier us ++ tieredObservations bitTier vs := by
simp [tieredObservations,List.flatMap_append]
def emitSlotTier (j : ℕ) (slots : List (Option ObservedAccess)) : List (Option LocalRecord) :=
slots.flatMap (emitTier j)
@[simp] theorem emitSlotTier_length (j : ℕ) (slots : List (Option ObservedAccess)) :
(emitSlotTier j slots).length = 2*slots.length := by
induction slots with
| nil => rfl
| cons s ss ih =>
rw [emitSlotTier,List.flatMap_cons,List.length_append,emitTier_length,
show ss.flatMap (emitTier j) = emitSlotTier j ss from rfl,ih,List.length_cons]
omega
theorem emitSlotTier_exact (j : ℕ) (slots : List (Option ObservedAccess)) :
(emitSlotTier j slots).filterMap id =
atTier j (tieredObservations bitTier (slots.filterMap id)) := by
induction slots with
| nil => rfl
| cons s ss ih =>
rw [emitSlotTier,List.flatMap_cons,List.filterMap_append,emitTier_exact,
show ss.flatMap (emitTier j) = emitSlotTier j ss from rfl,ih]
cases s with
| none => simp [tieredObservations,atTier]
| some r =>
simp only [Option.toList_some,List.flatMap_cons,List.flatMap_nil,List.append_nil,List.filterMap_cons,
id_eq]
exact (memoryEmitAtTierAppend j _ _).symm
def memoryEmitLanes (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
List (Option LocalRecord) :=
(memoryTierSlots t j).flatMap fun s => emitSlotTier j (packed s)
theorem memoryEmitLanes_length (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess))
(hb : ∀ s ∈ layoutSlots t, (packed s).length = 3) :
(memoryEmitLanes t j packed).length = memoryTierRows t j := by
have hLen (xs : List (ℕ×ℕ)) (h : ∀ s ∈ xs, s ∈ layoutSlots t) :
(xs.flatMap fun s => emitSlotTier j (packed s)).length = 6*xs.length := by
induction xs with
| nil => rfl
| cons s ss ih =>
rw [List.flatMap_cons,List.length_append,emitSlotTier_length,hb _ (h _ (by simp)),
ih (fun s hs => h s (List.mem_cons_of_mem _ hs)),List.length_cons]
omega
exact hLen _ (fun s hs => (List.mem_filter.mp hs).1)
theorem memoryEmitLanes_projection (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
(memoryEmitLanes t j packed).filterMap id =
((memoryTierSlots t j).flatMap fun s =>
atTier j (tieredObservations bitTier ((packed s).filterMap id))) := by
unfold memoryEmitLanes
induction memoryTierSlots t j with
| nil => rfl
| cons s ss ih =>
rw [List.flatMap_cons,List.filterMap_append,emitSlotTier_exact,ih,List.flatMap_cons]
theorem memoryEmitLanes_sameProjection {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
(packed : (ℕ×ℕ) → List (Option ObservedAccess))
(hb : ∀ s ∈ layoutSlots t, (packed s).length = 3)
(hx : PackedSlots α n t b dict (fun s => (packed s).filterMap id)) (j : ℕ) :
(memoryEmitLanes t j packed).length = (memoryTierLanes t j (fun s => (packed s).filterMap id)).length ∧
(memoryEmitLanes t j packed).filterMap id =
(memoryTierLanes t j (fun s => (packed s).filterMap id)).filterMap id := by
refine ⟨(memoryEmitLanes_length t j packed hb).trans (memoryTierLanes_length hx j).symm,?_⟩
rw [memoryEmitLanes_projection]
unfold memoryTierLanes
induction memoryTierSlots t j with
| nil => rfl
| cons s ss ih =>
rw [List.flatMap_cons,List.flatMap_cons,List.filterMap_append,← ih]
congr 1
unfold perSlotTierRows
rw [List.filterMap_append,List.filterMap_map]
have he : (List.replicate (6-(atTier j (tieredObservations bitTier ((packed s).filterMap id))).length)
(none : Option LocalRecord)).filterMap id = [] := by
apply List.filterMap_eq_nil_iff.mpr
intro a ha
exact List.eq_of_mem_replicate ha
simp [he]
theorem memoryEmitLanes_exact {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
(packed : (ℕ×ℕ) → List (Option ObservedAccess))
(hb : ∀ s ∈ layoutSlots t, (packed s).length = 3)
(hx : PackedSlots α n t b dict (fun s => (packed s).filterMap id))
(good : WordEdge.Interned dict) :
observedMemoryValid (fun _ => 0) (memoryStream α n t) ↔
∀ j < (b+1).size+1,
TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j) (memoryEmitLanes t j packed)
(fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
refine (memoryTierLanes_exact hx good).trans ?_
refine forall_congr' (fun j => forall_congr' (fun _ => ?_))
let ys := memoryTierLanes t j (fun s => (packed s).filterMap id)
let xs := memoryEmitLanes t j packed
have hp := memoryEmitLanes_sameProjection packed hb hx j
have hl : ys.length ≤ memoryGroupCap j*memoryGroupCount t j :=
(memoryTierLanes_length hx j).trans_le (memoryGroupCount_cap t j)
have hl' : xs.length ≤ memoryGroupCap j*memoryGroupCount t j := hp.1.trans_le hl
have hfits : ∀ r ∈ tieredObservations bitTier (packMemoryStream t (fun s => (packed s).filterMap id)),
TierRecordFits (b+1) r := by
intro r hr
obtain ⟨o,ho,hor⟩ := List.mem_flatMap.mp hr
obtain ⟨s,hs,ho⟩ := List.mem_flatMap.mp ho
obtain ⟨ha,hv,hold⟩ := hx.widths s hs o ho
have h := Nat.add_le_add_right (min_le_right (2^s.2) b) 1
exact tieredAccess_fits (ha.trans h) (hv.trans h) (hold.trans h) r hor
have hR : ∀ r ∈ ys.filterMap id, r.addr < memoryGroupCap j := by
rw [show ys.filterMap id = _ from memoryTierLanes_projection hx j]
exact atTier_address_bounded hfits
have hR' : ∀ r ∈ xs.filterMap id, r.addr < memoryGroupCap j := hp.2.symm ▸ hR
rw [tierBatchCertificate_iff _ _ _ _ hl hR (bitTier_initial_restricted j),
tierBatchCertificate_iff _ _ _ _ hl' hR' (bitTier_initial_restricted j),hp.2]
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).