Local Boolean relations for RAM tier updates
DefinitionCNFEncComplexity_RobsonMemoryTierRowGatescomplexity-theorysatisfiability
Bounds-aware width flags, row encoding and update gates for the optional chronological records of one RAM slot.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieSlots
import Definitions.Def_CNFEncComplexity_RobsonMemoryParameters
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonLocalTierGates -/
namespace CNFEncComplexity.Robson
open CookLevin
/-- Two fixed chronological lanes per raw observation. A write cancels its old
tier entry before it inserts its new one. When the tier stays the same, the first
lane is a single replacement. Inactive slots and irrelevant tiers emit nothing. -/
def emitTier (j : ℕ) : Option ObservedAccess → List (Option LocalRecord)
| none => [none,none]
| some r =>
let a := r.action.address
let v := r.action.value
let dest := bitTier a v = j
let src := bitTier a r.old = j
if r.action.writes then
[if src then some ⟨a,some r.old,if dest then some v else none⟩ else none,
if dest ∧ ¬src then some ⟨a,none,some v⟩ else none]
else [if dest then some ⟨a,some v,some v⟩ else none,none]
@[simp] theorem emitTier_length (j : ℕ) (o : Option ObservedAccess) :
(emitTier j o).length = 2 := by
cases o with
| none => rfl
| some r => cases e : r.action.writes <;> simp [emitTier,e]
theorem emitTier_exact (j : ℕ) (o : Option ObservedAccess) :
(emitTier j o).filterMap id =
atTier j (o.toList.flatMap (fun r => tieredAccess bitTier r.action r.old)) := by
cases o with
| none => rfl
| some r =>
let a := r.action.address
let v := r.action.value
have ht : ((bitTier a r.old,a) = (bitTier a v,a)) ↔ bitTier a r.old = bitTier a v := by simp
cases hw : r.action.writes
· by_cases hj : bitTier a v = j <;>
simp [emitTier,tieredAccess,hw,atTier,a,v,hj,localRecord]
· by_cases hSrc : bitTier a r.old = j <;> by_cases hDest : bitTier a v = j
· have same : bitTier a r.old = bitTier a v := hSrc.trans hDest.symm
simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,same,localRecord]
· have diff : bitTier a r.old ≠ bitTier a v := fun h => hDest (h.symm.trans hSrc)
simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,Ne.symm hDest,diff,localRecord]
· have diff : bitTier a r.old ≠ bitTier a v := fun h => hSrc (h.trans hDest)
simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,diff,localRecord]
· by_cases he : bitTier a r.old = bitTier a v <;>
simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,he,List.filter_cons]
open RobsonCNF
/-- The suffix query at an index beyond the word width reads the false sentinel. -/
def tierAbove (n base k : ℕ) : ℕ := widthFlagWire base (min n k)
theorem tierAbove_exact (a : Assignment) (n base : ℕ) (key : ℕ → ℕ) (k : ℕ)
(hg : ∀ g ∈ widthCircuit base n key, g.Holds a) :
a (tierAbove n base k) = decide (k < (wireValue a key n).size) := by
rw [tierAbove,widthCircuit_exact base n key a hg (min_le_left _ _)]
have h := Nat.size_le.mpr (wireValue_lt a key n)
by_cases hk : k ≤ n
· rw [min_eq_right hk]
· have h₁ : ¬ k < (wireValue a key n).size := by omega
rw [min_eq_left (by omega),decide_eq_false (show ¬ n < _ from by omega),decide_eq_false h₁]
/-- Once suffix flags have been made, deciding one tier takes a constant
number of gates, regardless of the original word widths. -/
def tierTestGates (j aBase vBase n out : ℕ) : List Gate :=
let aboveA := tierAbove n aBase
let aboveV := tierAbove n vBase
let hi := 2^j - 1
if j=0 then
[.disj out (aboveA hi) (aboveV hi), .inv (out+1) out]
else
let lo := 2^(j-1)-1
[.disj out (aboveA hi) (aboveV hi), .inv (out+1) out,
.disj (out+2) (aboveA lo) (aboveV lo), .conj (out+3) (out+1) (out+2)]
def tierTestOutput (j out : ℕ) : ℕ := if j=0 then out+1 else out+3
private theorem tier_size_zero (a v : ℕ) :
bitTier a v = 0 ↔ ¬ (0 < a.size ∨ 0 < v.size) := by
unfold bitTier
simp only [Nat.size_eq_zero,not_or,not_lt]
omega
private theorem tier_size_pos (a v j : ℕ) (hj : 0 < j) :
bitTier a v = j ↔ (2^(j-1)-1 < a.size ∨ 2^(j-1)-1 < v.size) ∧
¬(2^j-1 < a.size ∨ 2^j-1 < v.size) := by
unfold bitTier
have h0 : 0 < (2:ℕ)^j := Nat.two_pow_pos _
have h1 : 0 < (2:ℕ)^(j-1) := Nat.two_pow_pos _
have e : j-1+1=j := by omega
constructor
· intro h
have hLo := Nat.lt_size.mp (show j-1 < (max a.size v.size).size by omega)
have hHi := Nat.size_le.mp (show (max a.size v.size).size ≤ j from h.le)
omega
· rintro ⟨hLo,hHi⟩
have hl : j-1 < (max a.size v.size).size := Nat.lt_size.mpr (by omega)
have hh : (max a.size v.size).size ≤ j := Nat.size_le.mpr (by omega)
omega
theorem tierTestGates_exact (a : Assignment) (j aBase vBase n out : ℕ) (ka kv : ℕ → ℕ)
(ha : ∀ g ∈ widthCircuit aBase n ka,g.Holds a)
(hv : ∀ g ∈ widthCircuit vBase n kv,g.Holds a)
(hg : ∀ g ∈ tierTestGates j aBase vBase n out, g.Holds a) :
a (tierTestOutput j out) = decide (bitTier (wireValue a ka n) (wireValue a kv n) = j) := by
have ha' := fun k => tierAbove_exact a n aBase ka k ha
have hv' := fun k => tierAbove_exact a n vBase kv k hv
by_cases h0 : j = 0
· subst j
simp only [tierTestGates,if_true,tierTestOutput,pow_zero,Nat.sub_self, List.forall_mem_cons,
List.not_mem_nil,false_implies,implies_true,and_true,Gate.Holds] at hg ⊢
rw [hg.2,hg.1,ha',hv']
apply Bool.eq_iff_iff.mpr
simp [tier_size_zero]
· simp only [tierTestGates,tierTestOutput,if_neg h0,List.forall_mem_cons,List.not_mem_nil,
false_implies,implies_true,and_true,Gate.Holds] at hg ⊢
rw [hg.2.2.2,hg.2.1,hg.1,hg.2.2.1,ha',hv',ha',hv']
apply Bool.eq_iff_iff.mpr
simp [tier_size_pos _ _ _ (Nat.pos_of_ne_zero h0),and_comm]
theorem tierTestGates_length (j aBase vBase n out : ℕ) :
(tierTestGates j aBase vBase n out).length ≤ 4 := by
unfold tierTestGates
by_cases h : j=0 <;> simp [h]
/-- Output flag keys are packed in eight fresh positions. The only
data-dependent word in the result is the first lane's before value. -/
def emissionControl (base live writes src dst : ℕ) : List Gate :=
[.mux base writes src dst, .conj (base+1) live base, .inv (base+2) src,
.conj (base+3) writes dst, .conj (base+4) (base+2) (base+3),
.conj (base+5) live (base+4), .inv (base+6) writes,
.disj (base+7) (base+6) dst]
theorem emissionControl_exact (a : Assignment) (base live writes src dst : ℕ)
(hg : ∀ g ∈ emissionControl base live writes src dst, g.Holds a) :
a (base+1) = (a live && (if a writes then a src else a dst)) ∧
a (base+5) = (a live && (!a src && (a writes && a dst))) ∧
a (base+7) = (!a writes || a dst) := by
simp only [emissionControl,List.forall_mem_cons,List.not_mem_nil,false_implies,implies_true,
and_true,Gate.Holds] at hg
obtain ⟨h0,h1,h2,h3,h4,h5,h6,h7⟩ := hg
exact ⟨by rw [h1,h0],by rw [h5,h4,h2,h3],by rw [h7,h6]⟩
def emissionMux (base w writes : ℕ) (old value : ℕ → ℕ) : List Gate :=
(List.range w).map (fun i => .mux (base+8+i) writes (old i) (value i))
theorem emissionMux_exact (a : Assignment) (base w writes : ℕ) (old value : ℕ→ℕ)
(hg : ∀ g ∈ emissionMux base w writes old value, g.Holds a) :
wireValue a (fun i => base+8+i) w =
if a writes then wireValue a old w else wireValue a value w := by
cases he : a writes
· simp only [he,Bool.false_eq_true,if_false]
apply (wireValue_eq_iff _ _ _ _).2
intro i hi
have h := hg (.mux _ _ _ _) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
simpa [Gate.Holds,he] using h
· simp only [he,if_true]
apply (wireValue_eq_iff _ _ _ _).2
intro i hi
have h := hg (.mux _ _ _ _) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
simpa [Gate.Holds,he] using h
end CNFEncComplexity.Robson
/- RobsonEmitFormat -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem wireValue_take_of_fit (a : Assignment) (key : ℕ → ℕ) {n w : ℕ}
(hwn : w ≤ n) (hFit : wireValue a key n < 2^w) :
wireValue a key w = wireValue a key n := by
induction n generalizing w with
| zero =>
have e : w=0 := by omega
subst w
rfl
| succ n ih =>
by_cases e : w=n+1
· rw [e]
· have hSub : w ≤ n := by omega
have hN : (2:ℕ)^w ≤ 2^n := Nat.pow_le_pow_right (by decide) hSub
cases hBit : a (key n)
· have hE : wireValue a key (n+1) = wireValue a key n := by simp [wireValue,hBit]
rw [hE] at hFit ⊢
exact ih hSub hFit
· have hSum : wireValue a key (n+1) = wireValue a key n + 2^n := by
simp [wireValue,hBit]
rw [hSum] at hFit
omega
theorem wireValue_clip (a : Assignment) (key : ℕ → ℕ) (n w z : ℕ) (hz : a z=false)
(hfit : (wireValue a key n).size ≤ w) :
wireValue a (paddedKey n z key) w = wireValue a key n := by
rcases le_total n w with hn|hw
· exact wireValue_pad a n z key hz w hn
· have h : wireValue a (paddedKey n z key) w = wireValue a key w := by
apply wireValue_key_congr
intro i hi
simp [paddedKey,hi.trans_le hw]
exact h.trans (wireValue_take_of_fit a key hw (Nat.size_le.mp hfit))
structure EmitInput where
width : ℕ
live : ℕ
writes : ℕ
address : ℕ → ℕ
value : ℕ → ℕ
old : ℕ → ℕ
def EmitInput.read (u : EmitInput) (a : Assignment) : Option ObservedAccess :=
if a u.live then some ⟨⟨wireValue a u.address u.width,wireValue a u.value u.width,a u.writes⟩,
wireValue a u.old u.width⟩ else none
/-- The untagged row format consumed by the fixed stable sorter. -/
def emissionRow (w z active beforeFlag afterFlag : ℕ) (addr before after : ℕ → ℕ) (k : ℕ) : ℕ :=
if k=0 then active
else if k < 1+w then addr (k-1)
else if k=1+w then beforeFlag
else if k < 2+2*w then before (k-(2+w))
else if k=2+2*w then afterFlag
else if k < 3+3*w then after (k-(3+2*w)) else z
theorem emissionRow_read (a : Assignment) (w z active beforeFlag afterFlag : ℕ)
(addr before after : ℕ → ℕ) :
laneRecord a w 0 (emissionRow w z active beforeFlag afterFlag addr before after) =
(if a active then some ⟨wireValue a addr w,memoryOpt a beforeFlag before w,
memoryOpt a afterFlag after w⟩ else none) := by
have hAddr (i : ℕ) (hi : i < w) :
laneAddress 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = addr i := by
have h : 1+i < 1+w := by omega
change emissionRow w z active beforeFlag afterFlag addr before after (1+i) = _
unfold emissionRow
rw [if_neg (by omega),if_pos (by omega)]
simp
have hB (i : ℕ) (hi : i < w) :
laneBefore w 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = before i := by
unfold laneBefore
rw [show 1+0+w+1+i=2+w+i by omega]
unfold emissionRow
rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_pos (by omega)]
rw [show 2+w+i-(2+w)=i by omega]
have hF (i : ℕ) (hi : i < w) :
laneAfter w 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = after i := by
have he : 1+0+w+(1+w)+1+i = 3+2*w+i := by omega
unfold laneAfter
rw [he]
unfold emissionRow
rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),
if_pos (by omega),show 3+2*w+i-(3+2*w)=i by omega]
have hBF : laneBeforeFlag w 0 (emissionRow w z active beforeFlag afterFlag addr before after) = beforeFlag := by
unfold laneBeforeFlag emissionRow
rw [if_neg (by omega),if_neg (by omega),if_pos (by omega)]
have hAF : laneAfterFlag w 0 (emissionRow w z active beforeFlag afterFlag addr before after) = afterFlag := by
unfold laneAfterFlag emissionRow
rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),if_pos (by omega)]
have hA := wireValue_key_congr a (n:=w) hAddr
have hB' := wireValue_key_congr a (n:=w) hB
have hF' := wireValue_key_congr a (n:=w) hF
have hk : laneActive (emissionRow w z active beforeFlag afterFlag addr before after) = active := by
simp [laneActive,emissionRow]
unfold laneRecord
rw [hk,hA]
unfold memoryOpt
rw [hBF,hAF,hB',hF']
def emitFirstRow (u : EmitInput) (w z o base : ℕ) : ℕ → ℕ :=
emissionRow w z (base+1) o (base+7) (paddedKey u.width z u.address)
(fun i => base+8+i) (paddedKey u.width z u.value)
def emitSecondRow (u : EmitInput) (w z o base : ℕ) : ℕ → ℕ :=
emissionRow w z (base+5) z o (paddedKey u.width z u.address)
(fun _ => z) (paddedKey u.width z u.value)
theorem emitRows_exact (a : Assignment) (u : EmitInput) (j z o base s d : ℕ)
(hz : a z=false) (ho : a o=true)
(hs : a s = decide (bitTier (wireValue a u.address u.width) (wireValue a u.old u.width) = j))
(hd : a d = decide (bitTier (wireValue a u.address u.width) (wireValue a u.value u.width) = j))
(hc : ∀ g ∈ emissionControl base u.live u.writes s d, g.Holds a)
(hm : ∀ g ∈ emissionMux base (2^j) u.writes (paddedKey u.width z u.old)
(paddedKey u.width z u.value),g.Holds a) :
[laneRecord a (2^j) 0 (emitFirstRow u (2^j) z o base),
laneRecord a (2^j) 0 (emitSecondRow u (2^j) z o base)] = emitTier j (u.read a) := by
set addr := wireValue a u.address u.width with hA
set value := wireValue a u.value u.width with hV
set old := wireValue a u.old u.width with hO
have hAddr (h : bitTier addr value=j ∨ bitTier addr old=j) :
wireValue a (paddedKey u.width z u.address) (2^j) = addr := by
refine wireValue_clip _ _ _ _ _ hz ?_
rcases h with h|h
· exact (h ▸ (bitTier_width addr value).1).le
· exact (h ▸ (bitTier_width addr old).1).le
have hValue (h : bitTier addr value=j) :
wireValue a (paddedKey u.width z u.value) (2^j) = value :=
wireValue_clip _ _ _ _ _ hz (h ▸ (bitTier_width addr value).2.le)
have hOld (h : bitTier addr old=j) :
wireValue a (paddedKey u.width z u.old) (2^j) = old :=
wireValue_clip _ _ _ _ _ hz (h ▸ (bitTier_width addr old).2.le)
have hC := emissionControl_exact a base u.live u.writes s d hc
have hM := emissionMux_exact _ _ _ _ _ _ hm
simp only [emitFirstRow,emitSecondRow,emissionRow_read,memoryOpt,hz,ho,if_true,
Bool.false_eq_true,if_false,hC.1,hC.2.1,hC.2.2,hM,hs,hd,EmitInput.read,← hA,← hV,← hO]
cases hL : a u.live
· simp [hL,emitTier]
· cases hW : a u.writes
· by_cases hd : bitTier addr value=j
· simp [hL,hW,emitTier,hd,hAddr (.inl hd),hValue hd]
· simp [hL,hW,emitTier,hd]
· by_cases hs : bitTier addr old=j <;> by_cases hd : bitTier addr value=j
· simp [hL,hW,emitTier,hs,hd,hAddr (.inr hs),hValue hd,hOld hs]
· simp [hL,hW,emitTier,hs,hd,hAddr (.inr hs),hOld hs]
· simp [hL,hW,emitTier,hs,hd,hAddr (.inl hd),hValue hd]
· simp [hL,hW,emitTier,hs,hd]
end CNFEncComplexity.Robson
/- RobsonEmitWitness -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def tierFlagValues (a : Assignment) (j n xBase yBase : ℕ) : List Bool :=
let hi := a (tierAbove n xBase (2^j-1)) || a (tierAbove n yBase (2^j-1))
let lo := a (tierAbove n xBase (2^(j-1)-1)) || a (tierAbove n yBase (2^(j-1)-1))
[hi,!hi,lo,!hi && lo]
/-- Install a short list of private boolean outputs. -/
def fillBits (a : Assignment) (base : ℕ) (bits : List Bool) : Assignment := fun r =>
if base ≤ r ∧ r < base+bits.length then bits.getD (r-base) false else a r
theorem fillBits_at (a : Assignment) (base : ℕ) (bits : List Bool) {i : ℕ} (hi : i < bits.length) :
fillBits a base bits (base+i) = bits[i] := by
simp [fillBits,hi,List.getD]
theorem fillBits_frame (a : Assignment) (base : ℕ) (bits : List Bool) {r : ℕ}
(h : r < base ∨ base+bits.length ≤ r) : fillBits a base bits r = a r := by
have hn : ¬ (base ≤ r ∧ r < base+bits.length) := by omega
simp [fillBits,hn]
theorem tierTestGates_extend (a : Assignment) (j n x y b : ℕ)
(hx : ∀ k, tierAbove n x k < b) (hy : ∀ k, tierAbove n y k < b) :
∃ a' : Assignment, (∀ r, r < b ∨ b+4 ≤ r → a' r = a r) ∧
(∀ g ∈ tierTestGates j x y n b,g.Holds a') := by
let bits := tierFlagValues a j n x y
let a' := fillBits a b bits
have hl : bits.length=4 := rfl
have hKeep (r : ℕ) (h : r < b ∨ b+4 ≤ r) : a' r = a r :=
fillBits_frame a b bits (hl.symm ▸ h)
have hB (i : ℕ) (hi : i < 4) : a' (b+i) = bits[i]'(by omega) :=
fillBits_at a b bits (by omega)
have hx' (k : ℕ) := hKeep _ (Or.inl (hx k))
have hy' (k : ℕ) := hKeep _ (Or.inl (hy k))
refine ⟨a',hKeep,?_⟩
have h0 : a' b = (a (tierAbove n x (2^j-1)) || a (tierAbove n y (2^j-1))) := by
simpa [bits,tierFlagValues] using hB 0 (by decide)
have h1 : a' (b+1) = !a' b := by
rw [h0]
simpa [bits,tierFlagValues] using hB 1 (by decide)
have h2 : a' (b+2) = (a (tierAbove n x (2^(j-1)-1)) || a (tierAbove n y (2^(j-1)-1))) := by
simpa [bits,tierFlagValues] using hB 2 (by decide)
have h3 : a' (b+3) = (a' (b+1) && a' (b+2)) := by
rw [h1,h0,h2]
simpa [bits,tierFlagValues] using hB 3 (by decide)
by_cases h : j=0
· simp only [tierTestGates,h,if_true,List.forall_mem_cons,List.not_mem_nil,false_implies,
implies_true,and_true,Gate.Holds]
subst j
exact ⟨by rw [h0,hx',hy'],h1⟩
· simp only [tierTestGates,h,if_false,List.forall_mem_cons,List.not_mem_nil,false_implies,
implies_true,and_true,Gate.Holds]
exact ⟨by rw [h0,hx',hy'],h1,by rw [h2,hx',hy'],h3⟩
def emissionControlValues (a : Assignment) (live writes src dst : ℕ) : List Bool :=
let pick := if a writes then a src else a dst
let cancel := !a src
let insert := a writes && a dst
let move := cancel && insert
let reading := !a writes
[pick,a live && pick,cancel,insert,move,a live && move,reading,reading || a dst]
theorem emissionControl_extend (a : Assignment) (b live writes src dst : ℕ)
(hl : live < b) (hw : writes < b) (hs : src < b) (hd : dst < b) :
∃ a' : Assignment, (∀ r, r < b ∨ b+8 ≤ r → a' r = a r) ∧
(∀ g ∈ emissionControl b live writes src dst,g.Holds a') := by
let bits := emissionControlValues a live writes src dst
let a' := fillBits a b bits
have hLen : bits.length=8 := rfl
have hKeep (r : ℕ) (h : r < b ∨ b+8 ≤ r) : a' r = a r :=
fillBits_frame a b bits (hLen.symm ▸ h)
have hB (i : ℕ) (hi : i < 8) : a' (b+i) = bits[i]'(by omega) :=
fillBits_at a b bits (by omega)
have hL := hKeep _ (Or.inl hl)
have hW := hKeep _ (Or.inl hw)
have hS := hKeep _ (Or.inl hs)
have hD := hKeep _ (Or.inl hd)
have o0 : a' b = (if a writes then a src else a dst) := by
simpa [bits,emissionControlValues] using hB 0 (by decide)
have o1 : a' (b+1) = (a live && (if a writes then a src else a dst)) :=
hB 1 (by decide)
have o2 : a' (b+2) = !a src := hB 2 (by decide)
have o3 : a' (b+3) = (a writes && a dst) := hB 3 (by decide)
have o4 : a' (b+4) = (!a src && (a writes && a dst)) := hB 4 (by decide)
have o5 : a' (b+5) = (a live && (!a src && (a writes && a dst))) := hB 5 (by decide)
have o6 : a' (b+6) = !a writes := hB 6 (by decide)
have o7 : a' (b+7) = (!a writes || a dst) := hB 7 (by decide)
refine ⟨a',hKeep,?_⟩
simp only [emissionControl,List.forall_mem_cons,List.not_mem_nil,false_implies,implies_true,and_true,
Gate.Holds,hL,hW,hS,hD,o0,o1,o2,o3,o4,o5,o6,o7]
theorem emissionMux_extend (a : Assignment) (b w writes : ℕ) (old value : ℕ→ℕ)
(hw : writes < b+8) (ho : ∀ i < w,old i < b+8) (hv : ∀ i < w,value i < b+8) :
∃ a' : Assignment, (∀ r, r < b+8 ∨ b+8+w ≤ r → a' r = a r) ∧
(∀ g ∈ emissionMux b w writes old value,g.Holds a') := by
let bits := (List.range w).map (fun i => if a writes then a (old i) else a (value i))
let a' := fillBits a (b+8) bits
have hlen : bits.length=w := by simp [bits]
have hKeep (r : ℕ) (h : r < b+8 ∨ b+8+w ≤ r) : a' r = a r :=
fillBits_frame a (b+8) bits (hlen.symm ▸ h)
refine ⟨a',hKeep,?_⟩
intro g hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hI := List.mem_range.mp hi
change a' (b+8+i) = (if a' writes then a' (old i) else a' (value i))
have hB : a' (b+8+i) = bits[i]'(by omega) := fillBits_at a (b+8) bits (by omega)
rw [hKeep _ (.inl hw),hKeep _ (.inl (ho i hI)),hKeep _ (.inl (hv i hI)),hB]
simp [bits]
end CNFEncComplexity.Robson
/- RobsonEmitBlock -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
structure EmitFlags where
addr : ℕ
value : ℕ
old : ℕ
def EmitFlags.valid (u : EmitInput) (f : EmitFlags) (a : Assignment) : Prop :=
GateSat a (widthCircuit f.addr u.width u.address) ∧
GateSat a (widthCircuit f.value u.width u.value) ∧
GateSat a (widthCircuit f.old u.width u.old)
def EmitInput.coreGates (u : EmitInput) (f : EmitFlags) (j z b : ℕ) : List Gate :=
let source := tierTestOutput j b
let dest := tierTestOutput j (b+4)
tierTestGates j f.addr f.old u.width b ++ tierTestGates j f.addr f.value u.width (b+4) ++
emissionControl (b+8) u.live u.writes source dest ++
emissionMux (b+8) (2^j) u.writes (paddedKey u.width z u.old) (paddedKey u.width z u.value)
theorem EmitInput.coreGates_length (u : EmitInput) (f : EmitFlags) (j z b : ℕ) :
(u.coreGates f j z b).length ≤ 17*2^j := by
have hS := tierTestGates_length j f.addr f.old u.width b
have hD := tierTestGates_length j f.addr f.value u.width (b+4)
have hW := Nat.two_pow_pos j
simp only [EmitInput.coreGates,List.length_append,emissionControl,emissionMux,
List.length_cons,List.length_nil,List.length_map,List.length_range]
omega
theorem EmitInput.coreGates_sound (u : EmitInput) (f : EmitFlags) (a : Assignment)
(j z o b : ℕ) (hz : a z=false) (ho : a o=true) (hW : f.valid u a)
(h : GateSat a (u.coreGates f j z b)) :
[laneRecord a (2^j) 0 (emitFirstRow u (2^j) z o (b+8)),
laneRecord a (2^j) 0 (emitSecondRow u (2^j) z o (b+8))] = emitTier j (u.read a) := by
simp only [EmitInput.coreGates,GateSat.append] at h
obtain ⟨⟨⟨hs,hd⟩,hc⟩,hm⟩ := h
exact emitRows_exact a u j z o (b+8) (tierTestOutput j b) (tierTestOutput j (b+4)) hz ho
(tierTestGates_exact a j f.addr f.old u.width b u.address u.old hW.1 hW.2.2 hs)
(tierTestGates_exact a j f.addr f.value u.width (b+4) u.address u.value hW.1 hW.2.1 hd)
hc hm
theorem tierTestGates_names (j n x y b : ℕ)
(g : Gate) (hg : g ∈ tierTestGates j x y n b) (r : ℕ) (hr : r ∈ RobsonCNF.Gate.names g) :
b ≤ r ∧ r < b+4 ∨ (∃ k,r=tierAbove n x k) ∨ ∃ k,r=tierAbove n y k := by
by_cases hj : j=0
· simp only [tierTestGates,hj,if_true,List.mem_cons,List.not_mem_nil,or_false] at hg
rcases hg with rfl|rfl <;>
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
· rcases hr with rfl|rfl|rfl
· exact .inl ⟨by omega,by omega⟩
· exact .inr (.inl ⟨_,rfl⟩)
· exact .inr (.inr ⟨_,rfl⟩)
· rcases hr with rfl|rfl <;> exact .inl ⟨by omega,by omega⟩
· simp only [tierTestGates,hj,if_false,List.mem_cons,List.not_mem_nil,or_false] at hg
rcases hg with rfl|rfl|rfl|rfl <;>
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
· rcases hr with rfl|rfl|rfl
· exact .inl ⟨by omega,by omega⟩
· exact .inr (.inl ⟨_,rfl⟩)
· exact .inr (.inr ⟨_,rfl⟩)
· rcases hr with rfl|rfl <;> exact .inl ⟨by omega,by omega⟩
· rcases hr with rfl|rfl|rfl
· exact .inl ⟨by omega,by omega⟩
· exact .inr (.inl ⟨_,rfl⟩)
· exact .inr (.inr ⟨_,rfl⟩)
· rcases hr with rfl|rfl|rfl <;> exact .inl ⟨by omega,by omega⟩
theorem tierTestGates_names_lt (j n x y b : ℕ)
(hx : ∀ k,tierAbove n x k < b) (hy : ∀ k,tierAbove n y k < b) :
∀ g ∈ tierTestGates j x y n b, ∀ r ∈ RobsonCNF.Gate.names g, r < b+4 := by
intro g hg r hr
rcases tierTestGates_names j n x y b g hg r hr with hh|⟨k,rfl⟩|⟨k,rfl⟩
· exact hh.2
· exact (hx k).trans_le (by omega)
· exact (hy k).trans_le (by omega)
theorem emissionControl_names_lt (b live writes src dst : ℕ)
(hl : live < b) (hw : writes < b) (hs : src < b) (hd : dst < b) :
∀ g ∈ emissionControl b live writes src dst, ∀ r ∈ RobsonCNF.Gate.names g, r < b+8 := 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
theorem emissionMux_names_lt (b w writes : ℕ) (old value : ℕ→ℕ)
(hw : writes < b+8) (ho : ∀ i < w,old i < b+8) (hv : ∀ i < w,value i < b+8) :
∀ g ∈ emissionMux b w writes old value, ∀ r ∈ RobsonCNF.Gate.names g, r < b+8+w := by
intro g hg r hr
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hi' := List.mem_range.mp hi
have h1 := ho i hi'
have h2 := hv i hi'
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
omega
private theorem preserves_prefix_sat {a a' : Assignment} {gates : List Gate} {n : ℕ}
(h : GateSat a gates) (hn : ∀ g ∈ gates, ∀ r ∈ RobsonCNF.Gate.names g, r < n)
(ha : ∀ r < n, a' r = a r) : GateSat a' gates := by
intro g hg
exact (g.holds_congr a' a (fun r hr => ha _ (hn g hg r hr))).2 (h g hg)
theorem EmitInput.coreGates_extend (u : EmitInput) (f : EmitFlags) (a : Assignment) (j z b : ℕ)
(hLive : u.live < b) (hWrites : u.writes < b) (hZ : z < b)
(hOld : ∀ i < u.width,u.old i < b) (hValue : ∀ i < u.width,u.value i < b)
(hAddr : ∀ k,tierAbove u.width f.addr k < b)
(hVO : ∀ k,tierAbove u.width f.value k < b)
(hOO : ∀ k,tierAbove u.width f.old k < b) :
∃ beta, Keeps a beta b (b+16+2^j) ∧ GateSat beta (u.coreGates f j z b) := by
let w := 2^j
let s := tierTestOutput j b
let d := tierTestOutput j (b+4)
have hS : s < b+8 := by unfold s tierTestOutput; split <;> omega
have hD : d < b+8 := by unfold d tierTestOutput; split <;> omega
have hPad (k : ℕ→ℕ) (hk : ∀ i < u.width,k i < b) : ∀ i < w, paddedKey u.width z k i < b+16 := by
intro i hi
unfold paddedKey
split
· exact (hk i ‹i < u.width›).trans_le (by omega)
· omega
have hLive' : u.live < b+8 := by omega
have hWrites' : u.writes < b+8 := by omega
have hWrites'' : u.writes < b+8+8 := by omega
have hAddress' (k : ℕ) : tierAbove u.width f.addr k < b+4 := (hAddr k).trans_le (by omega)
have hVO' (k : ℕ) : tierAbove u.width f.value k < b+4 := (hVO k).trans_le (by omega)
obtain ⟨a₁,h1,g1⟩ := tierTestGates_extend a j u.width f.addr f.old b hAddr hOO
obtain ⟨a₂,h2,g2⟩ := tierTestGates_extend a₁ j u.width f.addr f.value (b+4) hAddress' hVO'
obtain ⟨a₃,h3,g3⟩ := emissionControl_extend a₂ (b+8) u.live u.writes s d hLive' hWrites' hS hD
obtain ⟨a₄,h4,g4⟩ := emissionMux_extend a₃ (b+8) w u.writes
(paddedKey u.width z u.old) (paddedKey u.width z u.value)
hWrites'' (hPad _ hOld) (hPad _ hValue)
have hkeep : Keeps a a₄ b (b+16+w) := by
intro i hi
rcases hi with hi|hi
· rw [h4 i (.inl (by omega)),h3 i (.inl (by omega)),h2 i (.inl (by omega)),h1 i (.inl hi)]
· have h16 : b+16 ≤ i := (Nat.le_add_right _ w).trans hi
have hu : b+8+8+w ≤ i := by
rw [show b+8+8+w=b+16+w by omega]
exact hi
rw [h4 i (.inr hu),h3 i (.inr (by omega)),h2 i (.inr (by omega)),h1 i (.inr (by omega))]
have hg2 := preserves_prefix_sat g2
(tierTestGates_names_lt _ _ _ _ _ hAddress' hVO')
(fun r hr => h3 r (.inl (by omega)))
have hgg1 := preserves_prefix_sat g1
(tierTestGates_names_lt _ _ _ _ _ hAddr hOO)
(fun r hr => (h3 r (.inl (by omega))).trans (h2 r (.inl hr)))
have hf1 := preserves_prefix_sat hgg1
(tierTestGates_names_lt _ _ _ _ _ hAddr hOO) (fun r hr => h4 r (.inl (by omega)))
have hf2 := preserves_prefix_sat hg2
(tierTestGates_names_lt _ _ _ _ _ hAddress' hVO') (fun r hr => h4 r (.inl (by omega)))
have hf3 := preserves_prefix_sat g3
(emissionControl_names_lt _ _ _ _ _ hLive' hWrites' hS hD) (fun r hr => h4 r (.inl hr))
refine ⟨a₄,hkeep,?_⟩
simp only [EmitInput.coreGates,GateSat.append]
exact ⟨⟨⟨hf1,hf2⟩,hf3⟩,g4⟩
end CNFEncComplexity.Robson
/- RobsonEmitLayout -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def emitSlotSpan (t : ℕ) : ℕ := layoutHorizon t*(layoutHeight t+1)
def emitSlotIndex (t : ℕ) (s : ℕ×ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2
theorem emitSlotIndex_bound {t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) :
emitSlotIndex t s < emitSlotSpan t := by
rcases s with ⟨a,j⟩
have ⟨ha,hj,_⟩ := layout_mem.mp hs
have hMul := Nat.mul_le_mul_right (layoutHeight t+1) (Nat.succ_le_of_lt ha)
rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hMul
unfold emitSlotIndex emitSlotSpan
dsimp only
omega
private theorem linearIndex_injective {d a b i j : ℕ} (hi : i < d) (hj : j < d)
(h : a*d+i=b*d+j) : a=b ∧ i=j := by
have hPos : 0 < d := by omega
have h₁ : (a*d+i)/d = a := by
rw [Nat.mul_comm a d,Nat.mul_add_div hPos,Nat.div_eq_of_lt hi,Nat.add_zero]
have h₂ : (b*d+j)/d = b := by
rw [Nat.mul_comm b d,Nat.mul_add_div hPos,Nat.div_eq_of_lt hj,Nat.add_zero]
have hA := h₁.symm.trans ((congrArg (fun n => n/d) h).trans h₂)
subst b
exact ⟨rfl,by omega⟩
theorem emitSlotIndex_injective {t : ℕ} {s u : ℕ×ℕ}
(hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t)
(h : emitSlotIndex t s = emitSlotIndex t u) : s=u := by
rcases s with ⟨a,j⟩
rcases u with ⟨c,k⟩
have ⟨hA,hB⟩ := linearIndex_injective
(Nat.lt_succ_of_le (layout_mem.mp hs).2.1) (Nat.lt_succ_of_le (layout_mem.mp hu).2.1) h
exact Prod.ext hA hB
def emitInputs (base n t : ℕ) (s : ℕ×ℕ) (row : ℕ) : EmitInput :=
let b := trieLevel t
⟨normalizeWidth b s,port n t s (3+5*row) 0,port n t s (3+5*row+1) 0,
(normalizeSlotWires base n t b s row 0).label,
(normalizeSlotWires base n t b s row 1).label,
(normalizeSlotWires base n t b s row 2).label⟩
theorem emitInputs_eq (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) (row : ℕ) :
(emitInputs base n t s row).read a = slotCompactMemory a base n t (trieLevel t) s row := rfl
def emitFlagStride (t : ℕ) : ℕ := layoutHorizon t+2
def emitFlagIndex (t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : ℕ :=
9*emitSlotIndex t s+3*r+f
def emitFlagBase (base t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : ℕ :=
base+emitFlagIndex t s r f*emitFlagStride t
def emitFlagTop (base t : ℕ) : ℕ :=
base+9*emitSlotSpan t*emitFlagStride t
def emitFlags (base t : ℕ) (s : ℕ×ℕ) (r : ℕ) : EmitFlags :=
⟨emitFlagBase base t s r 0,emitFlagBase base t s r 1,emitFlagBase base t s r 2⟩
theorem emitFlagWidth_bound {t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) :
normalizeWidth (trieLevel t) s+1 ≤ emitFlagStride t := by
rcases s with ⟨a,j⟩
have hW : 2^j ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
have hh := min_le_left (2^j) (2^trieLevel t)
unfold normalizeWidth emitFlagStride
dsimp only
omega
theorem emitFlagBlock_bounds {base t r f : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
(hr : r < 3) (hf : f < 3) :
base ≤ emitFlagBase base t s r f ∧
emitFlagBase base t s r f+emitFlagStride t ≤ emitFlagTop base t := by
have hi := emitSlotIndex_bound hs
have hI : emitFlagIndex t s r f+1 ≤ 9*emitSlotSpan t := by unfold emitFlagIndex; omega
have h := Nat.mul_le_mul_right (emitFlagStride t) hI
rw [Nat.add_mul,Nat.one_mul] at h
unfold emitFlagBase emitFlagTop
omega
theorem emitFlagIndex_injective {t r r' f f' : ℕ} {s u : ℕ×ℕ}
(hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t) (hr : r < 3) (hr' : r'<3) (hf : f < 3) (hf' : f'<3)
(h : emitFlagIndex t s r f = emitFlagIndex t u r' f') :
s=u ∧ r=r' ∧ f=f' := by
have h1 : 3*r+f < 9 := by omega
have h2 : 3*r'+f'<9 := by omega
have hI : emitSlotIndex t s*9+(3*r+f)=emitSlotIndex t u*9+(3*r'+f') := by
unfold emitFlagIndex at h
omega
obtain ⟨hi,hj⟩ := linearIndex_injective h1 h2 hI
have ht : r*3+f=r'*3+f' := by omega
exact ⟨emitSlotIndex_injective hs hu hi,linearIndex_injective hf hf' ht⟩
def emitWidthGates (base region n t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : List Gate :=
widthCircuit (emitFlagBase region t s r f) (normalizeWidth (trieLevel t) s)
(normalizeSlotWires base n t (trieLevel t) s r f).label
def emitWidthLayoutGates (base region n t : ℕ) : List Gate :=
(layoutSlots t).flatMap fun s =>
(List.range 3).flatMap fun r =>
(List.range 3).flatMap (emitWidthGates base region n t s r)
theorem emitWidthGates_length (base region n t : ℕ) (s : ℕ×ℕ) (r f : ℕ) :
(emitWidthGates base region n t s r f).length ≤ 3*2^s.2 := by
have hp := Nat.two_pow_pos s.2
have hMin := min_le_left (2^s.2) (2^trieLevel t)
simp [emitWidthGates,length_widthCircuit,normalizeWidth]
omega
def emitLevels (t : ℕ) : ℕ := (trieWidth t+1).size+1
def emitBlockStride (t : ℕ) : ℕ := 2*(layoutHorizon t+1)+17
def emitBlockIndex (t j : ℕ) (s : ℕ×ℕ) (r : ℕ) : ℕ :=
3*(j*emitSlotSpan t+emitSlotIndex t s)+r
def emitBlockBase (base t j : ℕ) (s : ℕ×ℕ) (r : ℕ) : ℕ :=
emitFlagTop base t+emitBlockIndex t j s r*emitBlockStride t
def emitBlockTop (base t : ℕ) : ℕ :=
emitFlagTop base t+3*(emitLevels t*emitSlotSpan t)*emitBlockStride t
theorem emitBlockWidth_bound {t j : ℕ} (hj : j < emitLevels t) :
16+2^j ≤ emitBlockStride t := by
let b := trieWidth t+1
have hm : b ≤ layoutHorizon t+1 := Nat.succ_le_succ (trieWidth_in_horizon t)
have hx : 2^b.size ≤ 2*b+1 := pow2_size_le b
have hk : j ≤ b.size := Nat.le_of_lt_succ hj
have h := Nat.pow_le_pow_right (by decide : 0<(2:ℕ)) hk
unfold emitBlockStride
omega
theorem emitBlockIndex_bound {t j r : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) (hj : j < emitLevels t) (hr : r < 3) :
emitBlockIndex t j s r < 3*(emitLevels t*emitSlotSpan t) := by
have hI := emitSlotIndex_bound hs
have h := Nat.mul_le_mul_right (emitSlotSpan t) (Nat.succ_le_of_lt hj)
rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at h
unfold emitBlockIndex
omega
theorem emitBlockIndex_injective {t j j' r r' : ℕ} {s u : ℕ×ℕ}
(hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t) (hr : r < 3) (hr' : r'<3)
(h : emitBlockIndex t j s r = emitBlockIndex t j' u r') : j=j' ∧ s=u ∧ r=r' := by
have hp : (j*emitSlotSpan t+emitSlotIndex t s)*3+r =
(j'*emitSlotSpan t+emitSlotIndex t u)*3+r' := by
simp only [Nat.mul_comm _ 3]
exact h
obtain ⟨hIJ,hR⟩ := linearIndex_injective hr hr' hp
obtain ⟨hJ,hS⟩ := linearIndex_injective (emitSlotIndex_bound hs) (emitSlotIndex_bound hu) hIJ
exact ⟨hJ,emitSlotIndex_injective hs hu hS,hR⟩
def emitOne (base region n t j z : ℕ) (s : ℕ×ℕ) (r : ℕ) : List Gate :=
(emitInputs base n t s r).coreGates (emitFlags region t s r) j z (emitBlockBase region t j s r)
def emitTierGateList (base region n t j z : ℕ) (slots : List (ℕ×ℕ)) : List Gate :=
slots.flatMap fun s => (List.range 3).flatMap (emitOne base region n t j z s)
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).