Gates for sorted memory windows
DefinitionCNFEncComplexity_RobsonMemoryWindowGatescomplexity-theorysatisfiability
Gate relations for one chronological memory window. Stable address-and-time sorting checks each value transition and connects adjacent windows through boundary snapshots.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryCertificates
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonMemRow -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def memoryOpt (a : Assignment) (flag : ℕ) (bits : ℕ → ℕ) (w : ℕ) : Option ℕ :=
if a flag then some (wireValue a bits w) else none
def memoryOptEqual (p q : ℕ) (x y : ℕ → ℕ) (w : ℕ) : List Gate :=
.copy p q :: guarded (.Pos p) (wordCopy w x y)
theorem memoryOptEqual_exact (a : Assignment) (p q : ℕ) (x y : ℕ → ℕ) (w : ℕ) :
(∀ g ∈ memoryOptEqual p q x y w, g.Holds a) ↔ memoryOpt a p x w = memoryOpt a q y w := by
rw [memoryOptEqual,List.forall_mem_cons,guarded_exact,wordCopy_exact]
change (a p = a q ∧ (a p = true → _)) ↔ _
cases hp : a p <;> cases hq : a q <;> simp [memoryOpt,hp,hq]
theorem memoryOptEqual_length (p q : ℕ) (x y : ℕ → ℕ) (w : ℕ) :
(memoryOptEqual p q x y w).length ≤ 1+4*w := by
have h := length_guarded (.Pos p) (wordCopy w x y)
simpa [memoryOptEqual,wordCopy,Nat.add_comm] using Nat.succ_le_succ h
/-- If live, the canonical initial value has a zero payload. -/
def zeroOptGates (p : ℕ) (x : ℕ → ℕ) (w : ℕ) : List Gate :=
guarded (.Pos p) (wordConst w x 0)
private theorem zeroOptGates_exact (a : Assignment) (p : ℕ) (x : ℕ → ℕ) (w : ℕ) :
(∀ g ∈ zeroOptGates p x w, g.Holds a) ↔ (a p = true → wireValue a x w = 0) := by
rw [zeroOptGates,guarded_exact]
exact imp_congr_right (fun _ => wordConst_exact w x 0 (by positivity) a)
private theorem zeroOptGates_length (p : ℕ) (x : ℕ → ℕ) (w : ℕ) :
(zeroOptGates p x w).length ≤ 4*w := by
simpa [zeroOptGates,wordConst] using length_guarded (.Pos p) (wordConst w x 0)
def bitBand (w lo hi : ℕ) : List ℕ :=
(List.range w).filter (fun i => decide (lo ≤ i ∧ i < hi))
private theorem bitBand_mem {w lo hi i : ℕ} : i ∈ bitBand w lo hi ↔
i < w ∧ lo ≤ i ∧ i < hi := by simp [bitBand]
private theorem bitBand_length (w lo hi : ℕ) : (bitBand w lo hi).length ≤ w := by
exact (List.length_filter_le ..).trans_eq List.length_range
private theorem wireValue_lt_pow_iff (a : Assignment) (key : ℕ → ℕ) (w k : ℕ) :
wireValue a key w < 2^k ↔ ∀ i < w, k ≤ i → a (key i) = false := by
induction w with
| zero => simp [wireValue, Nat.pow_pos (by decide : (0:ℕ)<2)]
| succ w ih =>
by_cases hw : k ≤ w
· rw [wireValue]
cases hB : a (key w)
· rw [if_neg (by simp [hB]),Nat.add_zero,ih]
exact ⟨fun h i hi hik => by
rcases Nat.lt_or_eq_of_le (Nat.le_of_lt_succ hi) with hlt|rfl
· exact h i hlt hik
· exact hB,
fun h i hi hik => h i (by omega) hik⟩
· have hpow : (2:ℕ)^k ≤ 2^w := Nat.pow_le_pow_right (by decide) hw
simp only [if_true]
constructor
· omega
· intro h
have hh := h w (by omega) hw
simp [hB] at hh
· have hk : w+1 ≤ k := by omega
exact ⟨fun _ i hi h => by omega, fun _ =>
(wireValue_lt a key (w+1)).trans_le (Nat.pow_le_pow_right (by decide) hk)⟩
def initHigh (tier : ℕ) : ℕ := 2^tier-1
/-- Require precisely the correct initially occupied flag for the supplied
address. Address widths are checked by the same fixed bit bands used elsewhere. -/
def initialFlagGates (tier w flag : ℕ) (addr : ℕ → ℕ) : List Gate :=
let high := (bitBand w (initHigh tier) w).map (fun i => Literal.Pos (addr i))
let noHigh := (bitBand w (initHigh tier) w).map
(fun i => Gate.assert [.Neg flag,.Neg (addr i)])
match tier with
| 0 => .assert (.Pos flag :: high) :: noHigh
| k+1 =>
let mid := bitBand w (initHigh k) (initHigh (k+1))
.assert (.Neg flag :: mid.map (fun i => Literal.Pos (addr i))) ::
(noHigh ++ mid.map (fun i => .assert (.Pos flag :: .Neg (addr i) :: high)))
private theorem allHigh_exact (a : Assignment) (w k flag : ℕ) (addr : ℕ → ℕ) :
(∀ g ∈ (bitBand w k w).map
(fun i => Gate.assert [.Neg flag,.Neg (addr i)]), g.Holds a) ↔
(a flag = true → wireValue a addr w < 2^k) := by
rw [wireValue_lt_pow_iff]
simp only [List.forall_mem_map,bitBand_mem,Gate.Holds,satisfiesClause,List.any_cons,
satisfiesLiteral,List.any_nil,Bool.or_false,Bool.or_eq_true,Bool.not_eq_true']
constructor
· intro h hf i hi hk
exact (h i ⟨hi,hk,hi⟩).resolve_left (by simp [hf])
· intro h i hi
cases hf : a flag
· exact Or.inl rfl
· exact Or.inr (h hf i hi.1 hi.2.1)
private theorem someBand_exact (a : Assignment) (w lo hi : ℕ) (addr : ℕ → ℕ) :
((bitBand w lo hi).map (fun i => Literal.Pos (addr i))).any (satisfiesLiteral a) = true ↔
∃ i < w, lo ≤ i ∧ i < hi ∧ a (addr i) = true := by
simp [List.any_map,List.any_eq_true,bitBand_mem,satisfiesLiteral,and_assoc]
private theorem noBand_exact (a : Assignment) (w k : ℕ) (addr : ℕ → ℕ) :
((bitBand w k w).map (fun i => Literal.Pos (addr i))).any (satisfiesLiteral a) = false ↔
wireValue a addr w < 2^k := by
rw [← Bool.not_eq_true, someBand_exact, wireValue_lt_pow_iff]
simp only [not_exists,not_and,Bool.not_eq_true]
exact ⟨fun h i hi hk => h i hi hk hi,fun h i hi hk _ => h i hi hk⟩
private theorem midBand_exact (a : Assignment) (w lo hi : ℕ) (addr : ℕ → ℕ)
(hHigh : wireValue a addr w < 2^hi) :
(∃ i < w, lo ≤ i ∧ i < hi ∧ a (addr i) = true) ↔ 2^lo ≤ wireValue a addr w := by
rw [← Nat.not_lt,wireValue_lt_pow_iff]
have hZero := (wireValue_lt_pow_iff a addr w hi).1 hHigh
constructor
· rintro ⟨i,hiw,hlo,hihi,hbi⟩ hz
exact Bool.noConfusion (hbi.symm.trans (hz i hiw hlo))
· intro h
by_contra! hn
apply h
intro i hiw hlo
by_cases hh : i < hi
· exact Bool.eq_false_of_not_eq_true (hn i hiw hlo hh)
· exact hZero i hiw (by omega)
private theorem bitTierAddress_initial (tier addr : ℕ) :
bitTier addr 0 = tier ↔ addr < 2^initHigh tier ∧
match tier with | 0 => True | k+1 => 2^initHigh k ≤ addr := by
have hb (k : ℕ) : bitTier addr 0 ≤ k ↔ addr < 2^initHigh k := by
simp only [bitTier,Nat.size_zero,max_zero,initHigh]
rw [Nat.size_le, ← Nat.le_sub_one_iff_lt (by positivity : 0 < (2:ℕ)^k),Nat.size_le]
cases tier with
| zero => simpa [Nat.le_zero] using hb 0
| succ tier =>
rw [show bitTier addr 0 = tier+1 ↔ bitTier addr 0 ≤ tier+1 ∧ ¬ bitTier addr 0 ≤ tier by omega,
hb,hb,Nat.not_lt]
theorem initialFlagGates_exact (a : Assignment) (tier w flag : ℕ) (addr : ℕ → ℕ) :
(∀ g ∈ initialFlagGates tier w flag addr, g.Holds a) ↔
(a flag = true ↔ bitTier (wireValue a addr w) 0 = tier) := by
cases tier with
| zero =>
rw [initialFlagGates,List.forall_mem_cons,allHigh_exact,bitTierAddress_initial]
simp only [Gate.Holds,satisfiesClause,List.any_cons,satisfiesLiteral,Bool.or_eq_true,and_true]
have h := noBand_exact a w (initHigh 0) addr
generalize ht : ((bitBand w (initHigh 0) w).map
(fun i => Literal.Pos (addr i))).any (satisfiesLiteral a) = z at h ⊢
cases hp : a flag <;> cases hz : z <;> simp_all
| succ k =>
let H := wireValue a addr w < 2^initHigh (k+1)
let M := ∃ i < w, initHigh k ≤ i ∧ i < initHigh (k+1) ∧ a (addr i) = true
have hHigh := noBand_exact a w (initHigh (k+1)) addr
have hMid : H → (M ↔ 2^initHigh k ≤ wireValue a addr w) :=
midBand_exact a w _ _ addr
have h0 :
(∀ g ∈ initialFlagGates (k+1) w flag addr, g.Holds a) ↔
(a flag = true → M) ∧ (a flag = true → H) ∧ (H → M → a flag = true) := by
simp only [initialFlagGates,List.forall_mem_cons,List.forall_mem_append,allHigh_exact]
apply and_congr
· simp only [Gate.Holds,satisfiesClause,List.any_cons,satisfiesLiteral,Bool.or_eq_true,
Bool.not_eq_true',someBand_exact]
cases hp : a flag <;> simp [hp,M]
· apply and_congr Iff.rfl
simp only [List.forall_mem_map,bitBand_mem,Gate.Holds,satisfiesClause,List.any_cons,
satisfiesLiteral,Bool.or_eq_true,Bool.not_eq_true']
constructor
· rintro hs hH ⟨i,hi,hlo,hhi,hb⟩
exact (hs i ⟨hi,hlo,hhi⟩).resolve_right (by simp [hHigh.mpr hH,hb])
· intro hs i hi
by_cases hH : H
· rw [hHigh.mpr hH]
by_cases hb : a (addr i) = true
· exact Or.inl (hs hH ⟨i,hi.1,hi.2.1,hi.2.2,hb⟩)
· exact Or.inr (Or.inl (Bool.eq_false_of_not_eq_true hb))
· have hz : ((bitBand w (initHigh (k+1)) w).map (fun i => Literal.Pos (addr i))).any
(satisfiesLiteral a) = true :=
Bool.eq_true_of_not_eq_false (fun hf => hH (hHigh.mp hf))
exact Or.inr (Or.inr hz)
rw [h0,bitTierAddress_initial]
change _ ↔ (a flag = true ↔ H ∧ _)
constructor
· rintro ⟨hp,hh,hq⟩
exact ⟨fun hf => ⟨hh hf,(hMid (hh hf)).mp (hp hf)⟩,
fun ⟨he,hl⟩ => hq he ((hMid he).mpr hl)⟩
· intro h
exact ⟨fun hp => (hMid (h.mp hp).1).mpr (h.mp hp).2,
fun hp => (h.mp hp).1,fun hh hm => h.mpr ⟨hh,(hMid hh).mp hm⟩⟩
theorem initialFlagGates_length (tier w flag : ℕ) (addr : ℕ → ℕ) :
(initialFlagGates tier w flag addr).length ≤ 1+2*w := by
cases tier with
| zero =>
have h := bitBand_length w (initHigh 0) w
simp [initialFlagGates]
omega
| succ k =>
have hh := bitBand_length w (initHigh (k+1)) w
have hm := bitBand_length w (initHigh k) (initHigh (k+1))
simp [initialFlagGates]
omega
def groupInitial (tier : Option ℕ) : LocalMemory :=
match tier with
| none => fun _ => none
| some j => fun a => liveMemory bitTier (fun _ => 0) (j,a)
def groupInitialGates (tier : Option ℕ) (w before : ℕ) (addr value : ℕ → ℕ) : List Gate :=
match tier with
| none => [.pin before false]
| some j => initialFlagGates j w before addr ++ zeroOptGates before value w
theorem groupInitialGates_exact (a : Assignment) (tier : Option ℕ)
(w before : ℕ) (addr value : ℕ → ℕ) :
(∀ g ∈ groupInitialGates tier w before addr value, g.Holds a) ↔
groupInitial tier (wireValue a addr w) = memoryOpt a before value w := by
cases tier with
| none =>
cases hb : a before <;> simp [groupInitialGates,groupInitial,memoryOpt,Gate.Holds,hb]
| some j =>
rw [groupInitialGates,List.forall_mem_append,initialFlagGates_exact,zeroOptGates_exact]
by_cases he : bitTier (wireValue a addr w) 0 = j
· change _ ↔ (if j = bitTier (wireValue a addr w) 0 then some 0 else none) = _
rw [if_pos he.symm]
cases hb : a before <;> simp [memoryOpt,he,hb]
exact Eq.comm
· have hne : j ≠ bitTier (wireValue a addr w) 0 := Ne.symm he
cases hb : a before <;> simp [groupInitial,liveMemory,memoryOpt,hne,he,hb]
theorem groupInitialGates_length (tier : Option ℕ) (w before : ℕ) (addr value : ℕ → ℕ) :
(groupInitialGates tier w before addr value).length ≤ 1+6*w := by
cases tier with
| none => simp [groupInitialGates]
| some j =>
have h1 := initialFlagGates_length j w before addr
have h2 := zeroOptGates_length before value w
simp [groupInitialGates]
omega
end CNFEncComplexity.Robson
/- RobsonMemPair -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def memLaneWidth (w h : ℕ) : ℕ := 1+h+w+(1+w)+(1+w)
def laneActive (r : ℕ → ℕ) : ℕ := r 0
def laneTime (r : ℕ → ℕ) (i : ℕ) : ℕ := r (1+i)
def laneAddress (h : ℕ) (r : ℕ → ℕ) (i : ℕ) : ℕ := r (1+h+i)
def laneBeforeFlag (w h : ℕ) (r : ℕ → ℕ) : ℕ := r (1+h+w)
def laneBefore (w h : ℕ) (r : ℕ → ℕ) (i : ℕ) : ℕ := r (1+h+w+1+i)
def laneAfterFlag (w h : ℕ) (r : ℕ → ℕ) : ℕ := r (1+h+w+(1+w))
def laneAfter (w h : ℕ) (r : ℕ → ℕ) (i : ℕ) : ℕ := r (1+h+w+(1+w)+1+i)
def laneRecord (a : Assignment) (w h : ℕ) (r : ℕ → ℕ) : Option LocalRecord :=
if a (laneActive r) then
some ⟨wireValue a (laneAddress h r) w,
memoryOpt a (laneBeforeFlag w h r) (laneBefore w h r) w,
memoryOpt a (laneAfterFlag w h r) (laneAfter w h r) w⟩
else none
def laneTag (a : Assignment) (w h : ℕ) (r : ℕ → ℕ) : Option LocalRecord × ℕ :=
(laneRecord a w h r,wireValue a (laneTime r) h)
def laneInit (tier : Option ℕ) (w h : ℕ) (r : ℕ → ℕ) : List Gate :=
guarded (.Pos (laneActive r)) (groupInitialGates tier w (laneBeforeFlag w h r)
(laneAddress h r) (laneBefore w h r))
theorem laneInit_exact (a : Assignment) (tier : Option ℕ) (w h : ℕ) (r : ℕ → ℕ) :
(∀ g ∈ laneInit tier w h r, g.Holds a) ↔
(laneRecord a w h r).elim True (fun v => groupInitial tier v.addr = v.before) := by
rw [laneInit,guarded_exact]
change (_ = true → _) ↔ _
simp only [groupInitialGates_exact,laneRecord]
cases hp : a (laneActive r) <;> simp [satisfiesLiteral,hp]
theorem laneInit_length (tier : Option ℕ) (w h : ℕ) (r : ℕ → ℕ) :
(laneInit tier w h r).length ≤ 4+24*w := by
unfold laneInit
refine (length_guarded _ _).trans ?_
have hi := groupInitialGates_length tier w (laneBeforeFlag w h r)
(laneAddress h r) (laneBefore w h r)
omega
def laneKey (h : ℕ) (r : ℕ → ℕ) : ℕ → ℕ :=
joinKey (laneTime r) (laneAddress h r) h
def laneCmpBase (w h base : ℕ) : ℕ := base+4*(h+w)+2
def laneCmpEnd (w h base : ℕ) : ℕ := laneCmpBase w h base+4*w+2
def lanePairComparators (w h base : ℕ) (l r : ℕ → ℕ) : List Gate :=
compareCircuit base (h+w) (laneKey h r) (laneKey h l) ++
compareCircuit (laneCmpBase w h base) w (laneAddress h l) (laneAddress h r)
def lanePairChecks (tier : Option ℕ) (w h base : ℕ) (l r : ℕ → ℕ) : List Gate :=
let eqAddr := eqWire (laneCmpBase w h base) w
[.assert [.Pos (laneActive l),.Neg (laneActive r)],
.assert [.Neg (laneActive l),.Neg (laneActive r),.Neg (ltWire base (h+w))]] ++
guarded (.Pos (laneActive l)) (guarded (.Pos (laneActive r))
(guarded (.Pos eqAddr) (memoryOptEqual (laneAfterFlag w h l) (laneBeforeFlag w h r)
(laneAfter w h l) (laneBefore w h r) w) ++
guarded (.Neg eqAddr) (groupInitialGates tier w (laneBeforeFlag w h r)
(laneAddress h r) (laneBefore w h r))))
def lanePair (tier : Option ℕ) (w h base : ℕ) (l r : ℕ → ℕ) : List Gate :=
lanePairComparators w h base l r ++ lanePairChecks tier w h base l r
private theorem laneKey_le_iff (a : Assignment) (w h : ℕ) (l r : ℕ → ℕ) :
¬ wireValue a (laneKey h r) (h+w) < wireValue a (laneKey h l) (h+w) ↔
wireValue a (laneAddress h l) w < wireValue a (laneAddress h r) w ∨
(wireValue a (laneAddress h l) w = wireValue a (laneAddress h r) w ∧
wireValue a (laneTime l) h ≤ wireValue a (laneTime r) h) := by
unfold laneKey
rw [wireValue_joinKey_lt]
omega
theorem lanePairChecks_exact (a : Assignment) (tier : Option ℕ) (w h base : ℕ)
(l r : ℕ → ℕ) (hC : ∀ g ∈ lanePairComparators w h base l r, g.Holds a) :
(∀ g ∈ lanePairChecks tier w h base l r, g.Holds a) ↔
slotTaggedLE (laneTag a w h l) (laneTag a w h r) ∧
slotBefore (groupInitial tier) (laneTag a w h l) (laneTag a w h r) := by
rw [lanePairComparators,List.forall_mem_append] at hC
have hLt := (compareCircuit_outputs _ _ _ _ a hC.1 _ le_rfl).1
have hEq := (compareCircuit_outputs _ _ _ _ a hC.2 _ le_rfl).2
rw [lanePairChecks,List.forall_mem_append,List.forall_mem_cons,List.forall_mem_cons,
guarded_exact]
simp only [List.not_mem_nil,false_implies,implies_true,and_true]
have hg :
(satisfiesLiteral a (.Pos (laneActive l)) = true →
∀ g ∈ guarded (.Pos (laneActive r)) (guarded (.Pos (eqWire (laneCmpBase w h base) w))
(memoryOptEqual (laneAfterFlag w h l) (laneBeforeFlag w h r)
(laneAfter w h l) (laneBefore w h r) w) ++
guarded (.Neg (eqWire (laneCmpBase w h base) w))
(groupInitialGates tier w (laneBeforeFlag w h r) (laneAddress h r) (laneBefore w h r))),
g.Holds a) ↔
(a (laneActive l) = true → a (laneActive r) = true →
(if wireValue a (laneAddress h l) w = wireValue a (laneAddress h r) w then
memoryOpt a (laneAfterFlag w h l) (laneAfter w h l) w
else groupInitial tier (wireValue a (laneAddress h r) w)) =
memoryOpt a (laneBeforeFlag w h r) (laneBefore w h r) w) := by
simp only [guarded_exact,List.forall_mem_append,memoryOptEqual_exact,
groupInitialGates_exact,satisfiesLiteral,hEq,decide_eq_true_eq]
by_cases ha : wireValue a (laneAddress h l) w = wireValue a (laneAddress h r) w <;>
simp [ha]
rw [hg]
have ho : (Gate.assert [.Neg (laneActive l),.Neg (laneActive r),.Neg (ltWire base (h+w))]).Holds a ↔
(a (laneActive l) = true → a (laneActive r) = true → ¬
wireValue a (laneKey h r) (h+w) < wireValue a (laneKey h l) (h+w)) := by
simp only [Gate.Holds,satisfiesClause,List.any_cons,List.any_nil,satisfiesLiteral,
Bool.or_false,Bool.or_eq_true,hLt,Bool.not_eq_true',decide_eq_false_iff_not]
cases hl : a (laneActive l) <;> cases hr : a (laneActive r) <;> simp [hl,hr]
rw [ho]
simp only [Gate.Holds,satisfiesClause,List.any_cons,List.any_nil,satisfiesLiteral,
Bool.or_false,Bool.or_eq_true,laneKey_le_iff,laneTag,laneRecord]
cases hl : a (laneActive l) <;> cases hr : a (laneActive r) <;>
simp [hl,hr,slotTaggedLE,slotBefore,localTaggedLE]
theorem lanePair_length (tier : Option ℕ) (w h base : ℕ) (l r : ℕ → ℕ) :
(lanePair tier w h base l r).length ≤ 4*h+648*w+134 := by
have h1 := memoryOptEqual_length (laneAfterFlag w h l) (laneBeforeFlag w h r)
(laneAfter w h l) (laneBefore w h r) w
have h2 := groupInitialGates_length tier w (laneBeforeFlag w h r)
(laneAddress h r) (laneBefore w h r)
let eqAddr := eqWire (laneCmpBase w h base) w
let copyG := guarded (.Pos eqAddr) (memoryOptEqual (laneAfterFlag w h l) (laneBeforeFlag w h r)
(laneAfter w h l) (laneBefore w h r) w)
let initG := guarded (.Neg eqAddr)
(groupInitialGates tier w (laneBeforeFlag w h r) (laneAddress h r) (laneBefore w h r))
let bothG := guarded (.Pos (laneActive r)) (copyG++initG)
have h3 : copyG.length ≤ 4*(1+4*w) := (length_guarded _ _).trans (Nat.mul_le_mul_left _ h1)
have h4 : initG.length ≤ 4*(1+6*w) := (length_guarded _ _).trans (Nat.mul_le_mul_left _ h2)
have h5 : bothG.length ≤ 4*(copyG.length+initG.length) := by
simpa only [List.length_append] using length_guarded (.Pos (laneActive r)) (copyG++initG)
have h6 := length_guarded (.Pos (laneActive l)) bothG
unfold lanePair lanePairComparators lanePairChecks
simp only [List.length_append,length_compareCircuit,List.length_cons,List.length_nil]
change _ + (2 + (guarded (.Pos (laneActive l)) bothG).length) ≤ _
omega
end CNFEncComplexity.Robson
/- RobsonMemRoute -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def memRouteName (w h base : ℕ) (v : RouteVar h (Fin (memLaneWidth w h))) : ℕ :=
base+(routeLabel h (memLaneWidth w h) v).val
def memRouteTop (w h base : ℕ) : ℕ :=
let B := 2^h * memLaneWidth w h
base+(B+(B+auxCount (memLaneWidth w h) h))
theorem memRouteName_lt (w h base : ℕ) (v : RouteVar h (Fin (memLaneWidth w h))) :
memRouteName w h base v < memRouteTop w h base := by
unfold memRouteName memRouteTop
exact Nat.add_lt_add_left (routeLabel h (memLaneWidth w h) v).isLt _
theorem memRouteName_ge (w h base : ℕ) (v : RouteVar h (Fin (memLaneWidth w h))) :
base ≤ memRouteName w h base v := Nat.le_add_right _ _
theorem memRouteName_inj (w h base : ℕ) : Function.Injective (memRouteName w h base) :=
fun _ _ he => (routeLabel h (memLaneWidth w h)).injective (Fin.ext (Nat.add_left_cancel he))
def memRouteGates (w h base : ℕ) : List Gate :=
(routeGates (List.finRange (memLaneWidth w h)) h).map (RouteGate.named (memRouteName w h base))
theorem memRouteGates_length (w h base : ℕ) :
(memRouteGates w h base).length = (2*h+1)*2^h*memLaneWidth w h := by
simp [memRouteGates,routeGates_length]
def memInputLane (w h base : ℕ) (i : Fin (2^h)) (j : ℕ) : ℕ :=
if hj : j < memLaneWidth w h then
memRouteName w h base (.input ((wireLabel h).symm i) ⟨j,hj⟩)
else base
def memOutputLane (w h base : ℕ) (i : Fin (2^h)) (j : ℕ) : ℕ :=
if hj : j < memLaneWidth w h then
memRouteName w h base (.output ((wireLabel h).symm i) ⟨j,hj⟩)
else base
theorem memOutputLane_lt (w h base : ℕ) (i : Fin (2^h)) (j : ℕ) (hj : j < memLaneWidth w h) :
memOutputLane w h base i j < memRouteTop w h base := by
rw [memOutputLane,dif_pos hj]
exact memRouteName_lt ..
private theorem routeData_congr {a b : Assignment} {x y : ℕ → ℕ} {w : ℕ}
(h : ∀ j < w, a (x j) = b (y j)) :
wireValue a x w = wireValue b y w := by
induction w with
| zero => rfl
| succ w ih => rw [wireValue,wireValue,ih (fun j hj => h j (by omega)),h w (by omega)]
theorem laneTag_congr {a b : Assignment} {x y : ℕ → ℕ} {w h : ℕ}
(he : ∀ j < memLaneWidth w h, a (x j) = b (y j)) :
laneTag a w h x = laneTag b w h y := by
have h0 : a (x 0) = b (y 0) := he _ (by unfold memLaneWidth; omega)
have hTime : wireValue a (laneTime x) h = wireValue b (laneTime y) h := by
apply routeData_congr
intro j hj
exact he (1+j) (by unfold memLaneWidth; omega)
have hAddr : wireValue a (laneAddress h x) w = wireValue b (laneAddress h y) w := by
apply routeData_congr
intro j hj
exact he (1+h+j) (by unfold memLaneWidth; omega)
have hB : memoryOpt a (laneBeforeFlag w h x) (laneBefore w h x) w =
memoryOpt b (laneBeforeFlag w h y) (laneBefore w h y) w := by
have hk : a (x (1+h+w)) = b (y (1+h+w)) := he _ (by unfold memLaneWidth; omega)
have hv : wireValue a (laneBefore w h x) w = wireValue b (laneBefore w h y) w := by
apply routeData_congr
intro j hj
exact he (1+h+w+1+j) (by unfold memLaneWidth; omega)
simp only [memoryOpt,laneBeforeFlag,hk,hv,eq_self] <;> rfl
have hA : memoryOpt a (laneAfterFlag w h x) (laneAfter w h x) w =
memoryOpt b (laneAfterFlag w h y) (laneAfter w h y) w := by
have hk : a (x (1+h+w+(1+w))) = b (y (1+h+w+(1+w))) := he _ (by unfold memLaneWidth; omega)
have hv : wireValue a (laneAfter w h x) w = wireValue b (laneAfter w h y) w := by
apply routeData_congr
intro j hj
exact he (1+h+w+(1+w)+1+j) (by unfold memLaneWidth; omega)
simp only [memoryOpt,laneAfterFlag,hk,hv,eq_self] <;> rfl
simp only [laneTag,laneRecord,laneActive,h0,hTime,hAddr,hB,hA,eq_self] <;> rfl
private theorem finPerm_ofFn {d : ℕ} (σ : Fin d ≃ Fin d) :
(List.ofFn σ).Perm (List.ofFn (id : Fin d → Fin d)) := by
classical
have ha : (List.ofFn σ).Nodup := List.nodup_ofFn.mpr σ.injective
have hb : (List.ofFn (id : Fin d → Fin d)).Nodup := List.nodup_ofFn.mpr Function.injective_id
apply List.perm_iff_count.mpr
intro j
rw [ha.count,hb.count]
have hj : j ∈ List.ofFn σ := List.mem_ofFn.mpr ⟨σ.symm j,σ.apply_symm_apply j⟩
have hj' : j ∈ List.ofFn (id : Fin d → Fin d) := List.mem_ofFn.mpr ⟨j,rfl⟩
simp [hj,hj']
theorem ofFn_perm_comp {d : ℕ} {X : Type} (f : Fin d → X) (σ : Fin d ≃ Fin d) :
(List.ofFn fun j => f (σ j)).Perm (List.ofFn f) := by
have h := (finPerm_ofFn σ).map f
simp only [List.map_ofFn] at h
exact h
theorem memRoute_rows_perm (w h base : ℕ) (a : Assignment)
(hG : ∀ g ∈ memRouteGates w h base, g.Holds a) :
(List.ofFn fun i => laneTag a w h (memOutputLane w h base i)).Perm
(List.ofFn fun i => laneTag a w h (memInputLane w h base i)) := by
have hValid : ∀ g ∈ routeGates (List.finRange (memLaneWidth w h)) h,
g.Valid (a ∘ memRouteName w h base) := by
intro g hg
exact (g.named_correct _ _).mp (hG _ (List.mem_map.mpr ⟨g,hg,rfl⟩))
obtain ⟨setting,hRoute⟩ := routeGates_sound h (a ∘ memRouteName w h base) hValid
let σ := ((wireLabel h).symm.trans (routing h setting)).trans (wireLabel h)
have hLane (i : Fin (2^h)) :
laneTag a w h (memOutputLane w h base (σ i)) = laneTag a w h (memInputLane w h base i) := by
apply laneTag_congr
intro j hj
simp only [memOutputLane,memInputLane,dif_pos hj,σ,Equiv.trans_apply,Equiv.symm_apply_apply]
exact hRoute ((wireLabel h).symm i) ⟨j,hj⟩ (by simp)
refine ((ofFn_perm_comp (fun i => laneTag a w h (memOutputLane w h base i)) σ).symm.trans ?_)
rw [show (fun j => laneTag a w h (memOutputLane w h base (σ j))) =
(fun i => laneTag a w h (memInputLane w h base i)) from funext hLane]
def sourceBitIndex (h j : ℕ) : ℕ := if j = 0 then 0 else j-h
/-- Link each packed network input to a chronological untagged lane. The missing
timestamp bits are pinned to their physical lane indices. -/
def laneAttachGate (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ)
(i : Fin (2^h)) (j : ℕ) : Gate :=
if 0 < j ∧ j ≤ h then .pin (memInputLane w h base i j) (i.val.testBit (j-1))
else .copy (memInputLane w h base i j) (src i (sourceBitIndex h j))
def attachRows (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) : List Gate :=
(List.finRange (2^h)).flatMap (fun i => (List.range (memLaneWidth w h)).map (laneAttachGate w h base src i))
theorem attachRows_length (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) :
(attachRows w h base src).length = 2^h * memLaneWidth w h := by
simp [attachRows,List.length_flatMap,List.map_const,List.sum_replicate]
def routeInBits (w h : ℕ) (src : Fin (2^h) → ℕ → ℕ) (a : Assignment)
(i : Fin (2^h)) (j : ℕ) : Bool :=
if 0 < j ∧ j ≤ h then i.val.testBit (j-1)
else a (src i (sourceBitIndex h j))
theorem attachRows_exact (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) (a : Assignment) :
(∀ g ∈ attachRows w h base src, g.Holds a) ↔
∀ (i : Fin (2^h)) (j : ℕ), j < memLaneWidth w h →
a (memInputLane w h base i j) = routeInBits w h src a i j := by
unfold attachRows
have hF (i : Fin (2^h)) (j : ℕ) :
(laneAttachGate w h base src i j).Holds a ↔
a (memInputLane w h base i j) = routeInBits w h src a i j := by
unfold laneAttachGate routeInBits
split <;> rfl
simp only [List.forall_mem_flatMap,List.forall_mem_map,List.mem_range,hF,List.mem_finRange,true_implies]
private theorem wireTime_testBit {h : ℕ} (i : Fin (2^h)) (key : ℕ → ℕ) (a : Assignment)
(he : ∀ j < h, a (key j) = i.val.testBit j) : wireValue a key h = i.val := by
rw [wireValue_eq_bitString]
have hp : (fun j : Fin h => a (key j.val)) = (Cslib.BitString.equivFin h).symm i := by
funext j
rw [Cslib.BitString.equivFin_symm_apply]
exact he _ j.isLt
rw [hp,Equiv.apply_symm_apply]
theorem attachedLane_tag {w h : ℕ} (src x : ℕ → ℕ) (a : Assignment)
(q : Fin (2^h)) (he : ∀ j < memLaneWidth w h, a (x j) =
routeInBits w h (fun _ => src) a q j) :
laneTag a w h x = (laneRecord a w 0 src,q.val) := by
have hz : a (x 0) = a (src 0) := by
simpa [routeInBits,sourceBitIndex] using he 0 (by unfold memLaneWidth; omega)
have hb (j : ℕ) (hj : 0 < j) (hk : j < memLaneWidth w 0) :
a (x (h+j)) = a (src j) := by
have hL : h+j < memLaneWidth w h := by unfold memLaneWidth at *; omega
have hh : ¬ ((0 < h+j) ∧ h+j ≤ h) := by omega
have hn : h+j ≠ 0 := by omega
have hE := he (h+j) hL
rw [routeInBits,if_neg hh,sourceBitIndex,if_neg hn,Nat.add_sub_cancel_left] at hE
exact hE
have hAddr : wireValue a (laneAddress h x) w = wireValue a (laneAddress 0 src) w := by
apply routeData_congr
intro j hj
have ho : 1+h+j = h+(1+0+j) := by omega
simp only [laneAddress,ho]
exact hb _ (by omega) (by unfold memLaneWidth; omega)
have hBefore : memoryOpt a (laneBeforeFlag w h x) (laneBefore w h x) w =
memoryOpt a (laneBeforeFlag w 0 src) (laneBefore w 0 src) w := by
have hp : a (x (1+h+w)) = a (src (1+0+w)) := by
rw [show 1+h+w = h+(1+0+w) by omega]
exact hb _ (by omega) (by unfold memLaneWidth; omega)
have hv : wireValue a (laneBefore w h x) w = wireValue a (laneBefore w 0 src) w := by
apply routeData_congr
intro j hj
simp only [laneBefore,show 1+h+w+1+j = h+(1+0+w+1+j) by omega]
exact hb _ (by omega) (by unfold memLaneWidth; omega)
simp only [memoryOpt,laneBeforeFlag,hp,hv,eq_self] <;> rfl
have hAfter : memoryOpt a (laneAfterFlag w h x) (laneAfter w h x) w =
memoryOpt a (laneAfterFlag w 0 src) (laneAfter w 0 src) w := by
have hp : a (x (1+h+w+(1+w))) = a (src (1+0+w+(1+w))) := by
rw [show 1+h+w+(1+w) = h+(1+0+w+(1+w)) by omega]
exact hb _ (by omega) (by unfold memLaneWidth; omega)
have hv : wireValue a (laneAfter w h x) w = wireValue a (laneAfter w 0 src) w := by
apply routeData_congr
intro j hj
simp only [laneAfter,show 1+h+w+(1+w)+1+j = h+(1+0+w+(1+w)+1+j) by omega]
exact hb _ (by omega) (by unfold memLaneWidth; omega)
simp only [memoryOpt,laneAfterFlag,hp,hv,eq_self] <;> rfl
have ht : wireValue a (laneTime x) h = q.val := by
apply wireTime_testBit
intro j hj
have hJ : 1+j < memLaneWidth w h := by unfold memLaneWidth; omega
simpa [laneTime,routeInBits,show 1+j ≤ h by omega,Nat.add_sub_cancel_left] using he (1+j) hJ
simp only [laneTag,laneRecord,laneActive,hz,hAddr,hBefore,hAfter,ht,eq_self] <;> rfl
def untaggedRows (w h : ℕ) (src : Fin (2^h) → ℕ → ℕ) (a : Assignment) : List (Option LocalRecord) :=
List.ofFn fun i => laneRecord a w 0 (src i)
theorem attachedRows_tags (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) (a : Assignment)
(hA : ∀ g ∈ attachRows w h base src, g.Holds a) :
(List.ofFn fun i => laneTag a w h (memInputLane w h base i)) = (untaggedRows w h src a).zipIdx := by
have hh (i : Fin (2^h)) :
laneTag a w h (memInputLane w h base i) = (laneRecord a w 0 (src i),i.val) :=
attachedLane_tag (src i) _ a i ((attachRows_exact ..).mp hA i)
rw [show (fun i => laneTag a w h (memInputLane w h base i)) =
(fun i => (laneRecord a w 0 (src i),i.val)) from funext hh]
apply List.ext_getElem
· simp [untaggedRows]
· intro i hi hj
rw [List.getElem_ofFn,List.getElem_zipIdx]
simp [untaggedRows,List.getElem_ofFn]
end CNFEncComplexity.Robson
/- RobsonMemGroup -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def memEdgeCount (h : ℕ) : ℕ := 2^h-1
def memEdgeStride (w h : ℕ) : ℕ := 4*(h+w)+2+4*w+2
def memEdgeBase (w h base : ℕ) (i : Fin (memEdgeCount h)) : ℕ :=
memRouteTop w h base + i.val*memEdgeStride w h
def memGroupTop (w h base : ℕ) : ℕ := memRouteTop w h base + memEdgeCount h*memEdgeStride w h
def memFirstIx (h : ℕ) : Fin (2^h) := ⟨0,by positivity⟩
def memEdgeLeft {h : ℕ} (i : Fin (memEdgeCount h)) : Fin (2^h) :=
⟨i.val,by have hh := i.isLt; unfold memEdgeCount at hh; omega⟩
def memEdgeRight {h : ℕ} (i : Fin (memEdgeCount h)) : Fin (2^h) :=
⟨i.val+1,by have hh := i.isLt; unfold memEdgeCount at hh; omega⟩
def outputChecks (tier : Option ℕ) (w h base : ℕ) : List Gate :=
laneInit tier w h (memOutputLane w h base (memFirstIx h)) ++
(List.finRange (memEdgeCount h)).flatMap (fun i =>
lanePair tier w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i)))
def memSortedRows (w h base : ℕ) (a : Assignment) : List (Option LocalRecord × ℕ) :=
List.ofFn fun i => laneTag a w h (memOutputLane w h base i)
private theorem chain_slotTagged (xs : List (Option LocalRecord × ℕ)) :
xs.IsChain slotTaggedLE ↔ xs.Pairwise slotTaggedLE := by
letI : Trans slotTaggedLE slotTaggedLE slotTaggedLE :=
⟨fun {a b c} => slotTaggedLE_trans a b c⟩
exact List.isChain_iff_pairwise
private theorem memOutputOrder {h : ℕ} {A : Type} (R : A → A → Prop) (f : Fin (2^h) → A) :
(List.ofFn f).IsChain R ↔
∀ i : Fin (memEdgeCount h), R (f (memEdgeLeft i)) (f (memEdgeRight i)) := by
rw [List.isChain_iff_getElem]
constructor
· intro hh i
have hi : i.val+1 < (List.ofFn f).length := by
rw [List.length_ofFn]
exact (memEdgeRight i).isLt
simpa only [List.getElem_ofFn,memEdgeLeft,memEdgeRight] using hh i.val hi
· intro hh i hi
have hi' : i < memEdgeCount h := by simp only [List.length_ofFn] at hi; unfold memEdgeCount; omega
simpa only [List.getElem_ofFn,memEdgeLeft,memEdgeRight] using hh ⟨i,hi'⟩
theorem outputChecks_exact (tier : Option ℕ) (w h base : ℕ) (a : Assignment)
(hc : ∀ i : Fin (memEdgeCount h), ∀ g ∈ lanePairComparators w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i)), g.Holds a) :
(∀ g ∈ outputChecks tier w h base, g.Holds a) ↔
(memSortedRows w h base a).Pairwise slotTaggedLE ∧
slotsAdjacent (groupInitial tier) (memSortedRows w h base a) := by
unfold outputChecks slotsAdjacent memSortedRows
simp only [List.forall_mem_append,List.forall_mem_flatMap,List.mem_finRange,true_implies,
lanePair,laneInit_exact,← chain_slotTagged,memOutputOrder]
have hHead : ((List.ofFn fun i => laneTag a w h (memOutputLane w h base i)).head?.bind Prod.fst) =
laneRecord a w h (memOutputLane w h base (memFirstIx h)) := by
rw [List.head?_eq_getElem?]
rw [List.getElem?_eq_getElem (by simp [List.length_ofFn,Nat.pow_pos (by decide : 0 < (2:ℕ))])]
simp only [List.getElem_ofFn,Option.bind_some,laneTag,memFirstIx]
rw [hHead]
constructor
· rintro ⟨hI,hP⟩
have hQ (i : Fin (memEdgeCount h)) := (lanePairChecks_exact a tier w h (memEdgeBase w h base i)
_ _ (hc i)).mp (hP i).2
exact ⟨fun i => (hQ i).1,hI,fun i => (hQ i).2⟩
· rintro ⟨hR,hI,hB⟩
exact ⟨hI,fun i => ⟨hc i,(lanePairChecks_exact a tier w h (memEdgeBase w h base i)
_ _ (hc i)).mpr ⟨hR i,hB i⟩⟩⟩
def memSortGates (tier : Option ℕ) (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) : List Gate :=
attachRows w h base src ++ memRouteGates w h base ++ outputChecks tier w h base
theorem memSortGates_sound (tier : Option ℕ) (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ)
(a : Assignment) (hSat : ∀ g ∈ memSortGates tier w h base src, g.Holds a) :
OptionalCertificate (groupInitial tier) (untaggedRows w h src a) := by
rw [memSortGates,List.forall_mem_append,List.forall_mem_append] at hSat
have hPerm := memRoute_rows_perm w h base a hSat.1.2
rw [attachedRows_tags w h base src a hSat.1.1] at hPerm
have hc (i : Fin (memEdgeCount h)) :
∀ g ∈ lanePairComparators w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i)), g.Holds a := by
intro g hg
apply hSat.2
unfold outputChecks
refine List.mem_append.mpr (.inr (List.mem_flatMap.mpr ⟨i,by simp,?_⟩))
exact List.mem_append.mpr (.inl hg)
exact ⟨memSortedRows w h base a,hPerm,(outputChecks_exact tier w h base a hc).mp hSat.2⟩
theorem outputChecks_length (tier : Option ℕ) (w h base : ℕ) :
(outputChecks tier w h base).length ≤ (4+24*w) + memEdgeCount h*(4*h+648*w+134) := by
unfold outputChecks
rw [List.length_append,List.length_flatMap]
apply Nat.add_le_add (laneInit_length ..)
have hw (is : List (Fin (memEdgeCount h))) :
(is.map (fun i => (lanePair tier w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i))).length)).sum ≤
is.length*(4*h+648*w+134) := by
induction is with
| nil => simp
| cons i is ih =>
have hi := lanePair_length tier w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i))
rw [List.map_cons,List.sum_cons,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
simpa using hw (List.finRange (memEdgeCount h))
theorem memSortGates_length (tier : Option ℕ) (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) :
(memSortGates tier w h base src).length ≤
2^h*((2*h+2)*memLaneWidth w h+4*h+672*w+138) := by
have hB : 1 ≤ (2:ℕ)^h := Nat.pow_pos (by decide)
have hA := outputChecks_length tier w h base
have hC : memEdgeCount h*(4*h+648*w+134) ≤ 2^h*(4*h+648*w+134) :=
Nat.mul_le_mul_right _ (Nat.sub_le _ _)
have hD : 4+24*w ≤ 2^h*(4+24*w) := by
simpa using Nat.mul_le_mul_right (4+24*w) hB
unfold memSortGates
rw [List.length_append,List.length_append,attachRows_length,memRouteGates_length]
calc
_ ≤ 2^h * memLaneWidth w h + (2*h+1)*2^h*memLaneWidth w h +
(2^h*(4+24*w)+2^h*(4*h+648*w+134)) := by omega
_ = _ := by ring
/-- Height is at most the tier bit width plus two, including two endpoint snapshots.
This form is designed for summing the tier costs without an additional logarithm. -/
theorem memSortGates_length_small (tier : Option ℕ) (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ)
(hW : 0 < w) (hh : h ≤ w+2) :
(memSortGates tier w h base src).length ≤ 1024*(2^h)*w*w := by
refine (memSortGates_length tier w h base src).trans ?_
have hB : memLaneWidth w h ≤ 9*w := by unfold memLaneWidth; omega
have hF : 2*h+2 ≤ 8*w := by omega
have hP : (2*h+2)*memLaneWidth w h ≤ 8*w*(9*w) := Nat.mul_le_mul hF hB
have hT : 4*h+672*w+138 ≤ 823*w := by omega
have hw : w ≤ w*w := by simpa using Nat.mul_le_mul_right w hW
calc
_ ≤ 2^h*(8*w*(9*w)+823*w) := Nat.mul_le_mul_left _ (by omega)
_ ≤ 2^h*(8*w*(9*w)+823*(w*w)) := Nat.mul_le_mul_left _ (Nat.add_le_add_left (Nat.mul_le_mul_left _ hw) _)
_ ≤ _ := by
have hEq : 2^h*(8*w*(9*w)+823*(w*w)) = 895*(2^h*w*w) := by ring
rw [hEq,show 1024*(2:ℕ)^h*w*w = 1024*(2^h*w*w) by ring]
exact Nat.mul_le_mul_right _ (by decide)
end CNFEncComplexity.Robson
/- RobsonMemRouteGeneric -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem allFinPerm_ofFn {d : ℕ} (σ : Fin d ≃ Fin d) :
(List.ofFn σ).Perm (List.ofFn (id : Fin d → Fin d)) := by
classical
have ha : (List.ofFn σ).Nodup := List.nodup_ofFn.mpr σ.injective
have hb : (List.ofFn (id : Fin d → Fin d)).Nodup := List.nodup_ofFn.mpr Function.injective_id
apply List.perm_iff_count.mpr
intro j
rw [ha.count,hb.count]
have hj : j ∈ List.ofFn σ := List.mem_ofFn.mpr ⟨σ.symm j,σ.apply_symm_apply j⟩
have hj' : j ∈ List.ofFn (id : Fin d → Fin d) := List.mem_ofFn.mpr ⟨j,rfl⟩
simp [hj,hj']
theorem bitRows_perm_comp {d : ℕ} {X : Type} (f : Fin d → X) (σ : Fin d ≃ Fin d) :
(List.ofFn fun j => f (σ j)).Perm (List.ofFn f) := by
have h := (allFinPerm_ofFn σ).map f
simp only [List.map_ofFn] at h
exact h
def routeNamedGates {h d : ℕ} (name : RouteVar h (Fin d) → ℕ) : List Gate :=
(routeGates (List.finRange d) h).map (RouteGate.named name)
theorem routeNamedGates_length {h d : ℕ} (name : RouteVar h (Fin d) → ℕ) :
(routeNamedGates name).length = (2*h+1)*2^h*d := by
simp [routeNamedGates,routeGates_length]
theorem routeNamedGates_perm {h d : ℕ} {X : Type} (name : RouteVar h (Fin d) → ℕ)
(read : (Fin d → Bool) → X) (a : Assignment)
(hValid : ∀ g ∈ routeNamedGates name, g.Holds a) :
(List.ofFn fun i : Fin (2^h) => read (fun j => a (name (.output ((wireLabel h).symm i) j)))).Perm
(List.ofFn fun i : Fin (2^h) => read (fun j => a (name (.input ((wireLabel h).symm i) j)))) := by
have hv : ∀ g ∈ routeGates (List.finRange d) h, g.Valid (a ∘ name) := by
intro g hg
exact (g.named_correct _ _).mp (hValid _ (List.mem_map.mpr ⟨g,hg,rfl⟩))
obtain ⟨s,hs⟩ := routeGates_sound h (a ∘ name) hv
let σ := ((wireLabel h).symm.trans (routing h s)).trans (wireLabel h)
let L (i : Fin (2^h)) := read (fun j => a (name (.output ((wireLabel h).symm i) j)))
let R (i : Fin (2^h)) := read (fun j => a (name (.input ((wireLabel h).symm i) j)))
have he : (fun i => L (σ i)) = R := by
funext i
apply congrArg read
funext j
simp only [L,R,σ,Equiv.trans_apply,Equiv.symm_apply_apply,id_eq]
exact hs _ _ (by simp)
exact (bitRows_perm_comp L σ).symm.trans (he ▸ List.Perm.refl _)
theorem routeNamedGates_extend {h d : ℕ} (name : RouteVar h (Fin d) → ℕ)
(hn : Function.Injective name) (a : Assignment) (input : Fin (2^h) → Fin d → Bool)
(σ : Fin (2^h) ≃ Fin (2^h)) :
∃ b : Assignment,
(∀ k, (∀ r, name r ≠ k) → b k = a k) ∧
(∀ g ∈ routeNamedGates name, g.Holds b) ∧
(∀ i j, b (name (.input ((wireLabel h).symm i) j)) = input i j) ∧
(∀ i j, b (name (.output ((wireLabel h).symm (σ i)) j)) = input i j) := by
let perm := ((wireLabel h).trans σ).trans (wireLabel h).symm
obtain ⟨s,hs⟩ := routing_universal h perm
obtain ⟨v,hg,hI,hO⟩ := routeGates_complete (List.finRange d) h s
(fun i j => input ((wireLabel h) i) j)
classical
let b : Assignment := Function.extend name v a
have he : b ∘ name = v := Function.extend_comp hn v a
refine ⟨b,?_,?_,?_,?_⟩
· intro k h
unfold b
rw [Function.extend_def,dif_neg]
rintro ⟨r,hr⟩
exact h r hr
· intro g h
obtain ⟨r,hr,rfl⟩ := List.mem_map.mp h
exact (r.named_correct name b).mpr (by rw [he]; exact hg r hr)
· intro i j
have hB := (congrFun he (.input ((wireLabel h).symm i) j)).trans (hI _ _)
simpa using hB
· intro i j
have hR := hO ((wireLabel h).symm i) j (by simp)
rw [hs] at hR
simpa [perm,Function.comp_def] using
(congrFun he (.output (perm ((wireLabel h).symm i)) j)).trans hR
end CNFEncComplexity.Robson
/- RobsonMemComplete -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem sourceBitIndex_lt {w h j : ℕ} (hj : j < memLaneWidth w h)
(hn : ¬ (0 < j ∧ j ≤ h)) : sourceBitIndex h j < memLaneWidth w 0 := by
by_cases hz : j = 0
· simp only [sourceBitIndex,hz,if_true,memLaneWidth]
omega
· rw [sourceBitIndex,if_neg hz]
unfold memLaneWidth at *
omega
theorem untaggedRows_congr {w h : ℕ} {src : Fin (2^h) → ℕ → ℕ} {a b : Assignment}
(ha : ∀ i j, j < memLaneWidth w 0 → a (src i j) = b (src i j)) :
untaggedRows w h src a = untaggedRows w h src b := by
apply congrArg List.ofFn
funext i
exact congrArg Prod.fst (laneTag_congr (ha i))
private theorem zipIdx_eq_ofFn {X : Type} {n : ℕ} (f : Fin n → X) :
(List.ofFn f).zipIdx = List.ofFn (fun i => (f i,i.val)) := by
apply List.ext_getElem
· simp
· intro i hi hj
simp only [List.getElem_zipIdx,List.getElem_ofFn,Nat.zero_add]
/-- Sorting tagged rows is a permutation of fixed chronological indices, even
when several untagged rows are identical. -/
theorem sorted_rows_index {n : ℕ} {X : Type} {values : Fin n → X} {rows : List (X × ℕ)}
(hp : rows.Perm (List.ofFn values).zipIdx) :
∃ σ : Fin n ≃ Fin n, rows = List.ofFn (fun i => (values (σ i),(σ i).val)) := by
have hLen : rows.length = n := by simpa using hp.length_eq
have hMem (i : Fin n) : rows[i.val]'(by simpa [hLen] using i.isLt) ∈ (List.ofFn values).zipIdx :=
hp.mem_iff.mp (List.getElem_mem _)
let r (i : Fin n) := rows[i.val]'(by simpa [hLen] using i.isLt)
let f (i : Fin n) : Fin n := ⟨(r i).2,by
obtain ⟨_,ht,_⟩ := List.mem_zipIdx (show ((r i).1,(r i).2) ∈ (List.ofFn values).zipIdx from hMem i)
simpa using ht⟩
have hN : (rows.map Prod.snd).Nodup := by
apply (hp.map Prod.snd).nodup_iff.mpr
rw [zipIdx_eq_ofFn,List.map_ofFn]
apply List.nodup_ofFn.mpr
intro i j hj
exact Fin.ext hj
have hinj : Function.Injective f := by
intro i j h
have hI : i.val < (rows.map Prod.snd).length := by simp [hLen,i.isLt]
have hJ : j.val < (rows.map Prod.snd).length := by simp [hLen,j.isLt]
have hEq : (rows.map Prod.snd)[i.val] = (rows.map Prod.snd)[j.val] := by
simp only [List.getElem_map]
exact congrArg Fin.val h
exact Fin.ext ((List.getElem_inj hN).mp hEq)
let σ := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hinj)
refine ⟨σ,?_⟩
apply List.ext_getElem (by simpa using hLen)
intro i hi hj
let j : Fin n := ⟨i,by simpa [hLen] using hi⟩
have hh := (List.mem_zipIdx
(show ((r j).1,(r j).2) ∈ (List.ofFn values).zipIdx from hMem j)).2.2
rw [List.getElem_ofFn]
apply Prod.ext
· simpa [σ,f,r,List.getElem_ofFn] using hh
· rfl
theorem memRoute_reorders (w h base : ℕ) (src : Fin (2^h) → ℕ → ℕ) (a : Assignment)
(hSrc : ∀ i j, j < memLaneWidth w 0 → src i j < base)
(σ : Fin (2^h) ≃ Fin (2^h)) :
∃ b : Assignment,
(∀ k, (k < base ∨ memRouteTop w h base ≤ k) → b k = a k) ∧
(∀ g ∈ attachRows w h base src, g.Holds b) ∧
(∀ g ∈ memRouteGates w h base, g.Holds b) ∧
memSortedRows w h base b = List.ofFn (fun i => (laneRecord a w 0 (src (σ i)),(σ i).val)) := by
let inp (i : Fin (2^h)) (j : Fin (memLaneWidth w h)) := routeInBits w h src a i j.val
obtain ⟨b,hb,hg,hI,hO⟩ := routeNamedGates_extend (memRouteName w h base)
(memRouteName_inj w h base) a inp σ.symm
have hAgree (k : ℕ) (hk : k < base ∨ memRouteTop w h base ≤ k) : b k = a k := by
apply hb k
intro r he
have hG := memRouteName_ge w h base r
have hL := memRouteName_lt w h base r
omega
have hInAgree (i : Fin (2^h)) (j : ℕ) (hj : j < memLaneWidth w h) :
routeInBits w h src b i j = routeInBits w h src a i j := by
unfold routeInBits
split
· rfl
· rename_i hn
exact hAgree _ (.inl (hSrc _ _ (sourceBitIndex_lt hj hn)))
refine ⟨b,hAgree,(attachRows_exact ..).2 ?_,hg,?_⟩
· intro i j hj
rw [hInAgree i j hj,memInputLane,dif_pos hj]
exact hI i ⟨j,hj⟩
· unfold memSortedRows
apply congrArg List.ofFn
funext i
have hBits (j : ℕ) (hj : j < memLaneWidth w h) :
b (memOutputLane w h base i j) = routeInBits w h (fun _ => src (σ i)) b (σ i) j := by
change _ = routeInBits w h src b (σ i) j
rw [hInAgree _ _ hj,memOutputLane,dif_pos hj,← σ.symm_apply_apply i]
have h := hO (σ i) ⟨j,hj⟩
rw [σ.symm_apply_apply] at h
simpa [inp] using h
have he := attachedLane_tag (src (σ i)) _ b (σ i) hBits
have hRec : laneRecord b w 0 (src (σ i)) = laneRecord a w 0 (src (σ i)) :=
congrArg Prod.fst (laneTag_congr (fun j hj => hAgree _ (.inl (hSrc _ _ hj))))
rw [he,hRec]
private theorem laneKey_name_lt {w h base : ℕ} (x : ℕ → ℕ)
(hx : ∀ j < memLaneWidth w h, x j < base) :
∀ j < h+w, laneKey h x j < base := by
intro j hj
unfold laneKey joinKey
split
· unfold laneTime
apply hx
unfold memLaneWidth
omega
· unfold laneAddress
apply hx
unfold memLaneWidth
omega
private theorem laneAddress_name_lt {w h base : ℕ} (x : ℕ → ℕ)
(hx : ∀ j < memLaneWidth w h, x j < base) :
∀ j < w, laneAddress h x j < base := by
intro j hj
apply hx
unfold memLaneWidth
omega
theorem lanePairComparators_names (w h base low : ℕ) (l r : ℕ → ℕ)
(hLow : low ≤ base)
(hL : ∀ j < memLaneWidth w h, l j < low) (hR : ∀ j < memLaneWidth w h, r j < low) :
∀ g ∈ lanePairComparators w h base l r,
∀ k ∈ g.names, k < low ∨ (base ≤ k ∧ k < laneCmpEnd w h base) := by
have h1 : ∀ g ∈ compareCircuit base (h+w) (laneKey h r) (laneKey h l),
∀ k ∈ g.names, k < low ∨ (base ≤ k ∧ k < laneCmpEnd w h base) := by
intro g hg k hk
change k ∈ Gate.names g at hk
have hn := compareCircuit_names_lt base (h+w) (laneKey h r) (laneKey h l)
(fun j hj => (laneKey_name_lt r hR j hj).trans_le hLow)
(fun j hj => (laneKey_name_lt l hL j hj).trans_le hLow) g hg k hk
have hL' := laneKey_name_lt l hL
have hR' := laneKey_name_lt r hR
rcases List.mem_append.mp hg with hm|hm
· simp only [List.mem_cons,List.not_mem_nil,or_false] at hm
rcases hm with rfl|rfl <;> simp [Gate.names,ltWire,eqWire] at hk <;>
unfold laneCmpEnd laneCmpBase <;> omega
· obtain ⟨j,hj,rflG⟩ := List.mem_flatMap.mp hm
obtain hJ := List.mem_range.mp hj
specialize hL' j hJ
specialize hR' j hJ
simp only [compareStep,List.mem_cons,List.not_mem_nil,or_false] at rflG
rcases rflG with rfl|rfl|rfl|rfl <;> simp [Gate.names,ltWire,eqWire,diffWire,sameWire] at hk <;>
unfold laneCmpEnd laneCmpBase <;> omega
have h2 : ∀ g ∈ compareCircuit (laneCmpBase w h base) w (laneAddress h l) (laneAddress h r),
∀ k ∈ g.names, k < low ∨ (base ≤ k ∧ k < laneCmpEnd w h base) := by
intro g hg k hk
change k ∈ Gate.names g at hk
have hh : low ≤ laneCmpBase w h base := by unfold laneCmpBase; omega
have hn := compareCircuit_names_lt (laneCmpBase w h base) w (laneAddress h l) (laneAddress h r)
(fun j hj => (laneAddress_name_lt l hL j hj).trans_le hh)
(fun j hj => (laneAddress_name_lt r hR j hj).trans_le hh) g hg k hk
have hL' := laneAddress_name_lt l hL
have hR' := laneAddress_name_lt r hR
rcases List.mem_append.mp hg with hm|hm
· simp only [List.mem_cons,List.not_mem_nil,or_false] at hm
rcases hm with rfl|rfl <;> simp [Gate.names,ltWire,eqWire] at hk <;>
unfold laneCmpEnd laneCmpBase at * <;> omega
· obtain ⟨j,hj,rflG⟩ := List.mem_flatMap.mp hm
obtain hJ := List.mem_range.mp hj
specialize hL' j hJ
specialize hR' j hJ
simp only [compareStep,List.mem_cons,List.not_mem_nil,or_false] at rflG
rcases rflG with rfl|rfl|rfl|rfl <;> simp [Gate.names,ltWire,eqWire,diffWire,sameWire] at hk <;>
unfold laneCmpEnd laneCmpBase at * <;> omega
rw [lanePairComparators]
intro g hg
cases List.mem_append.mp hg
· exact h1 g ‹_›
· exact h2 g ‹_›
theorem lanePairComparators_extend (w h base : ℕ) (l r : ℕ → ℕ) (a : Assignment)
(hL : ∀ j < memLaneWidth w h, l j < base) (hR : ∀ j < memLaneWidth w h, r j < base) :
∃ b : Assignment, (∀ k, (k < base ∨ laneCmpEnd w h base ≤ k) → b k = a k) ∧
(∀ g ∈ lanePairComparators w h base l r, g.Holds b) := by
obtain ⟨mid,hMid,h1⟩ := compareCircuit_extends_interval base (h+w) (laneKey h r) (laneKey h l) a
(laneKey_name_lt r hR) (laneKey_name_lt l hL)
let next := laneCmpBase w h base
have hn : base ≤ next := by unfold next laneCmpBase; omega
obtain ⟨b,hB,h2⟩ := compareCircuit_extends_interval next w (laneAddress h l) (laneAddress h r) mid
(fun j hj => (laneAddress_name_lt l hL j hj).trans_le hn)
(fun j hj => (laneAddress_name_lt r hR j hj).trans_le hn)
refine ⟨b,?_,?_⟩
· intro k hk
have hi (j : ℕ) : laneCmpEnd w h base ≤ j → next ≤ j := by
unfold laneCmpEnd next
omega
have e1 : b k = mid k := hB k (hk.elim (fun x => .inl (x.trans_le hn)) .inr)
have e2 : mid k = a k := hMid k (hk.elim .inl (fun e => .inr (hi k e)))
exact e1.trans e2
· rw [lanePairComparators,List.forall_mem_append]
refine ⟨?_,h2⟩
intro g hg
apply (g.holds_congr mid b (fun k hk => ?_)).mp (h1 g hg)
exact (hB k (.inl (compareCircuit_names_lt base (h+w) (laneKey h r) (laneKey h l)
(laneKey_name_lt r hR) (laneKey_name_lt l hL) g hg k hk))).symm
theorem memIndependentGateIntervals {d low width : ℕ} (parts : Fin d → List Gate) (a : Assignment)
(hNames : ∀ i : Fin d, ∀ g ∈ parts i, ∀ k ∈ g.names,
k < low ∨ (low+i.val*width ≤ k ∧ k < low+(i.val+1)*width))
(hParts : ∀ i : Fin d, ∃ b : Assignment,
(∀ k, (k < low+i.val*width ∨ low+(i.val+1)*width ≤ k) → b k = a k) ∧
(∀ g ∈ parts i, g.Holds b)) :
∃ b : Assignment,
(∀ k, k < low ∨ low+d*width ≤ k → b k = a k) ∧
(∀ i : Fin d, ∀ g ∈ parts i, g.Holds b) := by
classical
choose B hB hP using hParts
let F (k : ℕ) : Bool := if h : ∃ i : Fin d, low+i.val*width ≤ k ∧ k < low+(i.val+1)*width
then B (Classical.choose h) k else a k
have hBase (k : ℕ) (hl : k < low ∨ low+d*width ≤ k) : F k = a k := by
unfold F
rw [dif_neg]
rintro ⟨i,hi,hi'⟩
have hn : (i.val+1)*width ≤ d*width := Nat.mul_le_mul_right width (by omega)
omega
refine ⟨F,hBase,fun i g hg => (g.holds_congr (B i) F (fun k hk => ?_)).mp (hP i g hg)⟩
rcases hNames i g hg k hk with hl|⟨h0,h1⟩
· exact (hB i k (.inl (by omega))).trans (hBase k (.inl hl)).symm
· have he : ∃ j : Fin d, low+j.val*width ≤ k ∧ k < low+(j.val+1)*width :=
⟨i,h0,h1⟩
let j := Classical.choose he
have hj : low+j.val*width ≤ k ∧ k < low+(j.val+1)*width := Classical.choose_spec he
have eqIJ : i = j := by
apply Fin.ext
rcases lt_trichotomy i.val j.val with hh|hh|hh
· have hC : (i.val+1)*width ≤ j.val*width := Nat.mul_le_mul_right width (by omega)
omega
· exact hh
· have hC : (j.val+1)*width ≤ i.val*width := Nat.mul_le_mul_right width (by omega)
omega
unfold F
rw [dif_pos he]
change B i k = B j k
rw [eqIJ]
theorem memComparators_extend (w h base : ℕ) (a : Assignment) :
∃ b : Assignment,
(∀ k, k < memRouteTop w h base ∨ memGroupTop w h base ≤ k → b k = a k) ∧
∀ i : Fin (memEdgeCount h), ∀ g ∈ lanePairComparators w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i)), g.Holds b := by
let parts (i : Fin (memEdgeCount h)) :=
lanePairComparators w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i))
have hEnd (i : Fin (memEdgeCount h)) :
laneCmpEnd w h (memEdgeBase w h base i) =
memRouteTop w h base + (i.val+1)*memEdgeStride w h := by
unfold laneCmpEnd laneCmpBase memEdgeBase memEdgeStride
ring
apply memIndependentGateIntervals parts a
· intro i g hg k hk
have ha := lanePairComparators_names w h (memEdgeBase w h base i) (memRouteTop w h base)
_ _ (Nat.le_add_right _ _) (memOutputLane_lt w h base (memEdgeLeft i))
(memOutputLane_lt w h base (memEdgeRight i)) g hg k hk
rw [hEnd] at ha
exact ha
· intro i
have hg (j : Fin (2^h)) (k : ℕ) (hk : k < memLaneWidth w h) :
memOutputLane w h base j k < memEdgeBase w h base i :=
(memOutputLane_lt w h base j k hk).trans_le (Nat.le_add_right _ _)
have ha := lanePairComparators_extend w h (memEdgeBase w h base i) _ _ a (hg (memEdgeLeft i)) (hg (memEdgeRight i))
simp only [hEnd] at ha
exact ha
theorem memSortGates_complete (tier : Option ℕ) (w h base : ℕ)
(src : Fin (2^h) → ℕ → ℕ) (a : Assignment)
(hSrc : ∀ i j, j < memLaneWidth w 0 → src i j < base)
(hC : OptionalCertificate (groupInitial tier) (untaggedRows w h src a)) :
∃ b : Assignment,
(∀ k, (k < base ∨ memGroupTop w h base ≤ k) → b k = a k) ∧
(∀ g ∈ memSortGates tier w h base src, g.Holds b) := by
obtain ⟨rows,perm,order,adj⟩ := hC
obtain ⟨σ,hσ⟩ := sorted_rows_index perm
obtain ⟨mid,hM,hAtt,hRoute,hRows⟩ := memRoute_reorders w h base src a hSrc σ
obtain ⟨b,hB,hG⟩ := memComparators_extend w h base mid
have hTop : base ≤ memRouteTop w h base := Nat.le_add_right _ _
have hLow : memRouteTop w h base ≤ memGroupTop w h base := Nat.le_add_right _ _
have hp (k : ℕ) (hk : k < memRouteTop w h base) : b k = mid k := hB k (.inl hk)
refine ⟨b, ?_, ?_⟩
· intro k hk
rcases hk with hk | hk
· exact (hp k (hk.trans_le hTop)).trans (hM k (.inl hk))
· exact (hB k (.inr hk)).trans (hM k (.inr (hLow.trans hk)))
· rw [memSortGates,List.forall_mem_append,List.forall_mem_append]
refine ⟨⟨?_,?_⟩,?_⟩
· rw [attachRows_exact] at hAtt ⊢
intro i j hj
rw [memInputLane,dif_pos hj,hp _ (memRouteName_lt ..)]
have he : routeInBits w h src b i j = routeInBits w h src mid i j := by
unfold routeInBits
split
· rfl
· rename_i hn
exact hp _ ((hSrc _ _ (sourceBitIndex_lt hj hn)).trans_le hTop)
rw [he]
simpa [memInputLane,hj] using hAtt i j hj
· intro g hg
obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hg
have hRange : b ∘ memRouteName w h base = mid ∘ memRouteName w h base := by
funext r
exact hp _ (memRouteName_lt ..)
rw [r.named_correct,hRange,← r.named_correct]
exact hRoute _ (List.mem_map.mpr ⟨r,hr,rfl⟩)
· apply (outputChecks_exact tier w h base b hG).2
have he : memSortedRows w h base b = memSortedRows w h base mid := by
apply congrArg List.ofFn
funext i
apply laneTag_congr
intro j hj
exact hp _ (memOutputLane_lt w h base i j hj)
rw [he,hRows,← hσ]
exact ⟨order,adj⟩
theorem memSortGates_exact (tier : Option ℕ) (w h base : ℕ)
(src : Fin (2^h) → ℕ → ℕ) (a : Assignment)
(hSrc : ∀ i j, j < memLaneWidth w 0 → src i j < base) :
(∃ b : Assignment,
(∀ k, (k < base ∨ memGroupTop w h base ≤ k) → b k = a k) ∧
(∀ g ∈ memSortGates tier w h base src, g.Holds b)) ↔
OptionalCertificate (groupInitial tier) (untaggedRows w h src a) := by
constructor
· rintro ⟨b,hb,hs⟩
have he : untaggedRows w h src b = untaggedRows w h src a :=
untaggedRows_congr (fun i j hj => hb (src i j) (.inl (hSrc i j hj)))
exact he ▸ memSortGates_sound tier w h base src b hs
· exact memSortGates_complete tier w h base src a hSrc
end CNFEncComplexity.Robson
/- RobsonMemFrame -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- A boundary at index zero is the fixed tier initialization. Every later
boundary reads the same stored value from both incident memory windows. -/
def snapshotPort (tier z o : ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(boundary addr bit : ℕ) : ℕ :=
if boundary = 0 then
if bit = 0 ∧ bitTier addr 0 = tier then o else z
else snap boundary addr bit
def snapshotState (a : Assignment) (w q tier z o : ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(boundary : ℕ) : LocalMemory :=
fun addr => if addr < q then memoryOpt a (snapshotPort tier z o snap boundary addr 0)
(fun i => snapshotPort tier z o snap boundary addr (i+1)) w else none
theorem snapshotState_restricted (a : Assignment) (w q tier z o : ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) (boundary : ℕ) :
LocalMemory.Restricted q (snapshotState a w q tier z o snap boundary) := by
intro addr h
simp [snapshotState,Nat.not_lt.mpr h]
private theorem snapshotWireValue_const_false (a : Assignment) (x : ℕ → ℕ) (w : ℕ)
(he : ∀ i < w, a (x i) = false) : wireValue a x w = 0 := by
induction w with
| zero => rfl
| succ w ih =>
rw [wireValue,ih (fun i hi => he i (by omega)),he w (by omega)]
simp
theorem snapshotState_initial (a : Assignment) (w q tier z o : ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) (hz : a z = false) (ho : a o = true)
(hr : LocalMemory.Restricted q (groupInitial (some tier))) :
snapshotState a w q tier z o snap 0 = groupInitial (some tier) := by
funext addr
by_cases hA : addr < q
· rw [snapshotState,if_pos hA]
have hBits : wireValue a (fun i => snapshotPort tier z o snap 0 addr (i+1)) w = 0 := by
exact snapshotWireValue_const_false _ _ _ (fun i hi => by simp [snapshotPort,hz])
by_cases hT : bitTier addr 0 = tier
· change memoryOpt .. = if tier = bitTier addr 0 then some 0 else none
rw [if_pos hT.symm]
simp [memoryOpt,snapshotPort,hT,ho]
exact snapshotWireValue_const_false _ _ _ (fun _ _ => hz)
· have hN := Ne.symm hT
change memoryOpt .. = if tier = bitTier addr 0 then some 0 else none
rw [if_neg hN]
simp [memoryOpt,snapshotPort,hT,hz]
· rw [snapshotState,if_neg hA,hr addr (Nat.not_lt.mp hA)]
/-- Whole packed row for a boundary snapshot. A beginning row installs the
boundary value and an ending row removes it after verifying the value. -/
def snapshotLane (w tier z o : ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(begin : Bool) (boundary addr bit : ℕ) : ℕ :=
if bit = 0 then o
else if bit ≤ w then (if addr.testBit (bit-1) then o else z)
else if bit < 2+2*w then (if begin then z else
snapshotPort tier z o snap boundary addr (bit-(1+w)))
else (if begin then snapshotPort tier z o snap boundary addr (bit-(2+2*w)) else z)
private theorem snapshotLane_active (w tier z o : ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(begin : Bool) (boundary addr : ℕ) :
laneActive (snapshotLane w tier z o snap begin boundary addr) = o := rfl
private theorem wireValue_testBits (a : Assignment) (key : ℕ → ℕ) (w v : ℕ) (hv : v < 2^w)
(h : ∀ i < w, a (key i) = v.testBit i) : wireValue a key w = v := by
rw [wireValue_eq_bitString]
let V : Fin (2^w) := ⟨v,hv⟩
have he : (fun j : Fin w => a (key j.val)) = (Cslib.BitString.equivFin w).symm V := by
funext j
rw [Cslib.BitString.equivFin_symm_apply]
exact h _ j.isLt
rw [he,Equiv.apply_symm_apply]
theorem snapshotLane_record (a : Assignment) (w tier z o : ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(begin : Bool) (boundary addr : ℕ) (hA : addr < 2^w) (hz : a z=false) (ho : a o=true) :
laneRecord a w 0 (snapshotLane w tier z o snap begin boundary addr) =
if begin then some ⟨addr,none,snapshotState a w (2^w) tier z o snap boundary addr⟩
else some ⟨addr,snapshotState a w (2^w) tier z o snap boundary addr,none⟩ := by
let row := snapshotLane w tier z o snap begin boundary addr
let s := snapshotPort tier z o snap boundary addr
have addrEq : wireValue a (laneAddress 0 row) w = addr := by
apply wireValue_testBits a _ _ _ hA
intro j hj
have h1 : 1+0+j ≠ 0 := by omega
have h2 : 1+0+j ≤ w := by omega
change a (snapshotLane w tier z o snap begin boundary addr (1+0+j)) = addr.testBit j
rw [snapshotLane,if_neg h1,if_pos h2]
have h3 : 1+0+j-1 = j := by omega
rw [h3]
cases h : addr.testBit j <;> simp [h,hz,ho]
have hBefore (j : ℕ) (hj : j ≤ w) :
row (1+w+j) = if begin then z else s j := by
have h1 : 1+w+j ≠ 0 := by omega
have h2 : ¬1+w+j ≤ w := by omega
have h3 : 1+w+j < 2+2*w := by omega
unfold row snapshotLane
rw [if_neg h1,if_neg h2,if_pos h3,Nat.add_sub_cancel_left]
have hAfter (j : ℕ) :
row (2+2*w+j) = if begin then s j else z := by
have h1 : 2+2*w+j ≠ 0 := by omega
have h2 : ¬2+2*w+j ≤ w := by omega
have h3 : ¬2+2*w+j < 2+2*w := by omega
unfold row snapshotLane
rw [if_neg h1,if_neg h2,if_neg h3,Nat.add_sub_cancel_left]
have hb0 : laneBeforeFlag w 0 row = if begin then z else s 0 := by
unfold laneBeforeFlag
simpa using hBefore 0 (Nat.zero_le _)
have ha0 : laneAfterFlag w 0 row = if begin then s 0 else z := by
unfold laneAfterFlag
have hEq : 1+0+w+(1+w) = 2+2*w+0 := by omega
rw [hEq]
exact hAfter 0
have hb1 : wireValue a (laneBefore w 0 row) w =
wireValue a (fun j => if begin then z else s (j+1)) w := by
apply wireValue_key_congr
intro j hj
unfold laneBefore
rw [show 1+0+w+1+j=1+w+(j+1) by omega]
exact hBefore _ (by omega)
have ha1 : wireValue a (laneAfter w 0 row) w =
wireValue a (fun j => if begin then s (j+1) else z) w := by
apply wireValue_key_congr
intro j hj
unfold laneAfter
rw [show 1+0+w+(1+w)+1+j = 2+2*w+(j+1) by omega]
exact hAfter _
change laneRecord a w 0 row = _
simp only [laneRecord,show laneActive row = o from rfl,ho,if_true,addrEq,memoryOpt,hb0,ha0,hb1,ha1,
snapshotState,if_pos hA]
cases begin <;> simp [s,hz]
/-- The split layout uses fixed (q) middle rows. Missing events have false
presence, so a partial final window needs no extra addressing cases. -/
def memoryWindowSource (w tier q R g z o : ℕ) (src : ℕ → ℕ → ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) (i bit : ℕ) : ℕ :=
if R ≤ q then
if i < R then src i bit else z
else if i < q then snapshotLane w tier z o snap true g i bit
else if i < 2*q then
let ix := g*q+(i-q)
if ix < R then src ix bit else z
else if i < 3*q then snapshotLane w tier z o snap false (g+1) (i-2*q) bit
else z
def rawMemoryRows (a : Assignment) (w R : ℕ) (src : ℕ → ℕ → ℕ) : List (Option LocalRecord) :=
(List.range R).map (fun i => laneRecord a w 0 (src i))
def rawMemoryBlock (a : Assignment) (w q R g : ℕ) (src : ℕ → ℕ → ℕ) :
List (Option LocalRecord) :=
(List.range q).map fun i => if g*q+i < R then laneRecord a w 0 (src (g*q+i)) else none
theorem memoryWindow_single (a : Assignment) (w h tier R g z o : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(hz : a z=false) (hs : R ≤ 2^w) (hR : R ≤ 2^h) :
untaggedRows w h (fun i => memoryWindowSource w tier (2^w) R g z o src snap i.val) a =
rawMemoryRows a w R src ++ List.replicate (2^h-R) none := by
apply List.ext_getElem (by simp [untaggedRows,rawMemoryRows]; omega)
intro i hi hi'
have hiN : i < 2^h := by simpa [untaggedRows] using hi
simp only [untaggedRows,List.getElem_ofFn]
by_cases he : i < R
· rw [List.getElem_append_left (by simpa [rawMemoryRows] using he)]
have hKey : memoryWindowSource w tier (2^w) R g z o src snap i = src i := by
funext bit
simp [memoryWindowSource,hs,he]
rw [hKey]
simp [rawMemoryRows,List.getElem_range]
· rw [List.getElem_append_right (by simpa [rawMemoryRows] using Nat.not_lt.mp he),List.getElem_replicate]
simp [memoryWindowSource,hs,he,laneRecord,laneActive,hz]
def frameWindow (a : Assignment) (w tier R g z o : ℕ) (src : ℕ → ℕ → ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) : List (Option LocalRecord) :=
optionFrame (2^w) (snapshotState a w (2^w) tier z o snap g)
(snapshotState a w (2^w) tier z o snap (g+1)) (rawMemoryBlock a w (2^w) R g src)
theorem memoryWindow_split (a : Assignment) (w h tier R g z o : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(hz : a z=false) (ho : a o=true) (hs : ¬ R ≤ 2^w) (hR : 3*2^w ≤ 2^h) :
untaggedRows w h (fun i => memoryWindowSource w tier (2^w) R g z o src snap i.val) a =
frameWindow a w tier R g z o src snap ++ List.replicate (2^h-3*2^w) none := by
let q := 2^w
have hLen : (frameWindow a w tier R g z o src snap).length = 3*q := by
rw [frameWindow,optionFrame_length]
simp [rawMemoryBlock,q]
omega
apply List.ext_getElem (by simp [untaggedRows,hLen]; omega)
intro i hi hi'
simp only [untaggedRows,List.getElem_ofFn]
by_cases he : i < 3*q
· rw [List.getElem_append_left (by simpa only [hLen] using he)]
unfold frameWindow optionFrame
by_cases h0 : i < q
· rw [List.getElem_append_left (by simp [beginSnapshot,q]; omega),
List.getElem_append_left (by simp [beginSnapshot,q]; omega)]
simp only [beginSnapshot,List.getElem_map,List.getElem_range]
have hKey : memoryWindowSource w tier (2^w) R g z o src snap i =
snapshotLane w tier z o snap true g i := by
funext bit
simp [memoryWindowSource,hs,show i < 2^w from h0]
rw [hKey]
exact snapshotLane_record a w tier z o snap true g i (show i < 2^w from h0) hz ho
· by_cases hm : i < 2*q
· rw [List.getElem_append_left (by simp [beginSnapshot,rawMemoryBlock,q]; omega),
List.getElem_append_right (by simpa [beginSnapshot,q] using Nat.not_lt.mp h0)]
simp only [beginSnapshot,List.length_map,List.length_range,rawMemoryBlock,List.getElem_map,List.getElem_range]
by_cases hj : g*q+(i-q) < R
· have hKey : memoryWindowSource w tier (2^w) R g z o src snap i =
src (g*q+(i-q)) := by
funext bit
simp only [memoryWindowSource,if_neg hs,if_neg (show ¬ i < 2^w from h0),
if_pos (show i < 2*2^w from hm),if_pos (show g*2^w+(i-2^w) < R from hj)] <;> rfl
rw [hKey,if_pos (show g*2^w+(i-2^w) < R from hj)]
· simp [memoryWindowSource,hs,q,h0,hm,hj,laneRecord,laneActive,hz]
· rw [List.getElem_append_right (by simp [beginSnapshot,rawMemoryBlock,q] <;> omega)]
simp only [List.length_append,beginSnapshot,List.length_map,List.length_range,rawMemoryBlock,
endSnapshot,List.getElem_map,List.getElem_range]
have hEnd : i-2*q < q := by omega
have hIx : i-(q+q)=i-2*q := by omega
have hKey : memoryWindowSource w tier (2^w) R g z o src snap i =
snapshotLane w tier z o snap false (g+1) (i-2*q) := by
funext bit
simp only [memoryWindowSource,q,if_neg hs,if_neg (show ¬ i < 2^w from h0),
if_neg (show ¬ i < 2*2^w from hm),if_pos (show i < 3*2^w from he)]
rw [hKey]
simpa [q,hIx] using
snapshotLane_record a w tier z o snap false (g+1) (i-2*q) (show i-2*q < 2^w from hEnd) hz ho
· rw [List.getElem_append_right (by simpa only [hLen] using Nat.not_lt.mp he),List.getElem_replicate]
have hq : ¬ i < q := by omega
have hq2 : ¬ i < 2*q := by omega
simp [memoryWindowSource,q,hs,hq,hq2,he,laneRecord,laneActive,hz]
theorem fixedGroups_get {U : Type} (q count : ℕ) (rows : List U) (g : ℕ)
(hg : g < count) :
(fixedGroups q count rows)[g]'(by simpa using hg) = (rows.drop (g*q)).take q := by
induction count generalizing rows g with
| zero => omega
| succ c ih =>
cases g with
| zero => simp [fixedGroups]
| succ g =>
simp only [fixedGroups,List.getElem_cons_succ]
rw [ih (rows.drop q) g (by omega),List.drop_drop,Nat.add_comm q]
congr 2
ring
theorem rawMemoryBlock_eq (a : Assignment) (w q R g : ℕ) (src : ℕ → ℕ → ℕ) :
rawMemoryBlock a w q R g src = ((rawMemoryRows a w R src).drop (g*q)).take q ++
List.replicate (q - min q (R-g*q)) none := by
apply List.ext_getElem (by simp [rawMemoryBlock,rawMemoryRows] <;> omega)
intro i hi hj
have hL : (((rawMemoryRows a w R src).drop (g*q)).take q).length = min q (R-g*q) := by
simp [rawMemoryRows]
simp only [rawMemoryBlock,List.getElem_map,List.getElem_range]
by_cases hI : g*q+i < R
· have hiq : i < q := by simpa [rawMemoryBlock] using hi
have hj' : i < (((rawMemoryRows a w R src).drop (g*q)).take q).length := by rw [hL]; omega
rw [if_pos hI,List.getElem_append_left hj',List.getElem_take,List.getElem_drop]
simp [rawMemoryRows,List.getElem_range]
· have hj' : (((rawMemoryRows a w R src).drop (g*q)).take q).length ≤ i := by
rw [hL]; omega
rw [if_neg hI,List.getElem_append_right hj',List.getElem_replicate]
private theorem filterMap_replicate_none {U : Type} (n : ℕ) :
(List.replicate n (none : Option U)).filterMap id = [] := by
induction n with
| zero => rfl
| succ n ih => simp [List.replicate_succ,ih]
theorem optionalCertificate_filter_congr (initial : LocalMemory) {rows other : List (Option LocalRecord)}
(he : rows.filterMap id = other.filterMap id) :
OptionalCertificate initial rows ↔ OptionalCertificate initial other := by
rw [optionalCertificate_iff,optionalCertificate_iff,he]
theorem memoryWindow_single_certificate (a : Assignment) (w h tier R g z o : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(hz : a z=false) (hs : R ≤ 2^w) (hN : R ≤ 2^h) :
OptionalCertificate (groupInitial (some tier))
(untaggedRows w h (fun i => memoryWindowSource w tier (2^w) R g z o src snap i.val) a) ↔
OptionalCertificate (groupInitial (some tier)) (rawMemoryRows a w R src) := by
apply optionalCertificate_filter_congr
rw [memoryWindow_single a w h tier R g z o src snap hz hs hN,
List.filterMap_append,filterMap_replicate_none,List.append_nil]
theorem memoryWindow_split_certificate (a : Assignment) (w h tier R g z o count : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ)
(hz : a z=false) (ho : a o=true) (hs : ¬ R ≤ 2^w) (hN : 3*2^w ≤ 2^h) (hg : g < count) :
OptionalCertificate (groupInitial none)
(untaggedRows w h (fun i => memoryWindowSource w tier (2^w) R g z o src snap i.val) a) ↔
OptionalCertificate (groupInitial none)
(optionFrame (2^w) (snapshotState a w (2^w) tier z o snap g)
(snapshotState a w (2^w) tier z o snap (g+1))
((fixedGroups (2^w) count (rawMemoryRows a w R src))[g]'(by simpa using hg))) := by
apply optionalCertificate_filter_congr
rw [memoryWindow_split a w h tier R g z o src snap hz ho hs hN,
List.filterMap_append,filterMap_replicate_none,List.append_nil,frameWindow,
fixedGroups_get _ _ _ g hg,rawMemoryBlock_eq]
simp [optionFrame,List.filterMap_append,filterMap_replicate_none]
def SnapshotValuesFit (q : ℕ) (m : LocalMemory) : Prop :=
∀ a v, m a = some v → v < q
theorem StoreRecord.Runs.snapshot_fit {q : ℕ} {xs : List LocalRecord} {m n : LocalMemory}
(r : StoreRecord.Runs xs m n) (h : SnapshotValuesFit q m)
(hAfter : ∀ row ∈ xs, ∀ v, row.after = some v → v < q) : SnapshotValuesFit q n := by
induction r with
| nil m => exact h
| @cons row tail m n _ _ ih =>
apply ih
· intro a v hv
by_cases ha : a = row.addr
· subst a
exact hAfter row (by simp) v (by simpa using hv)
· exact h a v (by simpa [Function.update_of_ne ha] using hv)
· intro rr hr v hv
exact hAfter rr (List.mem_cons_of_mem _ hr) v hv
theorem snapshot_initial_fit (w tier : ℕ) :
SnapshotValuesFit (2^w) (groupInitial (some tier)) := by
intro a v h
change (if tier = bitTier a 0 then some 0 else none) = some v at h
split at h
· obtain rfl := Option.some.inj h
exact Nat.two_pow_pos _
· contradiction
theorem laneRecord_fits (a : Assignment) (w h : ℕ) (r : ℕ → ℕ) :
∀ row, laneRecord a w h r = some row →
row.addr < 2^w ∧
(∀ v, row.before = some v → v < 2^w) ∧ (∀ v, row.after = some v → v < 2^w) := by
have fit (f : ℕ) (key : ℕ → ℕ) (v : ℕ) (he : memoryOpt a f key w = some v) : v < 2^w := by
unfold memoryOpt at he
split at he
· obtain rfl := Option.some.inj he; exact wireValue_lt ..
· contradiction
intro row hr
unfold laneRecord at hr
split at hr
· obtain rfl := Option.some.inj hr
exact ⟨wireValue_lt ..,fit _ _,fit _ _⟩
· contradiction
/-- Independently assigned snapshot bits decode a prescribed finite boundary
state. Initial constants are supplied by the initialization instead. -/
def snapshotValueBit (v : Option ℕ) (j : ℕ) : Bool :=
if j = 0 then v.isSome else (v.getD 0).testBit (j-1)
theorem snapshotState_decode (a : Assignment) (w tier z o b : ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) (m : LocalMemory)
(hb : b ≠ 0) (hm : LocalMemory.Restricted (2^w) m)
(hFit : SnapshotValuesFit (2^w) m)
(hBits : ∀ addr < 2^w, ∀ j ≤ w, a (snap b addr j) = snapshotValueBit (m addr) j) :
snapshotState a w (2^w) tier z o snap b = m := by
funext addr
by_cases ha : addr < 2^w
· rw [snapshotState,if_pos ha]
unfold memoryOpt
have hP : a (snapshotPort tier z o snap b addr 0) = (m addr).isSome := by
rw [snapshotPort,if_neg hb,hBits _ ha _ (Nat.zero_le _)]
simp [snapshotValueBit]
rw [hP]
cases hv : m addr with
| none => simp
| some v =>
have hE : wireValue a (fun i => snapshotPort tier z o snap b addr (i+1)) w = v := by
apply wireValue_testBits _ _ _ _ (hFit _ _ hv)
intro j hj
rw [snapshotPort,if_neg hb,hBits _ ha _ (by omega),hv]
simp [snapshotValueBit]
simp [hE]
· rw [snapshotState,if_neg ha,hm _ (Nat.not_lt.mp ha)]
theorem snapshotIndexed_fits {w count R : ℕ} {src : ℕ → ℕ → ℕ} {a : Assignment}
(snap : Fin (count+1) → LocalMemory)
(hInit : SnapshotValuesFit (2^w) (snap 0))
(hRestr : ∀ i, LocalMemory.Restricted (2^w) (snap i))
(hGroups : ∀ i : Fin count, OptionalCertificate (fun _ => none)
(optionFrame (2^w) (snap i.castSucc) (snap i.succ)
((fixedGroups (2^w) count (rawMemoryRows a w R src))[i.val]'(by simpa using i.isLt)))) :
∀ i, SnapshotValuesFit (2^w) (snap i) := by
refine Fin.induction hInit (fun i hi => ?_)
let group := (fixedGroups (2^w) count (rawMemoryRows a w R src))[i.val]'(by simpa using i.isLt)
have hb (r : LocalRecord) (hr : r ∈ group.filterMap id) :
r.addr < 2^w ∧ (∀ v, r.after = some v → v < 2^w) := by
obtain ⟨row,hRow,hOpt⟩ := List.mem_filterMap.mp hr
have hh : row ∈ rawMemoryRows a w R src := by
unfold group at hRow
rw [fixedGroups_get _ _ _ _ i.isLt] at hRow
exact List.mem_of_mem_drop (List.mem_of_mem_take hRow)
obtain ⟨j,hj,hVal⟩ := List.mem_map.mp hh
have hZ := laneRecord_fits a w 0 (src j) r (hVal.trans hOpt)
exact ⟨hZ.1,hZ.2.2⟩
have hr := (optionFrame_iff (2^w) (snap i.castSucc) (snap i.succ) group
(fun r hr => (hb r hr).1) (hRestr _) (hRestr _)).mp (hGroups i)
exact hr.snapshot_fit hi (fun r hr => (hb r hr).2)
private theorem snapshotLane_bound (w tier z o boundary addr base : ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) (begin : Bool)
(hz : z < base) (ho : o < base) (hs : ∀ k ≤ w, snap boundary addr k < base) :
∀ bit < memLaneWidth w 0, snapshotLane w tier z o snap begin boundary addr bit < base := by
intro bit hbit
have hp (k : ℕ) (hk : k ≤ w) : snapshotPort tier z o snap boundary addr k < base := by
unfold snapshotPort
split
· split <;> assumption
· exact hs k hk
unfold snapshotLane
split
· exact ho
· split
· split <;> assumption
· split
· split
· exact hz
· apply hp
omega
· split
· apply hp
unfold memLaneWidth at hbit
omega
· exact hz
theorem memoryWindowSource_bound (w tier q R g z o base : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ) (hz : z < base) (ho : o < base)
(hr : ∀ i < R, ∀ b < memLaneWidth w 0, src i b < base)
(hs : ∀ k, (k=g ∨ k=g+1) → ∀ a < q, ∀ b ≤ w, snap k a b < base) :
∀ i b, b < memLaneWidth w 0 →
memoryWindowSource w tier q R g z o src snap i b < base := by
intro i b hb
unfold memoryWindowSource
split
· split
· exact hr _ ‹_› _ hb
· exact hz
· split
· exact snapshotLane_bound _ _ _ _ _ _ _ _ _ hz ho (hs g (.inl rfl) i ‹_›) b hb
· split
· dsimp only
split
· exact hr _ ‹_› _ hb
· exact hz
· split
· exact snapshotLane_bound _ _ _ _ _ _ _ _ _ hz ho
(hs (g+1) (.inr rfl) (i-2*q) (by omega)) b hb
· exact hz
private theorem snapshotLane_uses (w tier z o boundary addr : ℕ) (P : ℕ → Prop)
(snap : ℕ → ℕ → ℕ → ℕ) (begin : Bool)
(hz : P z) (ho : P o) (hs : ∀ k ≤ w, P (snap boundary addr k)) :
∀ bit < memLaneWidth w 0, P (snapshotLane w tier z o snap begin boundary addr bit) := by
intro bit hbit
have hp (k : ℕ) (hk : k ≤ w) : P (snapshotPort tier z o snap boundary addr k) := by
unfold snapshotPort
split
· split <;> assumption
· exact hs k hk
unfold snapshotLane
split
· exact ho
· split
· split <;> assumption
· split
· split
· exact hz
· apply hp
omega
· split
· apply hp
unfold memLaneWidth at hbit
omega
· exact hz
theorem memoryWindowSource_uses (w tier q R g z o : ℕ)
(src : ℕ → ℕ → ℕ) (snap : ℕ → ℕ → ℕ → ℕ) (P : ℕ → Prop) (hz : P z) (ho : P o)
(hr : ∀ i < R, ∀ b < memLaneWidth w 0, P (src i b))
(hs : ∀ k, (k=g ∨ k=g+1) → ∀ a < q, ∀ b ≤ w, P (snap k a b)) :
∀ i b, b < memLaneWidth w 0 →
P (memoryWindowSource w tier q R g z o src snap i b) := by
intro i b hb
unfold memoryWindowSource
split
· split
· exact hr _ ‹_› _ hb
· exact hz
· split
· exact snapshotLane_uses _ _ _ _ _ _ _ _ _ hz ho (hs g (.inl rfl) i ‹_›) b hb
· split
· dsimp only
split
· exact hr _ ‹_› _ hb
· exact hz
· split
· exact snapshotLane_uses _ _ _ _ _ _ _ _ _ hz ho
(hs (g+1) (.inr rfl) (i-2*q) (by omega)) b hb
· exact hz
end CNFEncComplexity.Robson
/- RobsonMemFrameNative -/
namespace CNFEncComplexity.Robson
open Turing.MultiTapeTM ComputableTidilyInPolyTime RobsonCNF
section
variable {A : Type} {e : A ↪ List Bool}
private abbrev FU := encUnary
private theorem frameAdd {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e FU) (b : ComputableTidilyInPolyTime g e FU) :
ComputableTidilyInPolyTime (fun x => f x+g x) e FU := unary_add.comp (a.prod b)
private theorem frameSub {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e FU) (b : ComputableTidilyInPolyTime g e FU) :
ComputableTidilyInPolyTime (fun x => f x-g x) e FU := unary_sub.comp (a.prod b)
private theorem frameMul {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e FU) (b : ComputableTidilyInPolyTime g e FU) :
ComputableTidilyInPolyTime (fun x => f x*g x) e FU := unary_mul.comp (a.prod b)
theorem snapshotPort_poly {tier z o boundary addr bit : A → ℕ} {snap : A → ℕ → ℕ → ℕ → ℕ}
(ht : ComputableTidilyInPolyTime tier e FU) (hz : ComputableTidilyInPolyTime z e FU)
(ho : ComputableTidilyInPolyTime o e FU)
(hb : ComputableTidilyInPolyTime boundary e FU) (ha : ComputableTidilyInPolyTime addr e FU)
(hi : ComputableTidilyInPolyTime bit e FU)
(hs : ComputableTidilyInPolyTime (fun p : ((A×ℕ)×ℕ)×ℕ => snap p.1.1.1 p.1.1.2 p.1.2 p.2)
(encPair (encPair (encPair e FU) FU) FU) FU) :
ComputableTidilyInPolyTime (fun a => snapshotPort (tier a) (z a) (o a)
(snap a) (boundary a) (addr a) (bit a)) e FU := by
have s := hs.comp ((((id' (encIn:=e)).prod hb).prod ha).prod hi)
have hTier := unary_size_poly.comp (unary_size_poly.comp ha)
have hC := (unary_beq hi (const 0)).cond (unary_beq hTier ht) (const false)
have hRun := (unary_beq hb (const 0)).cond (hC.cond ho hz) s
convert hRun using 1
funext a
by_cases hB : boundary a=0 <;> by_cases hI : bit a=0 <;> by_cases hT : (addr a).size.size=tier a <;>
simp [snapshotPort,hB,hI,hT,bitTier,Function.comp_def]
theorem snapshotLane_poly {w tier z o boundary addr bit : A → ℕ} {snap : A → ℕ → ℕ → ℕ → ℕ}
(begin : Bool)
(hw : ComputableTidilyInPolyTime w e FU)
(ht : ComputableTidilyInPolyTime tier e FU) (hz : ComputableTidilyInPolyTime z e FU)
(ho : ComputableTidilyInPolyTime o e FU)
(hb : ComputableTidilyInPolyTime boundary e FU) (ha : ComputableTidilyInPolyTime addr e FU)
(hi : ComputableTidilyInPolyTime bit e FU)
(hs : ComputableTidilyInPolyTime (fun p : ((A×ℕ)×ℕ)×ℕ => snap p.1.1.1 p.1.1.2 p.1.2 p.2)
(encPair (encPair (encPair e FU) FU) FU) FU) :
ComputableTidilyInPolyTime (fun a => snapshotLane (w a) (tier a) (z a) (o a)
(snap a) begin (boundary a) (addr a) (bit a)) e FU := by
have hA := binary_testBit (unary_to_binary.comp ha) (frameSub hi (const 1))
have hHead := hA.cond ho hz
have hCut := frameAdd (const 2) (frameMul (const 2) hw)
have s1 := snapshotPort_poly ht hz ho hb ha (frameSub hi (frameAdd (const 1) hw)) hs
have s2 := snapshotPort_poly ht hz ho hb ha (frameSub hi hCut) hs
have hOld := (const (encMid:=encBool) begin).cond hz s1
have hAfter := (const (encMid:=encBool) begin).cond s2 hz
have hTail := (unary_lt' hi hCut).ite' hOld hAfter
have hOut := (unary_beq hi (const 0)).cond ho ((unary_le' hi hw).ite' hHead hTail)
simpa only [snapshotLane,beq_iff_eq,decide_eq_true_eq,Function.comp_def] using hOut
theorem memoryWindowSource_poly {w tier q R g z o i bit : A → ℕ}
{src : A → ℕ → ℕ → ℕ} {snap : A → ℕ → ℕ → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e FU)
(ht : ComputableTidilyInPolyTime tier e FU) (hq : ComputableTidilyInPolyTime q e FU)
(hR : ComputableTidilyInPolyTime R e FU) (hg : ComputableTidilyInPolyTime g e FU)
(hz : ComputableTidilyInPolyTime z e FU) (ho : ComputableTidilyInPolyTime o e FU)
(hi : ComputableTidilyInPolyTime i e FU) (hB : ComputableTidilyInPolyTime bit e FU)
(hs : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e FU) FU) FU)
(hSnap : ComputableTidilyInPolyTime (fun p : ((A×ℕ)×ℕ)×ℕ => snap p.1.1.1 p.1.1.2 p.1.2 p.2)
(encPair (encPair (encPair e FU) FU) FU) FU) :
ComputableTidilyInPolyTime (fun a => memoryWindowSource (w a) (tier a) (q a) (R a) (g a) (z a)
(o a) (src a) (snap a) (i a) (bit a)) e FU := by
have hS : ComputableTidilyInPolyTime (fun a => src a (i a) (bit a)) e FU :=
hs.comp (((id' (encIn:=e)).prod hi).prod hB)
have hSmall := (unary_lt' hi hR).ite' hS hz
have hPre := snapshotLane_poly true hw ht hz ho hg hi hB hSnap
have hQ2 := frameMul (const 2) hq
have hQ3 := frameMul (const 3) hq
have hPost := snapshotLane_poly false hw ht hz ho (frameAdd hg (const 1)) (frameSub hi hQ2) hB hSnap
have hIX := frameAdd (frameMul hg hq) (frameSub hi hq)
have hSrc : ComputableTidilyInPolyTime (fun a => src a (g a*q a+(i a-q a)) (bit a)) e FU :=
hs.comp (((id' (encIn:=e)).prod hIX).prod hB)
have hData := (unary_lt' hIX hR).ite' hSrc hz
have hWide := (unary_lt' hi hq).ite' hPre
((unary_lt' hi hQ2).ite' hData ((unary_lt' hi hQ3).ite' hPost hz))
simpa only [memoryWindowSource,decide_eq_true_eq] using (unary_le' hR hq).ite' hSmall hWide
end
end CNFEncComplexity.Robson
/- RobsonMemSupport -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def GatesOn (P : ℕ → Prop) (gs : List Gate) : Prop :=
∀ g ∈ gs, ∀ k ∈ g.names, P k
theorem GatesOn.append {P : ℕ → Prop} {l r : List Gate}
(hl : GatesOn P l) (hr : GatesOn P r) : GatesOn P (l ++ r) := by
intro g hg k hk
rcases List.mem_append.mp hg with hg|hg
· exact hl g hg k hk
· exact hr g hg k hk
private theorem compile_names (g : Gate) {c : Clause} (hc : c ∈ g.compile) {l : Literal}
(hl : l ∈ c) : l.var ∈ g.names := by
cases g with
| pin k v =>
cases v <;>
simp [Gate.compile,pinLiteral,RobsonCNF.Gate.names] at hc hl ⊢ <;>
subst c <;> simp_all [Literal.var]
| assert c' =>
simp only [Gate.compile,List.mem_singleton] at hc
exact List.mem_map.mpr ⟨l,hc ▸ hl,rfl⟩
| copy p q | inv p q | conj p q r | disj p q r | parity p q r | mux p q r s =>
simp only [Gate.compile,List.mem_cons,List.not_mem_nil,or_false] at hc
rcases hc with rfl|rfl|rfl|rfl <;>
simp only [List.mem_cons,List.not_mem_nil,or_false] at hl <;>
rcases hl with rfl|rfl|rfl <;> simp [RobsonCNF.Gate.names,Literal.var]
theorem GatesOn.guard {P : ℕ → Prop} {gs : List Gate} {l : Literal}
(h : GatesOn P gs) (hp : P l.var) : GatesOn P (guarded l gs) := by
intro g hg k hk
obtain ⟨c,hc,rfl⟩ := List.mem_map.mp hg
obtain ⟨g,hg,hc⟩ := List.mem_flatMap.mp hc
obtain ⟨ls,hls,rfl⟩ := List.mem_map.mp hk
rcases List.mem_cons.mp hls with rfl|hl
· cases l <;> exact hp
· exact h g hg _ (compile_names g hc hl)
private theorem bounded_pin {P : ℕ → Prop} {k : ℕ} {v : Bool} (hk : P k) : GatesOn P [.pin k v] := by
intro g hg z hz
obtain rfl := List.mem_singleton.mp hg
simpa [RobsonCNF.Gate.names,List.mem_singleton.mp hz] using hk
private theorem wordCopy_on {P : ℕ → Prop} {w : ℕ} {x y : ℕ → ℕ}
(hx : ∀ j < w, P (x j)) (hy : ∀ j < w, P (y j)) : GatesOn P (wordCopy w x y) := by
intro g hg k hk
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hk
rcases hk with rfl|rfl
· exact hx _ (List.mem_range.mp hj)
· exact hy _ (List.mem_range.mp hj)
private theorem wordConst_on {P : ℕ → Prop} {w v : ℕ} {x : ℕ → ℕ}
(hx : ∀ j < w, P (x j)) : GatesOn P (wordConst w x v) := by
intro g hg k hk
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
exact (List.mem_singleton.mp hk) ▸ hx _ (List.mem_range.mp hj)
private theorem bitBand_lt {w lo hi j : ℕ} (hj : j ∈ bitBand w lo hi) : j < w :=
List.mem_range.mp (List.mem_filter.mp hj).1
private theorem initialFlagGates_on {P : ℕ → Prop} (tier w p : ℕ) (addr : ℕ → ℕ)
(hp : P p) (ha : ∀ j < w, P (addr j)) : GatesOn P (initialFlagGates tier w p addr) := by
have hHigh {q : ℕ} {k : ℕ}
(hk : k ∈ ((bitBand w (initHigh q) w).map (fun i => Literal.Pos (addr i))).map Literal.var) :
P k := by
rw [List.map_map] at hk
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hk
exact ha _ (bitBand_lt hi)
have hNeg (q : ℕ) : GatesOn P ((bitBand w (initHigh q) w).map
(fun i => Gate.assert [.Neg p,.Neg (addr i)])) := by
intro g hg k hk
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
simp only [RobsonCNF.Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,
or_false] at hk
rcases hk with rfl|rfl
· exact hp
· exact ha _ (bitBand_lt hi)
cases tier with
| zero =>
intro g hg k hk
rcases List.mem_cons.mp hg with rfl|hg
· simp only [RobsonCNF.Gate.names,List.map_cons,Literal.var,List.mem_cons] at hk
rcases hk with rfl|hk
· exact hp
· exact hHigh hk
· exact hNeg 0 g hg k hk
| succ j =>
intro g hg k hk
rcases List.mem_cons.mp hg with rfl|hg
· simp only [RobsonCNF.Gate.names,List.map_cons,Literal.var,List.mem_cons] at hk
rcases hk with rfl|hk
· exact hp
· rw [List.map_map] at hk
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hk
exact ha _ (bitBand_lt hi)
· rcases List.mem_append.mp hg with hg|hg
· exact hNeg (j+1) g hg k hk
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
simp only [RobsonCNF.Gate.names,List.map_cons,Literal.var,List.mem_cons] at hk
rcases hk with rfl|rfl|hh
· exact hp
· exact ha _ (bitBand_lt hi)
· exact hHigh hh
private theorem groupInitialGates_on {P : ℕ → Prop} (tier : Option ℕ) (w p : ℕ)
(addr value : ℕ → ℕ)
(hp : P p) (ha : ∀ j < w, P (addr j)) (hv : ∀ j < w, P (value j)) :
GatesOn P (groupInitialGates tier w p addr value) := by
cases tier with
| none => exact bounded_pin hp
| some j =>
exact (initialFlagGates_on j w p addr hp ha).append
((wordConst_on (v:=0) hv).guard hp)
private theorem row_ports_on {P : ℕ → Prop} {w h : ℕ} {row : ℕ → ℕ}
(hr : ∀ j < memLaneWidth w h, P (row j)) :
P (laneActive row) ∧ P (laneBeforeFlag w h row) ∧ P (laneAfterFlag w h row) ∧
(∀ j < w, P (laneAddress h row j)) ∧
(∀ j < w, P (laneBefore w h row j)) ∧
(∀ j < w, P (laneAfter w h row j)) := by
simp only [laneActive,laneBeforeFlag,laneAfterFlag,laneAddress,laneBefore,laneAfter]
refine ⟨hr _ ?_,hr _ ?_,hr _ ?_,fun j hj => hr _ ?_,fun j hj => hr _ ?_,fun j hj => hr _ ?_⟩ <;>
unfold memLaneWidth <;> omega
theorem laneInit_on {P : ℕ → Prop} (tier : Option ℕ) (w h : ℕ) (r : ℕ → ℕ)
(hr : ∀ j < memLaneWidth w h, P (r j)) : GatesOn P (laneInit tier w h r) := by
obtain ⟨p,b,_,a,v,_⟩ := row_ports_on hr
exact (groupInitialGates_on tier w _ _ _ b a v).guard p
theorem lanePairChecks_on {P : ℕ → Prop} (tier : Option ℕ) (w h base : ℕ)
(l r : ℕ → ℕ) (hl : ∀ j < memLaneWidth w h, P (l j))
(hr : ∀ j < memLaneWidth w h, P (r j)) (h1 : P (ltWire base (h+w)))
(h2 : P (eqWire (laneCmpBase w h base) w)) :
GatesOn P (lanePairChecks tier w h base l r) := by
obtain ⟨pl,_,al,_,_,vl⟩ := row_ports_on hl
obtain ⟨pr,br,_,ar,vr,_⟩ := row_ports_on hr
unfold lanePairChecks
apply GatesOn.append
· intro g hg k hk
simp only [List.mem_cons,List.not_mem_nil,or_false] at hg
rcases hg with rfl|rfl <;>
simp only [RobsonCNF.Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,or_false] at hk
· rcases hk with rfl|rfl
· exact pl
· exact pr
· rcases hk with rfl|rfl|rfl
· exact pl
· exact pr
· exact h1
· apply GatesOn.guard (l := .Pos (laneActive l)) _ pl
apply GatesOn.guard (l := .Pos (laneActive r)) _ pr
apply GatesOn.append
· apply GatesOn.guard (l := .Pos (eqWire (laneCmpBase w h base) w)) _ h2
unfold memoryOptEqual
change GatesOn P ([.copy (laneAfterFlag w h l) (laneBeforeFlag w h r)] ++ _)
apply GatesOn.append
· intro g hg k hk
obtain rfl := List.mem_singleton.mp hg
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hk
rcases hk with rfl|rfl
· exact al
· exact br
· exact (wordCopy_on vl vr).guard al
· exact (groupInitialGates_on tier w _ _ _ br ar vr).guard h2
theorem memSortGates_uses (tier : Option ℕ) (w h base : ℕ)
(src : Fin (2^h) → ℕ → ℕ) (P : ℕ → Prop)
(hSrc : ∀ i j, j < memLaneWidth w 0 → P (src i j))
(hPriv : ∀ k, base ≤ k → k < memGroupTop w h base → P k) :
GatesOn P (memSortGates tier w h base src) := by
have hTop : memRouteTop w h base ≤ memGroupTop w h base := Nat.le_add_right _ _
have hName (v : RouteVar h (Fin (memLaneWidth w h))) : P (memRouteName w h base v) :=
hPriv _ (memRouteName_ge ..) ((memRouteName_lt ..).trans_le hTop)
have hI (i : Fin (2^h)) (j : ℕ) (hj : j < memLaneWidth w h) :
P (memInputLane w h base i j) := by
rw [memInputLane,dif_pos hj]
exact hName _
have hO (i : Fin (2^h)) (j : ℕ) (hj : j < memLaneWidth w h) :
P (memOutputLane w h base i j) := by
rw [memOutputLane,dif_pos hj]
exact hName _
have hE (i : Fin (memEdgeCount h)) :
base ≤ memRouteTop w h base ∧ memRouteTop w h base ≤ memEdgeBase w h base i ∧
laneCmpEnd w h (memEdgeBase w h base i) ≤ memGroupTop w h base := by
refine ⟨Nat.le_add_right _ _,Nat.le_add_right _ _,?_⟩
have hu : (i.val+1)*memEdgeStride w h ≤ memEdgeCount h*memEdgeStride w h :=
Nat.mul_le_mul_right (memEdgeStride w h) (by omega)
calc
_ = memRouteTop w h base + (i.val+1)*memEdgeStride w h := by
unfold laneCmpEnd laneCmpBase memEdgeBase memEdgeStride
ring
_ ≤ memGroupTop w h base := Nat.add_le_add_left hu _
unfold memSortGates
apply GatesOn.append
· apply GatesOn.append
· intro g hg k hk
obtain ⟨i,_,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
have hJ := List.mem_range.mp hj
unfold laneAttachGate at hk
split at hk
· exact (List.mem_singleton.mp hk) ▸ hI i j hJ
· rename_i hn
simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hk
rcases hk with rfl|rfl
· exact hI i j hJ
· have hj' : sourceBitIndex h j < memLaneWidth w 0 := by
unfold sourceBitIndex
split
· unfold memLaneWidth; omega
· unfold memLaneWidth at *; omega
exact hSrc i _ hj'
· intro g hg k hk
obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hg
cases r <;> simp [RouteGate.named,RobsonCNF.Gate.names,List.mem_cons] at hk <;>
rcases hk with rfl|rfl|rfl|rfl <;> exact hName _
· unfold outputChecks
apply GatesOn.append (laneInit_on tier w h _ (hO _))
intro g hg k hk
obtain ⟨i,_,hg⟩ := List.mem_flatMap.mp hg
rcases List.mem_append.mp hg with hg|hg
· have he := hE i
rcases lanePairComparators_names w h (memEdgeBase w h base i) (memRouteTop w h base)
_ _ he.2.1 (memOutputLane_lt w h base (memEdgeLeft i))
(memOutputLane_lt w h base (memEdgeRight i)) g hg k hk with hBound|hBound
· -- Name below route top is a computed row input to the comparator.
by_cases hB : base ≤ k
· exact hPriv _ hB (hBound.trans_le hTop)
· have hLT : k < base := by omega
-- Re-evaluate closure with threshold base using the actual row names.
have h1 (x : Fin (2^h)) (b : ℕ) (hb : b < memLaneWidth w h) :
base ≤ memOutputLane w h base x b := by
rw [memOutputLane,dif_pos hb]
exact memRouteName_ge ..
have ht (_ : Fin (2^h)) : ∀ j < memLaneWidth w h, memOutputLane w h base
(memFirstIx h) j < memRouteTop w h base := memOutputLane_lt w h base _
-- The comparator uses only these row bits and its private interval.
have keyGe (x : Fin (2^h)) (j : ℕ) (hj : j < h+w) :
base ≤ laneKey h (memOutputLane w h base x) j := by
unfold laneKey joinKey
split
· apply h1; unfold memLaneWidth; omega
· apply h1; unfold memLaneWidth; omega
have addrGe (x : Fin (2^h)) (j : ℕ) (hj : j < w) :
base ≤ laneAddress h (memOutputLane w h base x) j := by
apply h1; unfold memLaneWidth; omega
unfold lanePairComparators at hg
have gen (q len : ℕ) (x y : ℕ → ℕ) (hq : base ≤ q)
(hx : ∀ j < len, base ≤ x j) (hy : ∀ j < len, base ≤ y j)
(hm : g ∈ compareCircuit q len x y) : False := by
rcases List.mem_append.mp hm with hm|hm
· simp only [List.mem_cons,List.not_mem_nil,or_false] at hm
rcases hm with rfl|rfl <;> simp [RobsonCNF.Gate.names,ltWire,eqWire] at hk <;> omega
· obtain ⟨j,hj,hm⟩ := List.mem_flatMap.mp hm
specialize hx j (List.mem_range.mp hj)
specialize hy j (List.mem_range.mp hj)
simp only [compareStep,List.mem_cons,List.not_mem_nil,or_false] at hm
rcases hm with rfl|rfl|rfl|rfl <;>
simp [RobsonCNF.Gate.names,ltWire,eqWire,diffWire,sameWire] at hk <;> omega
exfalso
rcases List.mem_append.mp hg with hm|hm
· exact gen _ _ _ _ (he.1.trans he.2.1) (keyGe _) (keyGe _) hm
· have hQ : base ≤ laneCmpBase w h (memEdgeBase w h base i) :=
(he.1.trans he.2.1).trans (by unfold laneCmpBase; omega)
exact gen _ _ _ _ hQ (addrGe _) (addrGe _) hm
· exact hPriv _ (he.1.trans (he.2.1.trans hBound.1)) (hBound.2.trans_le he.2.2)
· have he := hE i
have hLT : P (ltWire (memEdgeBase w h base i) (h+w)) := by
refine hPriv _ ((he.1.trans he.2.1).trans (Nat.le_add_right _ _)) ?_
apply LT.lt.trans_le _ he.2.2
unfold ltWire laneCmpEnd laneCmpBase
omega
have hEQ : P (eqWire (laneCmpBase w h (memEdgeBase w h base i)) w) := by
apply hPriv
· unfold eqWire laneCmpBase
omega
· apply LT.lt.trans_le _ he.2.2
unfold eqWire laneCmpEnd
omega
exact lanePairChecks_on tier w h _ _ _ (hO _) (hO _) hLT hEQ g hg k hk
theorem memSortGates_names (tier : Option ℕ) (w h base low : ℕ)
(src : Fin (2^h) → ℕ → ℕ) (_hlow : low ≤ base)
(hSrc : ∀ i j, j < memLaneWidth w 0 → src i j < low) :
GatesOn (fun k => k < low ∨ (base ≤ k ∧ k < memGroupTop w h base))
(memSortGates tier w h base src) :=
memSortGates_uses tier w h base src _ (fun i j hj => .inl (hSrc i j hj))
(fun k hl hr => .inr ⟨hl,hr⟩)
end CNFEncComplexity.Robson
/- RobsonRouteNumeric -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
set_option backward.isDefEq.respectTransparency false
@[simp] theorem wireLabel_succ_val {h : ℕ} (x : Wire h) (b : Bool) :
(wireLabel (h+1) (x,b)).val = 2*(wireLabel h x).val+b.toNat := by
change (finProdFinEquiv (wireLabel h x,finTwoEquiv.symm b)).val = _
rw [finProdFinEquiv_apply_val]
cases b <;> simp [finTwoEquiv,Nat.add_comm]
private theorem flatRange_double (n : ℕ) :
(List.range n).flatMap (fun i => [2*i,2*i+1]) = List.range (2*n) := by
induction n with
| zero => rfl
| succ n ih =>
rw [List.range_succ,List.flatMap_append,List.flatMap_singleton,ih]
have he : 2*(n+1) = 2*n+1+1 := by omega
rw [he,List.range_succ,List.range_succ]
simp [List.append_assoc]
private theorem routeWireList_map (h : ℕ) :
(routeWireList h).map (fun a => (wireLabel h a).val) = List.range (2^h) := by
induction h with
| zero => rfl
| succ h ih =>
change ((routeWireList h).flatMap fun x => ([(x,false),(x,true)] : List (Wire (h+1)))).map _ = _
erw [List.map_flatMap]
conv_rhs => rw [Nat.pow_succ,Nat.mul_comm]
change ((routeWireList h).flatMap fun x =>
[(wireLabel (h+1) (x,false)).val,(wireLabel (h+1) (x,true)).val]) = _
have hEq : (fun x : Wire h => [(wireLabel (h+1) (x,false)).val,(wireLabel (h+1) (x,true)).val]) =
fun x => [2*(wireLabel h x).val,2*(wireLabel h x).val+1] := by
funext x
exact congrArg₂ (fun i j => [i,j])
(by simpa using (wireLabel_succ_val x false)) (by simpa using (wireLabel_succ_val x true))
rw [hEq]
rw [← flatRange_double,← ih,List.flatMap_map]
theorem routeFinRange_val (d : ℕ) :
(List.finRange d).map Fin.val = List.range d := by
induction d with
| zero => rfl
| succ d ih =>
rw [List.finRange_succ,List.map_cons,List.map_map]
have h : Fin.val ∘ (Fin.succ : Fin d → Fin (d+1)) = (fun j => j+1) ∘ Fin.val := rfl
rw [h,← List.map_map,ih,List.range_succ_eq_map]
rfl
/-- A node opens onto two equally strided endpoint arrays. Its private variables
are the two switch columns followed by its children. -/
abbrev RouteNode := ℕ × ℕ × ℕ × ℕ × ℕ
def routeNodeDepth (node : RouteNode) : ℕ := node.1
def routeNodeInput (node : RouteNode) : ℕ := node.2.1
def routeNodeOutput (node : RouteNode) : ℕ := node.2.2.1
def routeNodeStride (node : RouteNode) : ℕ := node.2.2.2.1
def routeNodeAux (node : RouteNode) : ℕ := node.2.2.2.2
def rootRouteNode (w h base : ℕ) : RouteNode :=
let D := 2^h*w
(h,base,base+D,w,base+(D+D))
def nodeRouteName (w : ℕ) (node : RouteNode) :
RouteVar (routeNodeDepth node) (Fin w) → ℕ
| .input i j => routeNodeInput node+(wireLabel (routeNodeDepth node) i).val*routeNodeStride node+j.val
| .output i j => routeNodeOutput node+(wireLabel (routeNodeDepth node) i).val*routeNodeStride node+j.val
| .aux a => routeNodeAux node+(auxLabel w (routeNodeDepth node) a).val
@[simp] private theorem auxLabel_control_val
{w h : ℕ} (side : Bool) (a : Wire h) :
(auxLabel w (h+1) (.inl (side,a))).val = side.toNat*2^h+(wireLabel h a).val := by
change (finProdFinEquiv (finTwoEquiv.symm side,wireLabel h a)).val = _
rw [finProdFinEquiv_apply_val]
cases side <;> simp [finTwoEquiv,Nat.add_comm]
@[simp] private theorem auxLabel_inner_val
{w h : ℕ} (side : Bool) (a : Wire (h+1)) (j : Fin w) :
(auxLabel w (h+1) (.inr (.inl (side,a,j)))).val =
2^h*2+side.toNat*(2^(h+1)*w)+(wireLabel (h+1) a).val*w+j.val := by
change 2*2^h + (finProdFinEquiv (finTwoEquiv.symm side,
finProdFinEquiv (wireLabel (h+1) a,j))).val = _
rw [finProdFinEquiv_apply_val,finProdFinEquiv_apply_val]
cases side <;> simp [finTwoEquiv] <;> ring
@[simp] private theorem auxLabel_child_val
{w h : ℕ} (side : Bool) (a : RouteAux (Fin w) h) :
(auxLabel w (h+1) (.inr (.inr (side,a)))).val =
2^h*2+2*(2^(h+1)*w)+side.toNat*auxCount w h+(auxLabel w h a).val := by
change 2*2^h+(2*(2^(h+1)*w) + (finProdFinEquiv (finTwoEquiv.symm side,auxLabel w h a)).val) = _
rw [finProdFinEquiv_apply_val]
cases side <;> simp [finTwoEquiv] <;> ring
def routeNodeChild (w h inB outB s aux : ℕ) (b : Bool) : RouteNode :=
let n := 2^(h+1)
let q := n*w
(h,aux+n+b.toNat*w,aux+n+q+b.toNat*w,2*w,aux+n+2*q+b.toNat*auxCount w h)
theorem nodeRouteName_embed (w h inB outB step aux : ℕ) (b : Bool)
(v : RouteVar h (Fin w)) :
nodeRouteName w (h+1,inB,outB,step,aux) (v.embed b) =
nodeRouteName w (routeNodeChild w h inB outB step aux b) v := by
cases v with
| input i j =>
simp only [nodeRouteName,routeNodeChild,RouteVar.embed,RouteVar.internal,routeNodeDepth,
routeNodeAux,routeNodeInput,routeNodeStride]
erw [auxLabel_inner_val (w:=w) (h:=h) false (i,b) j]
rw [wireLabel_succ_val]
simp only [Bool.toNat_false,Nat.zero_mul,Nat.add_zero,Nat.pow_succ]
ring
| output i j =>
simp only [nodeRouteName,routeNodeChild,RouteVar.embed,RouteVar.internal,routeNodeDepth,
routeNodeAux,routeNodeOutput,routeNodeStride]
erw [auxLabel_inner_val (w:=w) (h:=h) true (i,b) j]
rw [wireLabel_succ_val]
simp only [Bool.toNat_true,Nat.one_mul,Nat.pow_succ]
ring
| aux a =>
simp only [nodeRouteName,routeNodeChild,RouteVar.embed,routeNodeDepth,routeNodeAux]
erw [auxLabel_child_val (w:=w) (h:=h) b a]
rw [Nat.pow_succ]
ring
theorem nodeRouteName_root (w h base : ℕ) (v : RouteVar h (Fin w)) :
nodeRouteName w (rootRouteNode w h base) v = base+(routeLabel h w v).val := by
cases v with
| input i j =>
change base+(wireLabel h i).val*w+j.val = base+(finProdFinEquiv (wireLabel h i,j)).val
rw [finProdFinEquiv_apply_val]
simp only [Prod.snd,Prod.fst]
ring
| output i j =>
change base+2^h*w+(wireLabel h i).val*w+j.val =
base+(2^h*w+(finProdFinEquiv (wireLabel h i,j)).val)
rw [finProdFinEquiv_apply_val]
simp only [Prod.snd,Prod.fst]
ring
| aux u =>
change base+(2^h*w+2^h*w)+(auxLabel w h u).val = base+(2^h*w+(2^h*w+(auxLabel w h u).val))
omega
def nodeColumnGate (w h inB outB stride aux : ℕ) (exit : Bool) (a b j : ℕ) : Gate :=
let n := 2^(h+1)
let x := 2*a+b
let cross := 2*a+(1-b)
let sel := aux+exit.toNat*2^h+a
let inside := aux+n+exit.toNat*(n*w)
if exit then
.mux (outB+x*stride+j) sel (inside+cross*w+j) (inside+x*w+j)
else
.mux (inside+x*w+j) sel (inB+cross*stride+j) (inB+x*stride+j)
def nodeColumn (w h inB outB stride aux : ℕ) (exit : Bool) : List Gate :=
(List.range (2^h)).flatMap fun a => [0,1].flatMap fun b =>
(List.range w).map fun j => nodeColumnGate w h inB outB stride aux exit a b j
theorem nodeColumn_exact (w h inB outB step aux : ℕ) (side : Bool) :
(routeSide (h:=h) (List.finRange w) side).map
(RouteGate.named (nodeRouteName w (h+1,inB,outB,step,aux))) =
nodeColumn w h inB outB step aux side := by
change ((routeWireList h).flatMap fun a => [false,true].flatMap fun b =>
(List.finRange w).map fun (j : Fin w) =>
(if side then (RouteGate.mux : RouteVar (h+1) (Fin w) → _ → _ → _ → _) (.output (a,b) j) (.control true a)
(.internal true (a,!b) j) (.internal true (a,b) j)
else (RouteGate.mux : RouteVar (h+1) (Fin w) → _ → _ → _ → _) (.internal false (a,b) j) (.control false a) (.input (a,!b) j) (.input (a,b) j))).map
_ = _
rw [nodeColumn,← routeWireList_map,← routeFinRange_val,List.flatMap_map]
simp only [List.map_flatMap,List.map_map]
apply congrArg (fun f => (routeWireList h).flatMap f)
funext a
simp only [List.flatMap_cons,List.flatMap_nil,List.append_nil]
congr 1
all_goals
apply List.map_congr_left
intro j hj
have hFalse := wireLabel_succ_val a false
have hTrue := wireLabel_succ_val a true
simp only [Bool.toNat_false,Bool.toNat_true,Nat.add_zero] at hFalse hTrue
cases side <;>
simp [Function.comp_def,nodeColumnGate,RouteGate.named,nodeRouteName,routeNodeDepth,routeNodeInput,
routeNodeOutput,routeNodeStride,routeNodeAux,RouteVar.control,RouteVar.internal,auxLabel_inner_val,
auxLabel_control_val,hFalse,hTrue,Nat.pow_succ] <;>
repeat' apply And.intro
all_goals
repeat' first | erw [hFalse] | erw [hTrue]
first | (left; rfl) | rfl | (left; ring) | ring
end CNFEncComplexity.Robson
/- RobsonRouteFrontier -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
set_option backward.isDefEq.respectTransparency false
/-- A route expansion alternates pending nodes, entry columns, terminal copies,
and exit columns. Keeping pending nodes in the same list preserves gate order. -/
abbrev RouteFrontEntry := ℕ × RouteNode
def routeFront : ℕ → ℕ → ℕ → ℕ → ℕ → ℕ → ℕ → List RouteFrontEntry
| _, _, 0, inB, outB, stride, aux => [(2,0,inB,outB,stride,aux)]
| _, 0, h+1, inB, outB, stride, aux => [(0,h+1,inB,outB,stride,aux)]
| w, k+1, h+1, inB, outB, stride, aux =>
let node := (h+1,inB,outB,stride,aux)
let l := routeNodeChild w h inB outB stride aux false
let r := routeNodeChild w h inB outB stride aux true
(1,node) :: (routeFront w k h l.2.1 l.2.2.1 l.2.2.2.1 l.2.2.2.2 ++
routeFront w k h r.2.1 r.2.2.1 r.2.2.2.1 r.2.2.2.2 ++ [(3,node)])
def routeOneGates (w : ℕ) (e : RouteFrontEntry) : List Gate :=
let (q,h,inB,outB,stride,aux) := e
if q = 2 then (List.range w).map (fun j => Gate.copy (outB+j) (inB+j))
else nodeColumn w (h-1) inB outB stride aux (q == 3)
private theorem named_route_map_rename {V W : Type} (f : V → W) (g : W → ℕ)
(bits : List (RouteGate V)) :
(bits.map (RouteGate.rename f)).map (RouteGate.named g) =
bits.map (RouteGate.named (g ∘ f)) := by
simp only [List.map_map]
congr 1
funext x
cases x <;> rfl
theorem routeFront_exact (w k h inB outB stride aux : ℕ) (hk : h ≤ k) :
(routeFront w k h inB outB stride aux).flatMap (routeOneGates w) =
routeNamedGates (nodeRouteName w (h,inB,outB,stride,aux)) := by
induction h generalizing k inB outB stride aux with
| zero =>
have he : (List.finRange w).map Fin.val = List.range w := routeFinRange_val w
simp only [routeNamedGates,routeNodeDepth,Prod.fst]
erw [routeFront,List.flatMap_cons,List.flatMap_nil,List.append_nil,routeOneGates,if_pos rfl,
routeGates.eq_1,← he,List.map_map,List.map_map]
congr 1
funext j
simp [Function.comp_def,nodeRouteName,RouteGate.named,routeNodeDepth,routeNodeInput,
routeNodeOutput,routeNodeStride,wireLabel]
| succ h ih =>
cases k with
| zero => omega
| succ k =>
have hk' : h ≤ k := by omega
simp only [routeNamedGates,routeNodeDepth,Prod.fst]
erw [routeGates_succ_eq]
simp only [List.map_append,named_route_map_rename,routeFront,List.flatMap_cons,List.flatMap_append,
List.flatMap_nil,List.append_nil]
have hL : nodeRouteName w (h+1,inB,outB,stride,aux) ∘
(RouteVar.embed (h:=h) (B:=Fin w) false) =
nodeRouteName w (routeNodeChild w h inB outB stride aux false) :=
funext (nodeRouteName_embed w h inB outB stride aux false)
have hR : nodeRouteName w (h+1,inB,outB,stride,aux) ∘
(RouteVar.embed (h:=h) (B:=Fin w) true) =
nodeRouteName w (routeNodeChild w h inB outB stride aux true) :=
funext (nodeRouteName_embed w h inB outB stride aux true)
erw [hL,hR]
rw [ih _ _ _ _ _ hk',ih _ _ _ _ _ hk']
simp only [routeOneGates,Nat.reduceEqDiff,if_false,beq_iff_eq,Nat.reduceEqDiff,
Nat.add_sub_cancel,beq_self_eq_true]
rw [nodeColumn_exact,nodeColumn_exact]
simp only [routeNamedGates,List.append_assoc]
rfl
/-- Logical expansion is independent of the budget used by native code
to cap unary powers. The cap is at least every active node width. -/
def capRoutePow (cap k : ℕ) : ℕ := min cap (2^k)
def expandRouteEntry (cap w : ℕ) (e : RouteFrontEntry) : List RouteFrontEntry :=
let (q,d,inB,outB,stride,aux) := e
if q = 0 then
let c := d-1
let n := capRoutePow cap d
let m := capRoutePow cap c
let p := n*w
let start := aux+n+2*p
[(1,d,inB,outB,stride,aux),
(if c = 0 then 2 else 0,c,aux+n,aux+n+p,2*w,start),
(if c = 0 then 2 else 0,c,aux+n+w,aux+n+p+w,2*w,start+c*m*(1+2*w)),
(3,d,inB,outB,stride,aux)]
else [e]
def expandRoute (cap w : ℕ) (f : List RouteFrontEntry) : List RouteFrontEntry :=
f.flatMap (expandRouteEntry cap w)
theorem expandRoute_correct (cap w k h inB outB stride aux : ℕ) (hh : 2^h ≤ cap) :
expandRoute cap w (routeFront w k h inB outB stride aux) =
routeFront w (k+1) h inB outB stride aux := by
induction k generalizing h inB outB stride aux with
| zero =>
cases h with
| zero => rfl
| succ h =>
have hh' : 2^h ≤ cap := (Nat.pow_le_pow_right (by decide) (Nat.le_succ h)).trans hh
have hh2 : 2 ≤ cap := by
have hx : 2^(0+1) ≤ (2:ℕ)^(h+1) := Nat.pow_le_pow_right (by decide) (by omega)
exact hx.trans hh
cases h <;> simp [expandRoute,expandRouteEntry,routeFront,capRoutePow,min_eq_right hh,min_eq_right hh2,hh2,
min_eq_right hh',routeNodeChild,auxCount_exact] <;> ring
| succ k ih =>
cases h with
| zero => rfl
| succ h =>
have hh' : 2^h ≤ cap := (Nat.pow_le_pow_right (by decide) (Nat.le_succ h)).trans hh
simp only [expandRoute,routeFront,List.flatMap_cons,List.flatMap_append,List.flatMap_nil,List.append_nil]
simp only [expandRouteEntry,Nat.reduceEqDiff,if_false,List.singleton_append]
rw [show List.flatMap (expandRouteEntry cap w) (routeFront w k h _ _ _ _) = _ from
ih h _ _ _ _ hh', show List.flatMap (expandRouteEntry cap w) (routeFront w k h _ _ _ _) = _ from
ih h _ _ _ _ hh']
theorem routeFront_card (w k h inB outB stride aux : ℕ) :
(routeFront w k h inB outB stride aux).length+2 ≤ 4*2^h := by
induction h generalizing k inB outB stride aux with
| zero => cases k <;> simp [routeFront]
| succ h ih =>
cases k with
| zero =>
have hP : 0 < (2:ℕ)^h := Nat.pow_pos (by decide)
simp [routeFront,Nat.pow_succ]
omega
| succ k =>
simp only [routeFront,List.length_cons,List.length_append,List.length_singleton,Nat.pow_succ]
let l := routeNodeChild w h inB outB stride aux false
let r := routeNodeChild w h inB outB stride aux true
have hL := ih k l.2.1 l.2.2.1 l.2.2.2.1 l.2.2.2.2
have hR := ih k r.2.1 r.2.2.1 r.2.2.2.1 r.2.2.2.2
change (routeFront w k h l.2.1 l.2.2.1 l.2.2.2.1 l.2.2.2.2).length+
((routeFront w k h r.2.1 r.2.2.1 r.2.2.2.1 r.2.2.2.2).length+1)+1+2 ≤ _
omega
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
private theorem routeFront_self (w h inB outB stride aux q : ℕ) (hq : q ≤ 3) :
q ≤ 3 ∧ routeNodeDepth (h,inB,outB,stride,aux) ≤ h ∧
routeNodeInput (h,inB,outB,stride,aux) ≤ max inB (aux+auxCount w h) ∧
routeNodeOutput (h,inB,outB,stride,aux) ≤ max outB (aux+auxCount w h) ∧
routeNodeStride (h,inB,outB,stride,aux) ≤ max stride (2*w) ∧
routeNodeAux (h,inB,outB,stride,aux)+auxCount w (routeNodeDepth (h,inB,outB,stride,aux)) ≤ aux+auxCount w h :=
⟨hq,le_rfl,le_max_left ..,le_max_left ..,le_max_left ..,le_rfl⟩
theorem routeFront_coordinates (w k h inB outB stride aux : ℕ) (x : RouteFrontEntry)
(hx : x ∈ routeFront w k h inB outB stride aux) :
x.1 ≤ 3 ∧ routeNodeDepth x.2 ≤ h ∧
routeNodeInput x.2 ≤ max inB (aux+auxCount w h) ∧
routeNodeOutput x.2 ≤ max outB (aux+auxCount w h) ∧
routeNodeStride x.2 ≤ max stride (2*w) ∧ routeNodeAux x.2+auxCount w (routeNodeDepth x.2) ≤ aux+auxCount w h := by
induction h generalizing k inB outB stride aux x with
| zero =>
simp only [routeFront,List.mem_singleton] at hx
subst x
exact routeFront_self w _ _ _ _ _ 2 (by decide)
| succ h ih =>
cases k with
| zero =>
simp only [routeFront,List.mem_singleton] at hx
subst x
exact routeFront_self w _ _ _ _ _ 0 (by decide)
| succ k =>
have sub (b : Bool) (hy :
x ∈ routeFront w k h (routeNodeChild w h inB outB stride aux b).2.1
(routeNodeChild w h inB outB stride aux b).2.2.1
(routeNodeChild w h inB outB stride aux b).2.2.2.1
(routeNodeChild w h inB outB stride aux b).2.2.2.2) : _ := ih k _ _ _ _ x hy
simp only [routeFront,List.mem_cons,List.mem_append,List.mem_singleton,List.not_mem_nil,or_false] at hx
rcases hx with rfl| (hl|hr)|rfl
· exact routeFront_self w _ _ _ _ _ 1 (by decide)
· have hh := sub false hl
clear sub
rcases hh with ⟨rq,rd,ri,ro,rs,ra⟩
simp only [routeNodeChild,Prod.snd,Prod.fst,Bool.toNat_false,Nat.zero_mul,Nat.add_zero,
max_self] at ri ro rs ra
have hi : aux+2^(h+1) ≤ aux+auxCount w (h+1) := by rw [auxCount]; simp only [Nat.pow_succ]; omega
have ho : aux+2^(h+1)+2^(h+1)*w ≤ aux+auxCount w (h+1) := by
rw [auxCount]
have hm : (2:ℕ)^h*2 = 2*2^h := by omega
rw [show (2:ℕ)^(h+1)=2*2^h by rw [Nat.pow_succ,hm]]
omega
have ha : aux+2^(h+1)+2*(2^(h+1)*w)+auxCount w h ≤ aux+auxCount w (h+1) := by
rw [auxCount]
have hm : (2:ℕ)^(h+1) = 2*2^h := by rw [Nat.pow_succ,Nat.mul_comm]
nth_rw 1 [hm]
omega
exact ⟨rq,rd.trans (Nat.le_succ _),
ri.trans (max_le (hi.trans (le_max_right _ _)) (ha.trans (le_max_right _ _))),ro.trans (max_le (ho.trans (le_max_right _ _)) (ha.trans (le_max_right _ _))),
rs.trans (le_max_right _ _),ra.trans ha⟩
· have hh := sub true hr
clear sub
rcases hh with ⟨rq,rd,ri,ro,rs,ra⟩
simp only [routeNodeChild,Prod.snd,Prod.fst,Bool.toNat_true,Nat.one_mul,max_self] at ri ro rs ra
have hMono : w ≤ 2^(h+1)*w := by
simpa using Nat.mul_le_mul_right w (Nat.pow_pos (by decide) : 1 ≤ (2:ℕ)^(h+1))
have hPos : (2:ℕ)^(h+1) = 2*2^h := by rw [Nat.pow_succ,Nat.mul_comm]
have hi : aux+2^(h+1)+w ≤ aux+auxCount w (h+1) := by
rw [auxCount]
nth_rw 1 [hPos]
omega
have ho : aux+2^(h+1)+2^(h+1)*w+w ≤ aux+auxCount w (h+1) := by
rw [auxCount]
nth_rw 1 [hPos]
omega
have ha : aux+2^(h+1)+2*(2^(h+1)*w)+auxCount w h+auxCount w h ≤ aux+auxCount w (h+1) := by
rw [auxCount]
nth_rw 1 [hPos]
omega
exact ⟨rq,rd.trans (Nat.le_succ _),
ri.trans (max_le (hi.trans (le_max_right _ _)) (ha.trans (le_max_right _ _))),ro.trans (max_le (ho.trans (le_max_right _ _)) (ha.trans (le_max_right _ _))),
rs.trans (le_max_right _ _),ra.trans ha⟩
· exact routeFront_self w _ _ _ _ _ 3 (by decide)
end CNFEncComplexity.Robson
/- RobsonRouteNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
private abbrev N := encUnary
private abbrev nodeEnc : RouteNode ↪ List Bool := encPair N (encPair N (encPair N (encPair N N)))
private abbrev entryEnc : RouteFrontEntry ↪ List Bool := encPair N nodeEnc
private abbrev frontierEnc : List RouteFrontEntry ↪ List Bool := encList entryEnc
private theorem uAdd {A : Type} {e : A ↪ List Bool} {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e N) (b : ComputableTidilyInPolyTime g e N) :
ComputableTidilyInPolyTime (fun x => f x+g x) e N := unary_add.comp (a.prod b)
private theorem uSub {A : Type} {e : A ↪ List Bool} {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e N) (b : ComputableTidilyInPolyTime g e N) :
ComputableTidilyInPolyTime (fun x => f x-g x) e N := unary_sub.comp (a.prod b)
private theorem uMul {A : Type} {e : A ↪ List Bool} {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e N) (b : ComputableTidilyInPolyTime g e N) :
ComputableTidilyInPolyTime (fun x => f x*g x) e N := unary_mul.comp (a.prod b)
private theorem capRoutePow_poly {A : Type} {e : A ↪ List Bool} {cap j : A → ℕ}
(hc : ComputableTidilyInPolyTime cap e N) (hj : ComputableTidilyInPolyTime j e N) :
ComputableTidilyInPolyTime (fun x => capRoutePow (cap x) (j x)) e N :=
(ComputableInPolyTime.binary_min_unary' hc.computableInPolyTime
(binary_two_pow.comp hj).computableInPolyTime).tidy
private abbrev ExpandArgs := ℕ × ℕ × RouteFrontEntry
private abbrev expandEnc : ExpandArgs ↪ List Bool := encPair N (encPair N entryEnc)
private theorem expandRouteEntry_poly :
ComputableTidilyInPolyTime (fun p : ExpandArgs => expandRouteEntry p.1 p.2.1 p.2.2)
expandEnc frontierEnc := by
have hCap : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.1) expandEnc N := by fun_prop
have hW : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.1) expandEnc N := by fun_prop
have hEntry : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2) expandEnc entryEnc := by fun_prop
have hQ : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.1) expandEnc N := by fun_prop
have hNode : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2) expandEnc nodeEnc := by fun_prop
have hD : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.1) expandEnc N := by fun_prop
have hAux : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.2.2.2.2) expandEnc N := by fun_prop
have hC := uSub hD (const 1)
have hN := capRoutePow_poly hCap hD
have hM := capRoutePow_poly hCap hC
have hV := uAdd hAux hN
have hP := uMul hN hW
have hS := uAdd hV (uMul (const 2) hP)
have hStride := uMul (const 2) hW
have hChildRank : ComputableTidilyInPolyTime
(fun p : ExpandArgs => if p.2.2.2.1-1 = 0 then 2 else 0) expandEnc N := by
simpa only [beq_iff_eq] using (unary_beq hC (const 0)).cond (const 2) (const 0)
have hL := hChildRank.prod (hC.prod (hV.prod
((uAdd hV hP).prod (hStride.prod hS))))
have hR := hChildRank.prod (hC.prod ((uAdd hV hW).prod
((uAdd (uAdd hV hP) hW).prod
(hStride.prod (uAdd hS
(uMul (uMul hC hM) (uAdd (const 1) hStride)))))))
have hAll := cons' ((const (encMid:=N) 1).prod hNode) (cons' hL
(cons' hR (cons' ((const (encMid:=N) 3).prod hNode) (const ([] : List RouteFrontEntry)))))
have hNo := cons' hEntry (const ([] : List RouteFrontEntry))
simpa only [expandRouteEntry,beq_iff_eq] using (unary_beq hQ (const 0)).cond hAll hNo
private theorem expandRoute_poly :
ComputableTidilyInPolyTime
(fun p : ℕ × ℕ × List RouteFrontEntry => expandRoute p.1 p.2.1 p.2.2)
(encPair N (encPair N frontierEnc)) frontierEnc := by
have hL : ComputableTidilyInPolyTime (fun p : ℕ × ℕ × List RouteFrontEntry => p.2.2)
(encPair N (encPair N frontierEnc)) frontierEnc := by fun_prop
have hCap : ComputableTidilyInPolyTime
(fun p : (ℕ × ℕ × List RouteFrontEntry) × RouteFrontEntry => p.1.1)
(encPair (encPair N (encPair N frontierEnc)) entryEnc) N := by fun_prop
have hW : ComputableTidilyInPolyTime
(fun p : (ℕ × ℕ × List RouteFrontEntry) × RouteFrontEntry => p.1.2.1)
(encPair (encPair N (encPair N frontierEnc)) entryEnc) N := by fun_prop
exact flatMapWithInput hL (expandRouteEntry_poly.comp
(hCap.prod (hW.prod (snd (encPair N (encPair N frontierEnc)) entryEnc))))
/-- The capped input lets the construction run in polynomial time even on
arbitrary arguments outside the range of the actual RAM compiler. -/
abbrev RouteArgs := ℕ × ℕ × ℕ × ℕ
abbrev routeArgsEnc : RouteArgs ↪ List Bool := encPair N (encPair N (encPair N N))
private def capWidth (p : RouteArgs) : ℕ := 2*p.2.2.2+1
private def rootDepth (p : RouteArgs) : ℕ := min p.2.1 p.2.2.2.size
private def rootBase (p : RouteArgs) : ℕ := p.2.2.1
private def rootWord (p : RouteArgs) : ℕ := p.1
private theorem rootDepth_poly : ComputableTidilyInPolyTime rootDepth routeArgsEnc N := by
have hRequested : ComputableTidilyInPolyTime (fun p : RouteArgs => p.2.1) routeArgsEnc N := by fun_prop
have hCap : ComputableTidilyInPolyTime (fun p : RouteArgs => p.2.2.2) routeArgsEnc N := by fun_prop
exact unary_min.comp (hRequested.prod (unary_size_poly.comp hCap))
private theorem capWidth_poly : ComputableTidilyInPolyTime capWidth routeArgsEnc N := by
unfold capWidth
fun_prop
private theorem rootWord_poly : ComputableTidilyInPolyTime rootWord routeArgsEnc N := by unfold rootWord; fun_prop
private theorem rootBase_poly : ComputableTidilyInPolyTime rootBase routeArgsEnc N := by unfold rootBase; fun_prop
private theorem rootDepth_bound (p : RouteArgs) : 2^rootDepth p ≤ capWidth p := by
exact (Nat.pow_le_pow_right (by decide) (min_le_right _ _)).trans (pow2_size_le _)
private theorem rootLaneCount_poly :
ComputableTidilyInPolyTime (fun p => 2^rootDepth p) routeArgsEnc N :=
unary_pow2_of_bound rootDepth_poly capWidth_poly rootDepth_bound
private def initialFront (p : RouteArgs) : List RouteFrontEntry :=
let d := rootDepth p
let b := rootBase p
let w := rootWord p
let row := 2^d*w
[(if d = 0 then 2 else 0,d,b,b+row,w,b+(row+row))]
private theorem initialFront_poly : ComputableTidilyInPolyTime initialFront routeArgsEnc frontierEnc := by
have hLane := uMul rootLaneCount_poly rootWord_poly
have hFlag : ComputableTidilyInPolyTime (fun p => if rootDepth p = 0 then 2 else 0) routeArgsEnc N := by
simpa only [beq_iff_eq] using (unary_beq rootDepth_poly (const 0)).cond (const 2) (const 0)
exact cons' (hFlag.prod (rootDepth_poly.prod (rootBase_poly.prod
((uAdd rootBase_poly hLane).prod (rootWord_poly.prod
(uAdd rootBase_poly (uAdd hLane hLane))))))) (const ([] : List RouteFrontEntry))
private theorem initFront_eq (p : RouteArgs) :
initialFront p = routeFront (rootWord p) 0 (rootDepth p) (rootBase p)
(rootBase p+2^rootDepth p*rootWord p) (rootWord p)
(rootBase p+(2^rootDepth p*rootWord p+2^rootDepth p*rootWord p)) := by
unfold initialFront
cases hd : rootDepth p <;> rfl
private theorem expandedFront_eq (p : RouteArgs) (i : ℕ) :
(expandRoute (capWidth p) (rootWord p))^[i] (initialFront p) =
routeFront (rootWord p) i (rootDepth p) (rootBase p)
(rootBase p+2^rootDepth p*rootWord p) (rootWord p)
(rootBase p+(2^rootDepth p*rootWord p+2^rootDepth p*rootWord p)) := by
induction i with
| zero => exact initFront_eq p
| succ i ih =>
rw [Function.iterate_succ_apply',ih,expandRoute_correct _ _ _ _ _ _ _ _ (rootDepth_bound p)]
private def routeSizeBound (p : RouteArgs) : ℕ :=
let w := rootWord p
let d := rootDepth p
let n := capWidth p
let b := rootBase p
1 + 4*n*(32 + 64*(d+w+b+2*n*w+d*n*(1+2*w)))
private theorem routeSizeBound_poly : ComputableTidilyInPolyTime routeSizeBound routeArgsEnc N := by
have hDW := uAdd rootDepth_poly (uAdd rootWord_poly rootBase_poly)
have hL := uMul (const 2) (uMul capWidth_poly rootWord_poly)
have hAux := uMul (uMul rootDepth_poly capWidth_poly)
(uAdd (const 1) (uMul (const 2) rootWord_poly))
have hSum := uAdd (uAdd hDW hL) hAux
have h := uAdd (const 1) (uMul (uMul (const 4) capWidth_poly)
(uAdd (const 32) (uMul (const 64) hSum)))
convert h using 1
funext p
unfold routeSizeBound
ring
private theorem frontier_encoded_bound (p : RouteArgs) (i : ℕ) :
(frontierEnc ((expandRoute (capWidth p) (rootWord p))^[i] (initialFront p))).length ≤ routeSizeBound p := by
rw [expandedFront_eq]
let w := rootWord p
let d := rootDepth p
let n := capWidth p
let b := rootBase p
let m := b+(2^d*w+2^d*w)
let xs := routeFront w i d b (b+2^d*w) w m
let cap := 32 + 64*(d+w+b+2*n*w+d*n*(1+2*w))
change (frontierEnc xs).length ≤ 1+4*n*cap
have hn : 2^d ≤ n := rootDepth_bound p
have hMul : 2^d*w ≤ n*w := Nat.mul_le_mul_right _ hn
have hm : m ≤ b+2*n*w := by unfold m; linarith
have hA : auxCount w d ≤ d*n*(1+2*w) := by
rw [auxCount_exact]
exact Nat.mul_le_mul_right _ (Nat.mul_le_mul_left _ hn)
have hOne (x : RouteFrontEntry) (hx : x ∈ xs) : 2*(entryEnc x).length+1 ≤ cap := by
obtain ⟨hq,hd,hI,hO,hS,hY⟩ := routeFront_coordinates _ _ _ _ _ _ _ x hx
have hIn : routeNodeInput x.2 ≤ b+2*n*w+d*n*(1+2*w) := by omega
have hOut : routeNodeOutput x.2 ≤ b+2*n*w+d*n*(1+2*w) := by omega
have hStride : routeNodeStride x.2 ≤ 2*w := by omega
have hY' : routeNodeAux x.2 ≤ b+2*n*w+d*n*(1+2*w) := by omega
simp only [routeNodeDepth,routeNodeInput,routeNodeOutput,routeNodeStride,routeNodeAux] at *
simp only [entryEnc,nodeEnc,N,length_encPair,encUnary_apply,List.length_replicate]
unfold cap
omega
have hList (l : List RouteFrontEntry) (hl : ∀ x ∈ l, 2*(entryEnc x).length+1 ≤ cap) :
(frontierEnc l).length ≤ 1+l.length*cap := by
induction l with
| nil => simp [length_encList]
| cons x xs ih =>
have hx := hl x (List.mem_cons_self)
have ht := ih (fun y hy => hl y (List.mem_cons_of_mem _ hy))
have hLen : (frontierEnc (x::xs)).length = (frontierEnc xs).length+(2*(entryEnc x).length+1) := by
simp only [frontierEnc,length_encList,List.map_cons,List.sum_cons]
omega
rw [hLen,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
have hc : xs.length ≤ 4*n :=
(Nat.le_add_right _ _).trans ((routeFront_card w i d b (b+2^d*w) w m).trans (Nat.mul_le_mul_left _ hn))
exact (hList _ hOne).trans (Nat.add_le_add_left (Nat.mul_le_mul_right cap hc) 1)
private def finishedFront (p : RouteArgs) : List RouteFrontEntry :=
(expandRoute (capWidth p) (rootWord p))^[rootDepth p] (initialFront p)
private theorem finishedFront_poly : ComputableTidilyInPolyTime finishedFront routeArgsEnc frontierEnc := by
have hBound : PolyBounded (fun p => (routeArgsEnc p).length) routeSizeBound := routeSizeBound_poly.polyBounded
have step := expandRoute_poly.comp
((capWidth_poly.comp (fst routeArgsEnc frontierEnc)).prod
((rootWord_poly.comp (fst routeArgsEnc frontierEnc)).prod (snd routeArgsEnc frontierEnc)))
exact iterateWith id' rootDepth_poly initialFront_poly step hBound
(fun p i _ => frontier_encoded_bound p i)
def boundedColumnGate (w half n inB outB step aux : ℕ) (exit : Bool) (a b j : ℕ) : Gate :=
let x := 2*a+b
let y := 2*a+(1-b)
let sel := aux+exit.toNat*half+a
let inside := aux+n+exit.toNat*(n*w)
if exit then
.mux (outB+x*step+j) sel (inside+y*w+j) (inside+x*w+j)
else
.mux (inside+x*w+j) sel (inB+y*step+j) (inB+x*step+j)
private theorem boundedColumnGate_poly {A : Type} {e : A ↪ List Bool}
{w half n inB outB step aux a b j : A → ℕ} {exit : A → Bool}
(hw : ComputableTidilyInPolyTime w e N) (hh : ComputableTidilyInPolyTime half e N)
(hn : ComputableTidilyInPolyTime n e N) (hi : ComputableTidilyInPolyTime inB e N)
(ho : ComputableTidilyInPolyTime outB e N) (hs : ComputableTidilyInPolyTime step e N)
(hu : ComputableTidilyInPolyTime aux e N) (he : ComputableTidilyInPolyTime exit e encBool)
(ha : ComputableTidilyInPolyTime a e N) (hb : ComputableTidilyInPolyTime b e N)
(hj : ComputableTidilyInPolyTime j e N) :
ComputableTidilyInPolyTime (fun x => boundedColumnGate (w x) (half x) (n x) (inB x)
(outB x) (step x) (aux x) (exit x) (a x) (b x) (j x)) e gateEnc := by
have x2 := uMul (const 2) ha
have x := uAdd x2 hb
have y := uAdd x2 (uSub (const 1) hb)
have ex := bool_toUnary.comp he
have sel := uAdd (uAdd hu (uMul ex hh)) ha
have inside := uAdd (uAdd hu hn) (uMul ex (uMul hn hw))
have pos := uAdd (uAdd inside (uMul x hw)) hj
have cross := uAdd (uAdd inside (uMul y hw)) hj
have ip := uAdd (uAdd hi (uMul x hs)) hj
have ic := uAdd (uAdd hi (uMul y hs)) hj
have o := uAdd (uAdd ho (uMul x hs)) hj
exact he.cond (gate_mux o sel cross pos) (gate_mux pos sel ic ip)
private def routeOneBounded (cap w : ℕ) (p : RouteFrontEntry) : List Gate :=
let (q,d,inB,outB,stride,aux) := p
if q = 2 then (List.range w).map (fun j => Gate.copy (outB+j) (inB+j))
else let half := capRoutePow cap (d-1)
let n := capRoutePow cap d
(List.range half).flatMap fun a => [0,1].flatMap fun b => (List.range w).map
fun j => boundedColumnGate w half n inB outB stride aux (q == 3) a b j
private theorem routeOneBounded_exact (cap w : ℕ) (p : RouteFrontEntry)
(hp : 2^routeNodeDepth p.2 ≤ cap)
(hKind : p.1 ≠ 2 → 0 < routeNodeDepth p.2) :
routeOneBounded cap w p = routeOneGates w p := by
rcases p with ⟨q,d,ib,ob,st,ax⟩
by_cases hQ : q = 2
· simp [routeOneBounded,routeOneGates,hQ]
· have hd : 0 < d := hKind hQ
have hpow : 2^(d-1+1) = (2:ℕ)^d := by congr 1; omega
have hp2 : 2^(d-1) ≤ cap :=
(Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _)).trans hp
have hp0 : 2^d ≤ cap := hp
simp only [routeOneBounded,routeOneGates,hQ,if_false,capRoutePow,
min_eq_right hp2,min_eq_right hp0,nodeColumn,boundedColumnGate,nodeColumnGate,hpow]
private theorem routeFront_active_depth (w k h inB outB stride aux : ℕ) (e : RouteFrontEntry)
(he : e ∈ routeFront w k h inB outB stride aux) :
e.1 ≠ 2 → 0 < routeNodeDepth e.2 := by
induction h generalizing k inB outB stride aux e with
| zero =>
simp only [routeFront,List.mem_singleton] at he
subst e
exact fun h => (h rfl).elim
| succ h ih =>
cases k with
| zero =>
simp only [routeFront,List.mem_singleton] at he
subst e
exact fun _ => Nat.succ_pos _
| succ k =>
simp only [routeFront,List.mem_cons,List.mem_append,List.mem_singleton,List.not_mem_nil,or_false] at he
rcases he with rfl|(hl|hr)|rfl
· exact fun _ => Nat.succ_pos _
· exact ih _ _ _ _ _ _ hl
· exact ih _ _ _ _ _ _ hr
· exact fun _ => Nat.succ_pos _
private theorem routeOneBounded_poly :
ComputableTidilyInPolyTime (fun p : ExpandArgs => routeOneBounded p.1 p.2.1 p.2.2)
expandEnc (encList gateEnc) := by
have hCap : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.1) expandEnc N := by fun_prop
have hW : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.1) expandEnc N := by fun_prop
have hQ : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.1) expandEnc N := by fun_prop
have hD : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.1) expandEnc N := by fun_prop
have hIn : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.2.1) expandEnc N := by fun_prop
have hOut : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.2.2.1) expandEnc N := by fun_prop
have hStep : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.2.2.2.1) expandEnc N := by fun_prop
have hAux : ComputableTidilyInPolyTime (fun p : ExpandArgs => p.2.2.2.2.2.2.2) expandEnc N := by fun_prop
have hHalf := capRoutePow_poly hCap (uSub hD (const 1))
have hN := capRoutePow_poly hCap hD
have hExit := unary_beq hQ (const 3)
have hCopy := mapWithInput (f := fun (p : ExpandArgs) j =>
Gate.copy (p.2.2.2.2.2.1+j) (p.2.2.2.2.1+j)) (range.comp hW) (gate_copy
(uAdd (hOut.comp (fst expandEnc N)) (snd expandEnc N))
(uAdd (hIn.comp (fst expandEnc N)) (snd expandEnc N)))
let EA := encPair expandEnc N
have hAB := fst expandEnc N
have ha := snd expandEnc N
let gb (p : ExpandArgs × ℕ) (b : ℕ) :=
(List.range p.1.2.1).map (fun j => boundedColumnGate p.1.2.1
(capRoutePow p.1.1 (p.1.2.2.2.1-1)) (capRoutePow p.1.1 p.1.2.2.2.1)
p.1.2.2.2.2.1 p.1.2.2.2.2.2.1 p.1.2.2.2.2.2.2.1 p.1.2.2.2.2.2.2.2
(p.1.2.2.1 == 3) p.2 b j)
have hMul (b : ℕ) :
ComputableTidilyInPolyTime (fun p : ExpandArgs × ℕ => gb p b) EA (encList gateEnc) := by
let hf := fst EA N
have hArg := hAB.comp hf
unfold gb
exact mapWithInput (f := fun (p : ExpandArgs × ℕ) j =>
boundedColumnGate p.1.2.1 (capRoutePow p.1.1 (p.1.2.2.2.1-1))
(capRoutePow p.1.1 p.1.2.2.2.1) p.1.2.2.2.2.1 p.1.2.2.2.2.2.1
p.1.2.2.2.2.2.2.1 p.1.2.2.2.2.2.2.2 (p.1.2.2.1 == 3) p.2 b j)
(range.comp (hW.comp hAB)) (boundedColumnGate_poly
(hW.comp hArg) (hHalf.comp hArg) (hN.comp hArg) (hIn.comp hArg) (hOut.comp hArg)
(hStep.comp hArg) (hAux.comp hArg) (hExit.comp hArg) (ha.comp hf) (const b) (snd EA N))
have hBranch := flatMapConst (f := gb) [0,1] (fun b _ => hMul b)
have hRows := flatMapWithInput (f := fun (p : ExpandArgs) a => [0,1].flatMap (gb (p,a)))
(range.comp hHalf) hBranch
simpa only [routeOneBounded,beq_iff_eq,gb,Function.comp_def] using (unary_beq hQ (const 2)).cond hCopy hRows
def boundedRouteGates (p : RouteArgs) : List Gate :=
(finishedFront p).flatMap (routeOneBounded (capWidth p) (rootWord p))
theorem boundedRouteGates_poly : ComputableTidilyInPolyTime boundedRouteGates routeArgsEnc (encList gateEnc) := by
let hP := fst routeArgsEnc entryEnc
exact flatMapWithInput finishedFront_poly (routeOneBounded_poly.comp
((capWidth_poly.comp hP).prod ((rootWord_poly.comp hP).prod (snd routeArgsEnc entryEnc))))
theorem boundedRouteGates_eq (w h base cap : ℕ) (hCap : 2^h ≤ cap) :
boundedRouteGates (w,h,base,cap) = routeNamedGates (fun v : RouteVar h (Fin w) =>
base+(routeLabel h w v).val) := by
let p : RouteArgs := (w,h,base,cap)
have hdep : rootDepth p = h := by
have hh := (Nat.lt_size.mpr hCap).le
exact min_eq_left hh
unfold boundedRouteGates finishedFront
rw [expandedFront_eq,hdep]
change (routeFront w h h base (base+2^h*w) w (base+(2^h*w+2^h*w))).flatMap
(routeOneBounded (capWidth p) w) = _
have hL : (routeFront w h h base (base+2^h*w) w (base+(2^h*w+2^h*w))).flatMap
(routeOneBounded (capWidth p) w) =
(routeFront w h h base (base+2^h*w) w (base+(2^h*w+2^h*w))).flatMap (routeOneGates w) := by
apply List.flatMap_congr
intro x hx
have hxD := (routeFront_coordinates _ _ _ _ _ _ _ x hx).2.1
have hPow := (Nat.pow_le_pow_right (by decide) hxD).trans (hdep ▸ rootDepth_bound p)
exact routeOneBounded_exact _ _ _ hPow (routeFront_active_depth _ _ _ _ _ _ _ x hx)
rw [hL,routeFront_exact _ _ _ _ _ _ _ le_rfl]
have hName := funext (nodeRouteName_root w h base)
exact congrArg routeNamedGates hName
end CNFEncComplexity.Robson
/- RobsonGuardNative -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime
theorem guardWithLiteral_poly {A : Type} {input : A ↪ List Bool} {condition : A → Literal}
{body : A → List Gate}
(hl : ComputableTidilyInPolyTime (fun a => literalN (condition a).negate) input encUnary)
(hg : ComputableTidilyInPolyTime body input (encList gateEnc)) :
ComputableTidilyInPolyTime (fun a => guarded (condition a) (body a)) input (encList gateEnc) := by
let e := encList encUnary
have hFormula : ComputableTidilyInPolyTime (fun a => formulaN (compile (body a)))
input (encList e) :=
(compile_polytime.tidy.comp hg).of_enc_eq (fun _ => rfl)
have hTag := fst input e
have hClause := snd input e
have hFields := cons' (const 8) (cons' (hl.comp hTag) hClause)
have hList := mapWithInput
(f:=fun (a : A) (row : List ℕ) => 8 :: literalN (condition a).negate :: row) hFormula hFields
apply hList.of_enc_eq
intro a
change (encList gateEnc) (guarded (condition a) (body a)) = (encList e) _
have he (ls : List Gate) :
(encList gateEnc) ls = encList e (ls.map Gate.code) := by
induction ls with
| nil => rfl
| cons g gs ih => rw [List.map_cons,encList_cons,encList_cons,ih]; rfl
rw [he,guarded,List.map_map]
congr 1
simp [formulaN,List.map_map,Function.comp_def,Gate.code,clauseN]
theorem guardedPos_poly {A : Type} {input : A ↪ List Bool} {flag : A → ℕ}
{body : A → List Gate}
(hf : ComputableTidilyInPolyTime flag input encUnary)
(hg : ComputableTidilyInPolyTime body input (encList gateEnc)) :
ComputableTidilyInPolyTime (fun a => guarded (.Pos (flag a)) (body a))
input (encList gateEnc) :=
guardWithLiteral_poly (condition:=fun a => .Pos (flag a))
(unary_mul.comp ((const 2).prod hf)) hg
theorem guardedNeg_poly {A : Type} {input : A ↪ List Bool} {flag : A → ℕ}
{body : A → List Gate}
(hf : ComputableTidilyInPolyTime flag input encUnary)
(hg : ComputableTidilyInPolyTime body input (encList gateEnc)) :
ComputableTidilyInPolyTime (fun a => guarded (.Neg (flag a)) (body a))
input (encList gateEnc) :=
guardWithLiteral_poly (condition:=fun a => .Neg (flag a))
(unary_add.comp ((unary_mul.comp ((const 2).prod hf)).prod (const 1))) hg
abbrev gateBranchEnc : (ℕ×List Gate) ↪ List Bool := encPair encUnary (encList gateEnc)
theorem choiceGates_poly :
ComputableTidilyInPolyTime choiceGates (encList gateBranchEnc) (encList gateEnc) := by
have hs := fst encUnary (encList gateEnc)
have hg := snd encUnary (encList gateEnc)
have hb := guardedPos_poly hs hg
have hRun : ComputableTidilyInPolyTime
(fun p : List (ℕ×List Gate) × (ℕ×List Gate) => guarded (.Pos p.2.1) p.2.2)
(encPair (encList gateBranchEnc) gateBranchEnc) (encList gateEnc) :=
hb.comp (snd (encList gateBranchEnc) gateBranchEnc)
have hBlocks := flatMapWithInput (f:=fun (_ : List (ℕ×List Gate)) p => guarded (.Pos p.1) p.2)
(id' (encIn:=encList gateBranchEnc)) hRun
have hSign := unary_add.comp ((unary_mul.comp ((const 2).prod hs)).prod (const 1))
have hCodes := map hSign
have hHead := gate_assert (c:=fun l : List (ℕ×List Gate) => l.map (fun p => .Pos p.1)) (by
simpa only [clauseN,List.map_map,Function.comp_def,literalN] using hCodes)
exact cons' hHead hBlocks
end CNFEncComplexity.RobsonCNF
/- RobsonMemCheckNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
private abbrev NG := encList gateEnc
private abbrev NU := encUnary
private theorem mAdd {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e NU) (b : ComputableTidilyInPolyTime g e NU) :
ComputableTidilyInPolyTime (fun x => f x+g x) e NU := unary_add.comp (a.prod b)
private theorem mSub {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e NU) (b : ComputableTidilyInPolyTime g e NU) :
ComputableTidilyInPolyTime (fun x => f x-g x) e NU := unary_sub.comp (a.prod b)
private theorem mMul {f g : A → ℕ}
(a : ComputableTidilyInPolyTime f e NU) (b : ComputableTidilyInPolyTime g e NU) :
ComputableTidilyInPolyTime (fun x => f x*g x) e NU := unary_mul.comp (a.prod b)
private theorem memBand_poly {w lo hi : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU)
(hl : ComputableTidilyInPolyTime lo e NU) (hh : ComputableTidilyInPolyTime hi e NU) :
ComputableTidilyInPolyTime (fun x => bitBand (w x) (lo x) (hi x)) e (encList NU) := by
let a := fst e NU
let i := snd e NU
have l := unary_le' (hl.comp a) i
have h := unary_lt' i (hh.comp a)
have hh1 : ComputableTidilyInPolyTime (fun q : A×ℕ => decide (lo q.1 ≤ q.2 ∧ q.2 < hi q.1))
(encPair e NU) encBool := by
convert l.cond h (const false) using 1
funext p
by_cases he : lo p.1 ≤ p.2 <;> simp [he,Function.comp_def]
exact filterWithInput (test:=fun x j => decide (lo x ≤ j ∧ j < hi x)) (range.comp hw) hh1
private def initCutoff (w j : ℕ) : ℕ := min (w+1) (2^j)-1
private theorem initCutoff_eq (w j : ℕ) : initCutoff w j = min w (initHigh j) := by
unfold initCutoff initHigh
omega
private theorem initCutoff_poly {w j : A → ℕ} (hw : ComputableTidilyInPolyTime w e NU)
(hj : ComputableTidilyInPolyTime j e NU) :
ComputableTidilyInPolyTime (fun x => initCutoff (w x) (j x)) e NU := by
have hCap := mAdd hw (const 1)
have hPow := binary_two_pow.comp hj
exact mSub (ComputableInPolyTime.binary_min_unary' hCap.computableInPolyTime
hPow.computableInPolyTime).tidy (const 1)
private theorem bitBand_clip (w lo hi : ℕ) :
bitBand w (min w lo) (min w hi) = bitBand w lo hi := by
unfold bitBand
apply List.filter_congr
intro i hi'
have h : i < w := List.mem_range.mp hi'
have he : (min w lo ≤ i ∧ i < min w hi) ↔ (lo ≤ i ∧ i < hi) := by omega
simpa only [he]
private theorem initialFlagGates_poly {w tier flag : A → ℕ} {addr : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (ht : ComputableTidilyInPolyTime tier e NU)
(hf : ComputableTidilyInPolyTime flag e NU)
(ha : ComputableTidilyInPolyTime (fun p : A×ℕ => addr p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun x => initialFlagGates (tier x) (w x) (flag x) (addr x))
e NG := by
have hHighClipped := memBand_poly hw (initCutoff_poly hw ht) hw
have hHigh : ComputableTidilyInPolyTime (fun x => bitBand (w x) (initHigh (tier x)) (w x))
e (encList NU) := by
convert hHighClipped using 1
funext p
conv_lhs => rw [← bitBand_clip (w p) (initHigh (tier p)) (w p)]
rw [min_self,initCutoff_eq]
have hMidClipped := memBand_poly hw (initCutoff_poly hw (mSub ht (const 1)))
(initCutoff_poly hw ht)
have hMid : ComputableTidilyInPolyTime
(fun x => bitBand (w x) (initHigh (tier x-1)) (initHigh (tier x))) e (encList NU) := by
convert hMidClipped using 1
funext x
simp only [initCutoff_eq,bitBand_clip]
let fa := fst e NU
have hg (hband : A → List ℕ) (hb : ComputableTidilyInPolyTime hband e (encList NU)) :
ComputableTidilyInPolyTime (fun x => clauseN ((hband x).map (fun j => Literal.Pos (addr x j))))
e (encList NU) := by
simpa only [clauseN,List.map_map,Function.comp_def] using
mapWithInput (f:=fun x j => literalN (.Pos (addr x j))) hb (positive_poly ha)
have hHighL := hg _ hHigh
have hMidL := hg _ hMid
have hNoHigh := mapWithInput
(f := fun x i => Gate.assert [.Neg (flag x),.Neg (addr x i)]) hHigh
(assert2_poly (negative_poly (hf.comp fa)) (negative_poly ha))
have hHead0 := gate_assert (c:=fun x => Literal.Pos (flag x) ::
(bitBand (w x) (initHigh (tier x)) (w x)).map (fun i => .Pos (addr x i)))
(cons' (positive_poly hf) hHighL)
have hHead1 := gate_assert (c:=fun x => Literal.Neg (flag x) ::
(bitBand (w x) (initHigh (tier x-1)) (initHigh (tier x))).map (fun i => .Pos (addr x i)))
(cons' (negative_poly hf) hMidL)
have hMidTail := mapWithInput (f:=fun x i => Gate.assert
(.Pos (flag x) :: .Neg (addr x i) ::
(bitBand (w x) (initHigh (tier x)) (w x)).map (fun j => .Pos (addr x j)))) hMid
(gate_assert (cons' (positive_poly (hf.comp fa)) (cons' (negative_poly ha) (hHighL.comp fa))))
have hh := (unary_beq ht (const 0)).cond (cons' hHead0 hNoHigh)
(cons' hHead1 (listAppend' hNoHigh hMidTail))
convert hh using 1
funext p
cases hp : tier p <;> simp [initialFlagGates,hp,Function.comp_def]
private theorem zeroOptGates_poly {w flag : A → ℕ} {bits : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU)
(hf : ComputableTidilyInPolyTime flag e NU)
(ha : ComputableTidilyInPolyTime (fun p : A×ℕ => bits p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun x => zeroOptGates (flag x) (bits x) (w x)) e NG := by
apply guardedPos_poly hf
unfold wordConst
simpa only [Nat.zero_testBit,Function.comp_def] using
mapWithInput (f:=fun x i => Gate.pin (bits x i) false) (range.comp hw) (gate_pin false ha)
def decodeGroupTier (code : ℕ) : Option ℕ :=
if code = 0 then none else some (code-1)
private theorem groupInitialGates_poly {w code before : A → ℕ} {addr value : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hc : ComputableTidilyInPolyTime code e NU)
(hb : ComputableTidilyInPolyTime before e NU)
(ha : ComputableTidilyInPolyTime (fun p : A×ℕ => addr p.1 p.2) (encPair e NU) NU)
(hv : ComputableTidilyInPolyTime (fun p : A×ℕ => value p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun x => groupInitialGates (decodeGroupTier (code x))
(w x) (before x) (addr x) (value x)) e NG := by
have hI := initialFlagGates_poly hw (mSub hc (const 1)) hb ha
have hZ := zeroOptGates_poly hw hb hv
have hg := (unary_beq hc (const 0)).cond (cons' (gate_pin false hb) (const [])) (listAppend' hI hZ)
convert hg using 1
funext x
by_cases he : code x = 0 <;> simp [decodeGroupTier,groupInitialGates,he]
private theorem memoryOptEqual_poly {w p q : A → ℕ} {x y : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hp : ComputableTidilyInPolyTime p e NU)
(hq : ComputableTidilyInPolyTime q e NU)
(hx : ComputableTidilyInPolyTime (fun a : A×ℕ => x a.1 a.2) (encPair e NU) NU)
(hy : ComputableTidilyInPolyTime (fun a : A×ℕ => y a.1 a.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun a => memoryOptEqual (p a) (q a) (x a) (y a) (w a)) e NG := by
have hWord := mapWithInput (f:=fun a i => Gate.copy (x a i) (y a i)) (range.comp hw) (gate_copy hx hy)
exact cons' (gate_copy hp hq) (guardedPos_poly hp hWord)
private theorem groupRowOffset {i : A → ℕ} {row : A → ℕ → ℕ}
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU)
(hi : ComputableTidilyInPolyTime i e NU) :
ComputableTidilyInPolyTime (fun x => row x (i x)) e NU :=
hr.comp ((id' (encIn:=e)).prod hi)
private theorem laneAddr_poly {h : A → ℕ} {row : A → ℕ → ℕ}
(hh : ComputableTidilyInPolyTime h e NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun p : A×ℕ => laneAddress (h p.1) (row p.1) p.2)
(encPair e NU) NU :=
hr.comp ((fst e NU).prod (mAdd (mAdd (const 1) (hh.comp (fst e NU))) (snd e NU)))
private theorem laneValBefore_poly {w h : A → ℕ} {row : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun p : A×ℕ => laneBefore (w p.1) (h p.1) (row p.1) p.2)
(encPair e NU) NU := by
let x := fst e NU
let i := snd e NU
exact hr.comp (x.prod
(mAdd (mAdd (mAdd (mAdd (const 1) (hh.comp x)) (hw.comp x)) (const 1)) i))
private theorem laneValAfter_poly {w h : A → ℕ} {row : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun p : A×ℕ => laneAfter (w p.1) (h p.1) (row p.1) p.2)
(encPair e NU) NU := by
let x := fst e NU
let i := snd e NU
have h0 := hw.comp x
exact hr.comp (x.prod
(mAdd (mAdd (mAdd (mAdd (mAdd (const 1) (hh.comp x)) h0) (mAdd (const 1) h0)) (const 1)) i))
private theorem laneKey_poly {h : A → ℕ} {row : A → ℕ → ℕ}
(hh : ComputableTidilyInPolyTime h e NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun p : A×ℕ => laneKey (h p.1) (row p.1) p.2)
(encPair e NU) NU := by
let x := fst e NU
let i := snd e NU
have hD := hh.comp x
have hT := hr.comp (x.prod (mAdd (const 1) i))
have hA := hr.comp (x.prod (mAdd (mAdd (const 1) hD) (mSub i hD)))
simpa [laneKey,joinKey,Function.comp_def,laneTime,laneAddress] using
(unary_lt' i hD).ite' hT hA
private theorem laneInit_poly {w h code : A → ℕ} {row : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hc : ComputableTidilyInPolyTime code e NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => row p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun a => laneInit (decodeGroupTier (code a)) (w a) (h a) (row a)) e NG := by
have hP := groupRowOffset hr (const 0)
have hB := groupRowOffset hr (mAdd (mAdd (const 1) hh) hw)
exact guardedPos_poly hP (groupInitialGates_poly hw hc hB (laneAddr_poly hh hr)
(laneValBefore_poly hw hh hr))
private theorem lanePair_poly {w h code base : A → ℕ} {l r : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hc : ComputableTidilyInPolyTime code e NU) (hb : ComputableTidilyInPolyTime base e NU)
(hl : ComputableTidilyInPolyTime (fun p : A×ℕ => l p.1 p.2) (encPair e NU) NU)
(hr : ComputableTidilyInPolyTime (fun p : A×ℕ => r p.1 p.2) (encPair e NU) NU) :
ComputableTidilyInPolyTime (fun a => lanePair (decodeGroupTier (code a)) (w a) (h a)
(base a) (l a) (r a)) e NG := by
have hW := mAdd hh hw
have hC := mAdd (mAdd hb (mMul (const 4) hW)) (const 2)
have hRi := laneAddr_poly hh hr
have hLi := laneAddr_poly hh hl
have hComp := listAppend'
(compareCircuit_polytime (lhs := fun a => laneKey (h a) (r a))
(rhs := fun a => laneKey (h a) (l a)) hb hW (laneKey_poly hh hr) (laneKey_poly hh hl))
(compareCircuit_polytime (lhs := fun a => laneAddress (h a) (l a))
(rhs := fun a => laneAddress (h a) (r a)) hC hw hLi hRi)
have hLT := mAdd hb (mMul (const 4) hW)
have hEQ := mAdd (mAdd hC (mMul (const 4) hw)) (const 1)
have hL := groupRowOffset hl (const 0)
have hR := groupRowOffset hr (const 0)
have hB := groupRowOffset hr (mAdd (mAdd (const 1) hh) hw)
have hA := groupRowOffset hl (mAdd (mAdd (mAdd (const 1) hh) hw) (mAdd (const 1) hw))
have hKeep := memoryOptEqual_poly (x := fun a => laneAfter (w a) (h a) (l a))
(y := fun a => laneBefore (w a) (h a) (r a)) hw hA hB
(laneValAfter_poly hw hh hl) (laneValBefore_poly hw hh hr)
have hNew := groupInitialGates_poly (addr := fun a => laneAddress (h a) (r a))
(value := fun a => laneBefore (w a) (h a) (r a)) hw hc hB hRi (laneValBefore_poly hw hh hr)
have hGate := cons' (assert2_poly (positive_poly hL) (negative_poly hR))
(cons' (assert3_poly (negative_poly hL) (negative_poly hR) (negative_poly hLT))
(guardedPos_poly hL (guardedPos_poly hR
(listAppend' (guardedPos_poly hEQ hKeep) (guardedNeg_poly hEQ hNew)))))
exact listAppend' hComp hGate
private theorem memLaneWidth_poly {w h : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU) :
ComputableTidilyInPolyTime (fun a => memLaneWidth (w a) (h a)) e NU :=
let a := mAdd (const 1) hw
mAdd (mAdd (mAdd (mAdd (const 1) hh) hw) a) a
private theorem memRouteTop_poly {w h base : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU) :
ComputableTidilyInPolyTime (fun a => memRouteTop (w a) (h a) (base a)) e NU := by
have hW := memLaneWidth_poly hw hh
have hB := mMul hn hW
have hC := mMul (mMul hh hn) (mAdd (const 1) (mMul (const 2) hW))
simpa only [memRouteTop,auxCount_exact] using mAdd hb (mAdd hB (mAdd hB hC))
private theorem memEdgeBase_poly {w h base idx : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU)
(hi : ComputableTidilyInPolyTime idx e NU) :
ComputableTidilyInPolyTime (fun a => memRouteTop (w a) (h a) (base a) + idx a*memEdgeStride (w a) (h a)) e NU :=
mAdd (memRouteTop_poly hw hh hb hn) (mMul hi
(mAdd (mAdd (mAdd (mMul (const 4) (mAdd hh hw)) (const 2)) (mMul (const 4) hw)) (const 2)))
private def memOutputNat (w h base n i j : ℕ) : ℕ :=
if j < memLaneWidth w h then base+n*memLaneWidth w h+i*memLaneWidth w h+j else base
private theorem memOutputNat_eq (w h base : ℕ) (i : Fin (2^h)) (j : ℕ) :
memOutputNat w h base (2^h) i.val j = memOutputLane w h base i j := by
by_cases hJ : j < memLaneWidth w h
· simp only [memOutputNat,memOutputLane,if_pos hJ,dif_pos hJ,memRouteName,
← nodeRouteName_root,rootRouteNode,nodeRouteName,routeNodeDepth,routeNodeOutput,routeNodeStride,
Equiv.apply_symm_apply]
erw [(wireLabel h).apply_symm_apply i]
· simp [memOutputNat,memOutputLane,hJ]
private theorem memInputLane_val (w h base : ℕ) (i : Fin (2^h)) (j : ℕ) (hJ : j < memLaneWidth w h) :
memInputLane w h base i j = base+i.val*memLaneWidth w h+j := by
simp only [memInputLane,dif_pos hJ,memRouteName,← nodeRouteName_root,
rootRouteNode,nodeRouteName,routeNodeDepth,routeNodeInput,routeNodeStride,Equiv.apply_symm_apply]
erw [(wireLabel h).apply_symm_apply i]
private theorem memOutputNat_poly {w h base n i j : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hn : ComputableTidilyInPolyTime n e NU)
(hi : ComputableTidilyInPolyTime i e NU) (hj : ComputableTidilyInPolyTime j e NU) :
ComputableTidilyInPolyTime (fun a => memOutputNat (w a) (h a) (base a) (n a) (i a) (j a)) e NU := by
have hW := memLaneWidth_poly hw hh
have h := (unary_lt' hj hW).ite' (mAdd (mAdd (mAdd hb (mMul hn hW)) (mMul hi hW)) hj) hb
simpa only [memOutputNat,decide_eq_true_eq] using h
private def memAttachOrd (w h base : ℕ) (src : ℕ → ℕ → ℕ) (i j : ℕ) : Gate :=
let v := base+i*memLaneWidth w h+j
if 0 < j ∧ j ≤ h then .pin v (i.testBit (j-1))
else .copy v (src i (sourceBitIndex h j))
private theorem memAttachOrd_poly {w h base idx j : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hi : ComputableTidilyInPolyTime idx e NU)
(hj : ComputableTidilyInPolyTime j e NU)
(hs : ComputableTidilyInPolyTime (fun a : (A×ℕ)×ℕ => src a.1.1 a.1.2 a.2)
(encPair (encPair e NU) NU) NU) :
ComputableTidilyInPolyTime (fun a => memAttachOrd (w a) (h a) (base a) (src a) (idx a) (j a)) e gateEnc := by
have hV := mAdd (mAdd hb (mMul hi (memLaneWidth_poly hw hh))) hj
have hJ0 := unary_beq hj (const 0)
have hS : ComputableTidilyInPolyTime (fun a => sourceBitIndex (h a) (j a)) e NU := by
simpa only [sourceBitIndex,beq_iff_eq] using hJ0.cond (const 0) (mSub hj hh)
have hCopy := gate_copy hV (hs.comp (((id' (encIn:=e)).prod hi).prod hS))
have hBit := binary_testBit (unary_to_binary.comp hi) (mSub hj (const 1))
have hPin := hBit.cond (gate_pin true hV) (gate_pin false hV)
have hWhen := (unary_lt' (const 0) hj).cond (unary_le' hj hh) (const false)
convert hWhen.cond hPin hCopy using 1
funext x
by_cases hz : 0 < j x <;> by_cases hb : j x ≤ h x <;> cases ht : (idx x).testBit (j x-1) <;>
simp [memAttachOrd,hz,hb,ht]
private theorem memAttachRows_poly {w h base : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU)
(hs : ComputableTidilyInPolyTime (fun a : (A×ℕ)×ℕ => src a.1.1 a.1.2 a.2)
(encPair (encPair e NU) NU) NU) :
ComputableTidilyInPolyTime (fun a => attachRows (w a) (h a) (base a) (fun i => src a i.val)) e NG := by
let pr := fst e NU
let pr2 := fst (encPair e NU) NU
have hGate : ComputableTidilyInPolyTime (fun q : (A×ℕ)×ℕ =>
memAttachOrd (w q.1.1) (h q.1.1) (base q.1.1) (src q.1.1) q.1.2 q.2)
(encPair (encPair e NU) NU) gateEnc := by
let a := pr.comp pr2
let ie := encPair (encPair e NU) NU
let q := fst ie NU
let first := (fst ie NU).comp (fst (encPair ie NU) NU)
have hPull := hs.comp (((a.comp first).prod ((snd ie NU).comp (fst (encPair ie NU) NU))).prod
(snd (encPair ie NU) NU))
exact memAttachOrd_poly (hw.comp a) (hh.comp a) (hb.comp a) ((snd e NU).comp pr2)
(snd (encPair e NU) NU) hPull
have hLine := mapWithInput (f:=fun (p : A×ℕ) j =>
memAttachOrd (w p.1) (h p.1) (base p.1) (src p.1) p.2 j)
(range.comp ((memLaneWidth_poly hw hh).comp pr)) hGate
have hRows := flatMapWithInput (f:=fun a i => (List.range (memLaneWidth (w a) (h a))).map
(memAttachOrd (w a) (h a) (base a) (src a) i)) (range.comp hn) hLine
convert hRows using 1
funext a
simp only [attachRows,Function.comp_def,← routeFinRange_val,List.flatMap_map]
apply List.flatMap_congr
intro i hi
apply List.map_congr_left
intro j hj
unfold laneAttachGate memAttachOrd
rw [memInputLane_val _ _ _ _ _ (List.mem_range.mp (by simpa only [routeFinRange_val] using hj))]
private def memOutputEdgeNat (tier : Option ℕ) (w h base i : ℕ) : List Gate :=
lanePair tier w h (memRouteTop w h base+i*memEdgeStride w h)
(memOutputNat w h base (2^h) i) (memOutputNat w h base (2^h) (i+1))
private def outputChecksNat (tier : Option ℕ) (w h base : ℕ) : List Gate :=
laneInit tier w h (memOutputNat w h base (2^h) 0) ++
(List.range (memEdgeCount h)).flatMap (memOutputEdgeNat tier w h base)
private theorem memOutputEdgeNat_eq (tier : Option ℕ) (w h base : ℕ) (i : Fin (memEdgeCount h)) :
memOutputEdgeNat tier w h base i.val =
lanePair tier w h (memEdgeBase w h base i)
(memOutputLane w h base (memEdgeLeft i)) (memOutputLane w h base (memEdgeRight i)) := by
have hl : memOutputNat w h base (2^h) i.val = memOutputLane w h base (memEdgeLeft i) :=
funext (memOutputNat_eq w h base (memEdgeLeft i))
have hr : memOutputNat w h base (2^h) (i.val+1) = memOutputLane w h base (memEdgeRight i) :=
funext (memOutputNat_eq w h base (memEdgeRight i))
simp only [memOutputEdgeNat,memEdgeBase,hl,hr]
private theorem outputChecksNat_eq (tier : Option ℕ) (w h base : ℕ) :
outputChecksNat tier w h base = outputChecks tier w h base := by
have h0 : memOutputNat w h base (2^h) 0 = memOutputLane w h base (memFirstIx h) :=
funext (memOutputNat_eq w h base (memFirstIx h))
unfold outputChecksNat outputChecks
rw [h0, ← routeFinRange_val (memEdgeCount h),List.flatMap_map]
apply congrArg (fun tail => laneInit tier w h (memOutputLane w h base (memFirstIx h)) ++ tail)
apply List.flatMap_congr
intro i _
exact memOutputEdgeNat_eq tier w h base i
private theorem memOutputRowNat_poly {w h base i : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU)
(hi : ComputableTidilyInPolyTime i e NU) :
ComputableTidilyInPolyTime
(fun p : A×ℕ => memOutputNat (w p.1) (h p.1) (base p.1) (2^(h p.1)) (i p.1) p.2)
(encPair e NU) NU := by
let first := fst e NU
exact memOutputNat_poly (hw.comp first) (hh.comp first) (hb.comp first)
(hn.comp first) (hi.comp first) (snd e NU)
private theorem memOutputEdgeNat_poly {w h base code i : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hc : ComputableTidilyInPolyTime code e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU)
(hi : ComputableTidilyInPolyTime i e NU) :
ComputableTidilyInPolyTime
(fun a => memOutputEdgeNat (decodeGroupTier (code a)) (w a) (h a) (base a) (i a)) e NG := by
let row (a : A) (j : ℕ) := memOutputNat (w a) (h a) (base a) (2^(h a)) j
have hl := memOutputRowNat_poly hw hh hb hn hi
have hr := memOutputRowNat_poly hw hh hb hn (mAdd hi (const 1))
exact lanePair_poly (l := fun a => row a (i a)) (r := fun a => row a (i a+1))
hw hh hc (memEdgeBase_poly hw hh hb hn hi) hl hr
set_option maxHeartbeats 1000000 in
private theorem outputChecksNat_poly {w h base code : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hc : ComputableTidilyInPolyTime code e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU) :
ComputableTidilyInPolyTime (fun a => outputChecksNat (decodeGroupTier (code a)) (w a) (h a) (base a)) e NG := by
have h0 := memOutputRowNat_poly hw hh hb hn (const 0)
have hInit := laneInit_poly (row := fun a => memOutputNat (w a) (h a) (base a) (2^(h a)) 0)
hw hh hc h0
have hCount : ComputableTidilyInPolyTime (fun a => memEdgeCount (h a)) e NU :=
mSub hn (const 1)
let first := fst e NU
have hEdge := memOutputEdgeNat_poly (hw.comp first) (hh.comp first) (hb.comp first)
(hc.comp first) (hn.comp first) (snd e NU)
exact listAppend' hInit (flatMapWithInput
(f := fun a i => memOutputEdgeNat (decodeGroupTier (code a)) (w a) (h a) (base a) i)
(range.comp hCount) hEdge)
private theorem memOutputChecks_poly {w h base code : A → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hc : ComputableTidilyInPolyTime code e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU) :
ComputableTidilyInPolyTime (fun a => outputChecks (decodeGroupTier (code a)) (w a) (h a) (base a)) e NG :=
(outputChecksNat_poly hw hh hb hc hn).of_enc_eq (fun a =>
congrArg (encList gateEnc) (outputChecksNat_eq (decodeGroupTier (code a)) (w a) (h a) (base a)).symm)
theorem memSortGates_polytime {w h base code : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e NU) (hh : ComputableTidilyInPolyTime h e NU)
(hb : ComputableTidilyInPolyTime base e NU) (hc : ComputableTidilyInPolyTime code e NU)
(hn : ComputableTidilyInPolyTime (fun a => 2^(h a)) e NU)
(hs : ComputableTidilyInPolyTime (fun a : (A×ℕ)×ℕ => src a.1.1 a.1.2 a.2)
(encPair (encPair e NU) NU) NU) :
ComputableTidilyInPolyTime (fun a => memSortGates (decodeGroupTier (code a))
(w a) (h a) (base a) (fun i => src a i.val)) e NG := by
have hR := boundedRouteGates_poly.comp ((memLaneWidth_poly hw hh).prod (hh.prod (hb.prod hn)))
have hR' : ComputableTidilyInPolyTime (fun a => memRouteGates (w a) (h a) (base a)) e NG := by
convert hR using 1
funext a
simp only [Function.comp_def,boundedRouteGates_eq _ _ _ _ le_rfl]
rfl
exact listAppend' (listAppend' (memAttachRows_poly hw hh hb hn hs) hR')
(memOutputChecks_poly hw hh hb hc hn)
end
end CNFEncComplexity.Robson
/- RobsonTierGeometry -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
/-- The numerical group width can saturate at the number of input lanes.
This avoids writing a unary address-domain size when no snapshots are used. -/
def sorterCappedCap (R w : ℕ) : ℕ := min R (2^w)
def sorterCount (R w : ℕ) : ℕ :=
if R = 0 then 0 else if R ≤ sorterCappedCap R w then 1 else R / sorterCappedCap R w+1
def sorterHeight (R w : ℕ) : ℕ :=
if R ≤ sorterCappedCap R w then slotLevel R else w+2
def sorterSnapshots (R w : ℕ) : ℕ :=
if R ≤ sorterCappedCap R w then 0 else (sorterCount R w+1)*sorterCappedCap R w*(w+1)
def sorterStride (R w : ℕ) : ℕ := memGroupTop w (sorterHeight R w) 0
def sorterStart (R w base : ℕ) : ℕ := base+sorterSnapshots R w
def sorterGroupBase (R w base g : ℕ) := sorterStart R w base + g*sorterStride R w
def sorterTierTop (R w base : ℕ) := sorterStart R w base + sorterCount R w*sorterStride R w
def sorterSnapshotName (R w base boundary addr bit : ℕ) : ℕ :=
base+(boundary*sorterCappedCap R w+addr)*(w+1)+bit
def sorterTierCode (R w tier : ℕ) : ℕ :=
if R ≤ sorterCappedCap R w then tier+1 else 0
theorem sorterCappedCap_small (R w : ℕ) : R ≤ sorterCappedCap R w ↔ R ≤ 2^w := by simp [sorterCappedCap]
theorem sorterCappedCap_split {R w : ℕ} (h : ¬ R ≤ 2^w) : sorterCappedCap R w = 2^w :=
min_eq_right (Nat.lt_of_not_ge h).le
theorem sorterCount_nonzero {R w : ℕ} (h : R ≠ 0) : 1 ≤ sorterCount R w := by
unfold sorterCount
rw [if_neg h]
split
· rfl
· exact Nat.succ_pos _
theorem sorterCount_split {R w : ℕ} (h : ¬ R ≤ 2^w) : sorterCount R w = R/2^w+1 := by
have hN : R ≠ 0 := fun he => h (he.symm ▸ Nat.zero_le _)
simp [sorterCount,hN,sorterCappedCap_small,h,sorterCappedCap_split h]
theorem sorterHeight_small {R w : ℕ} (h : R ≤ 2^w) : sorterHeight R w = slotLevel R := by
simp [sorterHeight,sorterCappedCap_small,h]
theorem sorterHeight_split {R w : ℕ} (h : ¬ R ≤ 2^w) : sorterHeight R w = w+2 := by
simp [sorterHeight,sorterCappedCap_small,h]
theorem sorterWires_bound (R w : ℕ) : 2^sorterHeight R w ≤ 8*R+1 := by
by_cases h : R ≤ 2^w
· rw [sorterHeight_small h]
change slotWidth R ≤ _
by_cases hz : R = 0
· subst R
decide
· exact (slotWidth_le_double (Nat.pos_of_ne_zero hz)).trans (by omega)
· rw [sorterHeight_split h,pow_add]
have hq : 2^w < R := by omega
norm_num
omega
theorem memGroupTop_shift (w h base extra : ℕ) :
memGroupTop w h (base+extra) = base+memGroupTop w h extra := by
simp only [memGroupTop,memRouteTop]
ring
theorem sorterGroupTop_eq (R w base g : ℕ) :
memGroupTop w (sorterHeight R w) (sorterGroupBase R w base g) =
sorterStart R w base +(g+1)*sorterStride R w := by
unfold sorterGroupBase
have h := memGroupTop_shift w (sorterHeight R w)
(sorterStart R w base + g*sorterStride R w) 0
rw [Nat.add_zero] at h
rw [h,Nat.add_mul,Nat.one_mul]
unfold sorterStride
omega
theorem sorterWindowSource_eq (R w tier g z o : ℕ) (source : ℕ → ℕ → ℕ)
(snap : ℕ → ℕ → ℕ → ℕ) :
memoryWindowSource w tier (sorterCappedCap R w) R g z o source snap =
memoryWindowSource w tier (2^w) R g z o source snap := by
by_cases h : R ≤ 2^w
· funext i j
simp [memoryWindowSource,h,sorterCappedCap_small]
· rw [sorterCappedCap_split h]
section Native
variable {A : Type} {e : A ↪ List Bool}
private theorem winAdd {f g : A → ℕ} (x : ComputableTidilyInPolyTime f e encUnary)
(y : ComputableTidilyInPolyTime g e encUnary) :
ComputableTidilyInPolyTime (fun a => f a+g a) e encUnary := unary_add.comp (x.prod y)
private theorem winSub {f g : A → ℕ} (x : ComputableTidilyInPolyTime f e encUnary)
(y : ComputableTidilyInPolyTime g e encUnary) :
ComputableTidilyInPolyTime (fun a => f a-g a) e encUnary := unary_sub.comp (x.prod y)
private theorem winMul {f g : A → ℕ} (x : ComputableTidilyInPolyTime f e encUnary)
(y : ComputableTidilyInPolyTime g e encUnary) :
ComputableTidilyInPolyTime (fun a => f a*g a) e encUnary := unary_mul.comp (x.prod y)
theorem sorterCappedCap_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterCappedCap (R a) (w a)) e encUnary :=
(ComputableInPolyTime.binary_min_unary' hr.computableInPolyTime
(binary_two_pow.comp hw).computableInPolyTime).tidy
theorem sorterCount_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterCount (R a) (w a)) e encUnary := by
have hQ := sorterCappedCap_poly hr hw
have hD := winAdd (unary_div_poly.comp (hr.prod hQ)) (const 1)
have h := (unary_beq hr (const 0)).cond (const 0)
((unary_le' hr hQ).ite' (const 1) hD)
simpa only [sorterCount,beq_iff_eq,decide_eq_true_eq,Function.comp_def] using h
theorem sorterHeight_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterHeight (R a) (w a)) e encUnary := by
have hQ := sorterCappedCap_poly hr hw
have hs := unary_size_poly.comp (winSub hr (const 1))
simpa only [sorterHeight,slotLevel,decide_eq_true_eq,Function.comp_def] using
(unary_le' hr hQ).ite' hs (winAdd hw (const 2))
theorem sorterWires_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => 2^sorterHeight (R a) (w a)) e encUnary :=
unary_pow2_of_bound (sorterHeight_poly hr hw) (winAdd (winMul (const 8) hr) (const 1))
(fun a => sorterWires_bound (R a) (w a))
theorem sorterSnapshots_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterSnapshots (R a) (w a)) e encUnary := by
have hQ := sorterCappedCap_poly hr hw
simpa only [sorterSnapshots,decide_eq_true_eq] using (unary_le' hr hQ).ite' (const 0)
(winMul (winMul (winAdd (sorterCount_poly hr hw) (const 1)) hQ) (winAdd hw (const 1)))
theorem sorterStride_poly {R w : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterStride (R a) (w a)) e encUnary := by
have h := sorterHeight_poly hr hw
have n := sorterWires_poly hr hw
have u := winAdd (const 1) hw
have W := winAdd (winAdd (winAdd (winAdd (const 1) h) hw) u) u
have hB := winMul n W
have hA := winMul (winMul h n) (winAdd (const 1) (winMul (const 2) W))
have hTop := winAdd hB (winAdd hB hA)
have hStride := winAdd (winAdd (winAdd (winMul (const 4) (winAdd h hw)) (const 2)) (winMul (const 4) hw)) (const 2)
have final := winAdd hTop (winMul (winSub n (const 1)) hStride)
simpa only [sorterStride,memGroupTop,memRouteTop,memEdgeCount,memEdgeStride,memLaneWidth,auxCount_exact,
Nat.zero_add] using final
theorem sorterGroupBase_poly {R w base g : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) (hb : ComputableTidilyInPolyTime base e encUnary)
(hg : ComputableTidilyInPolyTime g e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterGroupBase (R a) (w a) (base a) (g a)) e encUnary :=
winAdd (winAdd hb (sorterSnapshots_poly hr hw)) (winMul hg (sorterStride_poly hr hw))
theorem sorterTierTop_poly {R w base : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) (hb : ComputableTidilyInPolyTime base e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterTierTop (R a) (w a) (base a)) e encUnary :=
sorterGroupBase_poly hr hw hb (sorterCount_poly hr hw)
theorem sorterSnapshotName_poly {R w base k addr bit : A → ℕ}
(hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) (hb : ComputableTidilyInPolyTime base e encUnary)
(hk : ComputableTidilyInPolyTime k e encUnary) (ha : ComputableTidilyInPolyTime addr e encUnary)
(hi : ComputableTidilyInPolyTime bit e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterSnapshotName (R a) (w a)
(base a) (k a) (addr a) (bit a)) e encUnary :=
winAdd (winAdd hb (winMul (winAdd (winMul hk (sorterCappedCap_poly hr hw)) ha) (winAdd hw (const 1)))) hi
theorem sorterTierCode_poly {R w tier : A → ℕ} (hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary) (ht : ComputableTidilyInPolyTime tier e encUnary) :
ComputableTidilyInPolyTime (fun a => sorterTierCode (R a) (w a) (tier a)) e encUnary := by
simpa only [sorterTierCode,decide_eq_true_eq] using
(unary_le' hr (sorterCappedCap_poly hr hw)).ite' (winAdd ht (const 1)) (const 0)
end Native
end CNFEncComplexity.Robson
/- RobsonTierBatch -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def tierWindowGates (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (g : ℕ) : List Gate :=
memSortGates (decodeGroupTier (sorterTierCode R w tier)) w (sorterHeight R w)
(sorterGroupBase R w base g)
(fun i => memoryWindowSource w tier (sorterCappedCap R w) R g z o src (sorterSnapshotName R w base) i.val)
def tierBatchGates (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) : List Gate :=
(List.range (sorterCount R w)).flatMap (tierWindowGates R w tier base z o src)
theorem tierSortKind_small {R w tier : ℕ} (h : R ≤ 2^w) :
decodeGroupTier (sorterTierCode R w tier) = some tier := by
simp [sorterTierCode,sorterCappedCap_small,h,decodeGroupTier]
theorem tierSortKind_split {R w tier : ℕ} (h : ¬ R ≤ 2^w) :
decodeGroupTier (sorterTierCode R w tier) = none := by
simp [sorterTierCode,sorterCappedCap_small,h,decodeGroupTier]
theorem tier_small_padding {R w : ℕ} (h : R ≤ 2^w) :
R ≤ 2^sorterHeight R w := by
rw [sorterHeight_small h]
exact le_slotWidth _
theorem tier_split_padding {R w : ℕ} (h : ¬ R ≤ 2^w) :
3*2^w ≤ 2^sorterHeight R w := by
rw [sorterHeight_split h,pow_add]
norm_num
omega
theorem snapshotUsed_bound (R w base b u bit : ℕ)
(hSmall : ¬ R ≤ 2^w) (hb : b ≤ sorterCount R w)
(hu : u < sorterCappedCap R w) (hk : bit ≤ w) :
base ≤ sorterSnapshotName R w base b u bit ∧
sorterSnapshotName R w base b u bit < sorterStart R w base := by
unfold sorterSnapshotName sorterStart sorterSnapshots
rw [if_neg (fun h => hSmall ((sorterCappedCap_small R w).mp h))]
have hm : b*sorterCappedCap R w ≤ sorterCount R w*sorterCappedCap R w :=
Nat.mul_le_mul_right _ hb
have hR : b*sorterCappedCap R w+u+1 ≤ (sorterCount R w+1)*sorterCappedCap R w := by
rw [Nat.add_mul,Nat.one_mul]
omega
have hF := Nat.mul_le_mul_right (w+1) hR
rw [Nat.add_mul,Nat.one_mul] at hF
omega
theorem tierWindowSource_uses {P : ℕ → Prop} (R w tier base z o : ℕ)
(src : ℕ → ℕ → ℕ) (g : ℕ) (hg : g < sorterCount R w) (hz : P z) (ho : P o)
(hData : ∀ i < R, ∀ j < memLaneWidth w 0, P (src i j))
(hOwn : ∀ k, base ≤ k → k < sorterStart R w base → P k) :
∀ i j, j < memLaneWidth w 0 →
P (memoryWindowSource w tier (sorterCappedCap R w) R g z o src (sorterSnapshotName R w base) i j) := by
by_cases hSmall : R ≤ 2^w
· intro i j hj
have h := (sorterCappedCap_small R w).mpr hSmall
rw [memoryWindowSource,if_pos h]
split
· exact hData i ‹_› j hj
· exact hz
· apply memoryWindowSource_uses _ _ _ _ _ _ _ _ _ _ hz ho hData
intro k hk u hu bit hb
have hK : k ≤ sorterCount R w := by
rcases hk with rfl|rfl <;> omega
obtain ⟨h1,h2⟩ := snapshotUsed_bound R w base k u bit hSmall hK hu hb
exact hOwn _ h1 h2
theorem tierBatchGates_names (R w tier base low z o : ℕ) (src : ℕ → ℕ → ℕ)
(_ : low ≤ base) (hz : z < low) (ho : o < low)
(hData : ∀ i < R, ∀ j < memLaneWidth w 0, src i j < low) :
GatesOn (fun k => k < low ∨ (base ≤ k ∧ k < sorterTierTop R w base))
(tierBatchGates R w tier base z o src) := by
intro gate hG k hk
obtain ⟨g,hg,hg'⟩ := List.mem_flatMap.mp hG
have hI := List.mem_range.mp hg
have hStart : base ≤ sorterStart R w base := Nat.le_add_right _ _
have hBase : sorterStart R w base ≤ sorterGroupBase R w base g := Nat.le_add_right _ _
have hTop : memGroupTop w (sorterHeight R w) (sorterGroupBase R w base g) ≤ sorterTierTop R w base := by
rw [sorterGroupTop_eq,sorterTierTop]
exact Nat.add_le_add_left (Nat.mul_le_mul_right _ (by omega)) _
have hTierTop : sorterStart R w base ≤ sorterTierTop R w base := Nat.le_add_right _ _
have hp := memSortGates_uses (decodeGroupTier (sorterTierCode R w tier)) w (sorterHeight R w)
(sorterGroupBase R w base g)
(fun i => memoryWindowSource w tier (sorterCappedCap R w) R g z o src (sorterSnapshotName R w base) i.val)
(fun k => k < low ∨ (base ≤ k ∧ k < sorterTierTop R w base))
(fun i j hj => tierWindowSource_uses (P := fun k => k < low ∨ (base ≤ k ∧ k < sorterTierTop R w base))
R w tier base z o src g hI
(.inl hz) (.inl ho) (fun i hi j hj => .inl (hData i hi j hj))
(fun k hl hr => .inr ⟨hl,hr.trans_le hTierTop⟩) i.val j hj)
(fun k hl hr => .inr ⟨hStart.trans (hBase.trans hl),hr.trans_le hTop⟩)
exact hp gate hg' k hk
theorem tierBatchGates_length (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (hw : 0 < w) :
(tierBatchGates R w tier base z o src).length ≤
1024*sorterCount R w*2^sorterHeight R w*w*w := by
have hH : sorterHeight R w ≤ w+2 := by
by_cases hs : R ≤ 2^w
· rw [sorterHeight_small hs]
apply Nat.le_trans (_ : slotLevel R ≤ w) (by omega)
unfold slotLevel
apply Nat.size_le.mpr
have hh := Nat.two_pow_pos w
omega
· rw [sorterHeight_split hs]
let L := 1024*2^sorterHeight R w*w*w
have hl (g : ℕ) : (tierWindowGates R w tier base z o src g).length ≤ L :=
memSortGates_length_small _ _ _ _ _ hw hH
unfold tierBatchGates
rw [List.length_flatMap]
have hg (l : List ℕ) : (l.map fun g => (tierWindowGates R w tier base z o src g).length).sum ≤
l.length*L := by
induction l with
| nil => simp
| cons g gs ih =>
have h := hl g
simp only [List.map_cons,List.sum_cons,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
have he := hg (List.range (sorterCount R w))
rw [List.length_range] at he
exact he.trans_eq (by unfold L; ring)
theorem memIndexedSnapshots {q : ℕ} {groups : List (List (Option LocalRecord))}
{m : LocalMemory} (start : LocalMemory.Restricted q m) :
OptionSnapshotCertificate q groups m ↔
∃ snaps : Fin (groups.length+1) → LocalMemory,
snaps 0 = m ∧ (∀ i, LocalMemory.Restricted q (snaps i)) ∧
∀ i : Fin groups.length, OptionalCertificate (fun _ => none)
(optionFrame q (snaps i.castSucc) (snaps i.succ) groups[i]) := by
induction groups generalizing m with
| nil =>
exact ⟨fun _ => ⟨fun _ => m,rfl,fun _ => start,fun i => Fin.elim0 i⟩,fun _ => .nil _⟩
| cons g gs ih =>
constructor
· intro h
cases h with
| cons hNext hG hTail =>
obtain ⟨snaps,h0,hOk,hcert⟩ := (ih hNext).1 hTail
let frames : Fin ((g::gs).length+1) → LocalMemory := Fin.cons m snaps
refine ⟨frames,Fin.cons_zero ..,?_,?_⟩
· intro i
refine Fin.cases ?_ (fun j => ?_) i
· change LocalMemory.Restricted q m
exact start
· exact hOk j
· intro i
refine Fin.cases ?_ (fun j => ?_) i
· change OptionalCertificate _ (optionFrame q (frames 0)
(frames (Fin.succ (0 : Fin (gs.length+1)))) g)
dsimp only [frames]
rw [Fin.cons_zero,Fin.cons_succ,h0]
exact hG
· change OptionalCertificate _ (optionFrame q (frames (Fin.succ j.castSucc))
(frames (Fin.succ j.succ)) gs[j])
dsimp only [frames]
rw [Fin.cons_succ,Fin.cons_succ]
exact hcert j
· rintro ⟨snaps,hS,hB,hA⟩
let next := snaps (Fin.succ (0 : Fin (gs.length+1)))
have hN : LocalMemory.Restricted q next := hB _
refine .cons hN ?_ ((ih hN).2 ⟨Fin.tail snaps,rfl,fun i => hB i.succ,fun i => hA i.succ⟩)
have h := hA 0
change OptionalCertificate _ (optionFrame q (snaps 0) next g) at h
rwa [hS] at h
end CNFEncComplexity.Robson
/- RobsonTierBatchBudget -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem sorterGroupWires_budget (R w : ℕ) : sorterCount R w * 2^sorterHeight R w ≤ 8*R := by
by_cases h0 : R = 0
· simp [sorterCount,h0]
by_cases hs : R ≤ 2^w
· have hL := slotWidth_le_double (Nat.pos_of_ne_zero h0)
rw [sorterHeight_small hs]
simp only [sorterCount,if_neg h0,if_pos ((sorterCappedCap_small R w).mpr hs),Nat.one_mul]
exact hL.trans (by omega)
· rw [sorterCount_split hs,sorterHeight_split hs,pow_add]
have hD : R/2^w * 2^w ≤ R := Nat.div_mul_le_self _ _
have hQ : 2^w ≤ R := Nat.le_of_lt (Nat.lt_of_not_ge hs)
calc
(R / 2^w + 1) * (2^w * 2^2) = 4*(R/2^w * 2^w + 2^w) := by ring
_ ≤ 8*R := by omega
theorem tierBatchGates_budget (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (hw : 0 < w) :
(tierBatchGates R w tier base z o src).length ≤ 8192*R*w*w := by
have h := tierBatchGates_length R w tier base z o src hw
have r := Nat.mul_le_mul_left 1024 (sorterGroupWires_budget R w)
have s := Nat.mul_le_mul_right w (Nat.mul_le_mul_right w r)
calc
_ ≤ 1024*(sorterCount R w * 2^sorterHeight R w)*w*w := by
simpa only [Nat.mul_assoc] using h
_ ≤ 1024*(8*R)*w*w := s
_ = 8192*R*w*w := by ring
end CNFEncComplexity.Robson
/- RobsonTierBatchCorrect -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def sorterTierCertificate (R w tier : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment) : Prop :=
if R ≤ 2^w then OptionalCertificate (groupInitial (some tier)) (rawMemoryRows a w R src)
else OptionSnapshotCertificate (2^w) (fixedGroups (2^w) (sorterCount R w) (rawMemoryRows a w R src))
(groupInitial (some tier))
private theorem tierWindow_small_iff (R w tier base z o g : ℕ) (src : ℕ → ℕ → ℕ)
(a : Assignment) (hz : a z = false) (hs : R ≤ 2^w) :
OptionalCertificate (groupInitial (decodeGroupTier (sorterTierCode R w tier)))
(untaggedRows w (sorterHeight R w)
(fun i => memoryWindowSource w tier (sorterCappedCap R w) R g z o src (sorterSnapshotName R w base) i.val) a) ↔
OptionalCertificate (groupInitial (some tier)) (rawMemoryRows a w R src) := by
rw [tierSortKind_small hs,sorterWindowSource_eq]
exact memoryWindow_single_certificate _ _ _ _ _ _ _ _ _ _ hz hs (tier_small_padding hs)
private theorem tierWindow_split_iff (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ)
(a : Assignment) (hz : a z = false) (ho : a o = true) (hs : ¬ R ≤ 2^w)
(g : Fin (sorterCount R w)) :
OptionalCertificate (groupInitial (decodeGroupTier (sorterTierCode R w tier)))
(untaggedRows w (sorterHeight R w)
(fun i => memoryWindowSource w tier (sorterCappedCap R w) R g.val z o src (sorterSnapshotName R w base) i.val) a) ↔
OptionalCertificate (fun _ => none) (optionFrame (2^w)
(snapshotState a w (2^w) tier z o (sorterSnapshotName R w base) g.val)
(snapshotState a w (2^w) tier z o (sorterSnapshotName R w base) (g.val+1))
((fixedGroups (2^w) (sorterCount R w) (rawMemoryRows a w R src))[g.val]'(by simpa using g.isLt))) := by
rw [tierSortKind_split hs,sorterWindowSource_eq]
exact memoryWindow_split_certificate _ _ _ _ _ _ _ _ _ _ _ hz ho hs (tier_split_padding hs) g.isLt
theorem sorterRawRows_congr (R w : ℕ) (src : ℕ → ℕ → ℕ) (a b : Assignment)
(h : ∀ i < R, ∀ j < memLaneWidth w 0, a (src i j) = b (src i j)) :
rawMemoryRows a w R src = rawMemoryRows b w R src := by
unfold rawMemoryRows
apply List.map_congr_left
intro i hi
exact congrArg Prod.fst (laneTag_congr (h i (List.mem_range.mp hi)))
private theorem tierBatchWindow_mem (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ)
(i : Fin (sorterCount R w)) (g : Gate) (hg : g ∈ tierWindowGates R w tier base z o src i.val) :
g ∈ tierBatchGates R w tier base z o src :=
List.mem_flatMap.mpr ⟨i.val,List.mem_range.mpr i.isLt,hg⟩
theorem tierBatchGates_sound (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment)
(hz : a z = false) (ho : a o = true)
(hInit : LocalMemory.Restricted (2^w) (groupInitial (some tier)))
(hSat : ∀ g ∈ tierBatchGates R w tier base z o src, g.Holds a) :
sorterTierCertificate R w tier src a := by
have groupCert (i : Fin (sorterCount R w)) :
OptionalCertificate (groupInitial (decodeGroupTier (sorterTierCode R w tier)))
(untaggedRows w (sorterHeight R w)
(fun j => memoryWindowSource w tier (sorterCappedCap R w) R i.val z o src (sorterSnapshotName R w base) j.val) a) :=
memSortGates_sound _ _ _ _ _ _ (fun g hg => hSat g (tierBatchWindow_mem R w tier base z o src i g hg))
by_cases hs : R ≤ 2^w
· rw [sorterTierCertificate,if_pos hs]
by_cases h0 : R = 0
· subst R
change OptionalCertificate _ []
exact (optionalCertificate_iff _ _).2 ⟨_,.nil _⟩
· have hR := sorterCount_nonzero (w := w) h0
exact (tierWindow_small_iff R w tier base z o 0 src a hz hs).1 (groupCert ⟨0, hR⟩)
· rw [sorterTierCertificate,if_neg hs]
let groups := fixedGroups (2^w) (sorterCount R w) (rawMemoryRows a w R src)
have hL : groups.length = sorterCount R w := by simp [groups]
let snap (i : Fin (sorterCount R w+1)) :=
snapshotState a w (2^w) tier z o (sorterSnapshotName R w base) i.val
have hS : snap 0 = groupInitial (some tier) :=
snapshotState_initial _ _ _ _ _ _ _ hz ho hInit
have hW (i : Fin (sorterCount R w)) :
OptionalCertificate (fun _ => none) (optionFrame (2^w) (snap i.castSucc) (snap i.succ)
(groups[i.val]'(by rw [hL]; exact i.isLt))) :=
(tierWindow_split_iff R w tier base z o src a hz ho hs i).1 (groupCert i)
apply (memIndexedSnapshots hInit).2
refine ⟨fun i => snap (i.cast (by rw [hL])),hS,fun i => snapshotState_restricted a w (2^w) tier z o (sorterSnapshotName R w base) _,?_⟩
intro i
exact hW (i.cast hL)
private theorem sorterSnapshot_assign (R w tier base z o : ℕ) (a : Assignment)
(hs : ¬ R ≤ 2^w) (hz : a z = false) (ho : a o = true) (hzBase : z < base) (hoBase : o < base)
(snap : Fin (sorterCount R w+1) → LocalMemory)
(hS : snap 0 = groupInitial (some tier))
(hRest : ∀ i, LocalMemory.Restricted (2^w) (snap i))
(hFit : ∀ i, SnapshotValuesFit (2^w) (snap i)) :
∃ b : Assignment,
(∀ k, k < base ∨ sorterStart R w base ≤ k → b k = a k) ∧
(∀ i : Fin (sorterCount R w+1),
snapshotState b w (2^w) tier z o (sorterSnapshotName R w base) i.val = snap i) := by
classical
let D := (Fin (sorterCount R w+1) × Fin (2^w)) × Fin (w+1)
let key (i : D) := sorterSnapshotName R w base i.1.1.val i.1.2.val i.2.val
let value (i : D) := snapshotValueBit (snap i.1.1 i.1.2.val) i.2.val
have hKey : Function.Injective key := by
intro u v he
let e : D ≃ Fin (((sorterCount R w+1)*2^w)*(w+1)) :=
(finProdFinEquiv.prodCongr (Equiv.refl (Fin (w+1)))).trans finProdFinEquiv
apply e.injective
apply Fin.ext
change (finProdFinEquiv (finProdFinEquiv u.1,u.2)).val =
(finProdFinEquiv (finProdFinEquiv v.1,v.2)).val
simp only [finProdFinEquiv_apply_val]
simp only [key,sorterSnapshotName,sorterCappedCap_split hs] at he
ring_nf at he ⊢
omega
let b := Function.extend key value a
have outside (k : ℕ) (hk : k < base ∨ sorterStart R w base ≤ k) : b k = a k := by
apply Function.extend_apply'
rintro ⟨i,hi⟩
have hIn := snapshotUsed_bound R w base i.1.1.val i.1.2.val i.2.val hs
(Nat.le_of_lt_succ i.1.1.isLt)
(by rw [sorterCappedCap_split hs]; exact i.1.2.isLt)
(Nat.le_of_lt_succ i.2.isLt)
change sorterSnapshotName R w base i.1.1.val i.1.2.val i.2.val = k at hi
omega
refine ⟨b,outside,?_⟩
intro i
by_cases hZero : i = 0
· subst i
rw [hS]
exact snapshotState_initial _ _ _ _ _ _ _ ((outside z (.inl hzBase)).trans hz)
((outside o (.inl hoBase)).trans ho) (hS ▸ hRest 0)
· apply snapshotState_decode _ _ _ _ _ _ _ _ (fun he => hZero (Fin.ext he)) (hRest i) (hFit i)
intro addr ha j hj
exact congrFun (Function.extend_comp hKey value a) ((i,⟨addr,ha⟩),⟨j,Nat.lt_succ_of_le hj⟩)
private theorem tierBatchGates_finish (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ)
(a aS : Assignment)
(hz : z < base) (ho : o < base)
(hData : ∀ i < R, ∀ j < memLaneWidth w 0, src i j < base)
(hSnap : ∀ k, k < base ∨ sorterStart R w base ≤ k → aS k = a k)
(hCert : ∀ i : Fin (sorterCount R w),
OptionalCertificate (groupInitial (decodeGroupTier (sorterTierCode R w tier)))
(untaggedRows w (sorterHeight R w)
(fun j => memoryWindowSource w tier (sorterCappedCap R w) R i.val z o src (sorterSnapshotName R w base) j.val) aS)) :
∃ b : Assignment,
(∀ k, k < base ∨ sorterTierTop R w base ≤ k → b k = a k) ∧
(∀ g ∈ tierBatchGates R w tier base z o src, g.Holds b) := by
let start := sorterStart R w base
let width := sorterStride R w
let count := sorterCount R w
let parts (i : Fin count) := tierWindowGates R w tier base z o src i.val
have hB : base ≤ start := Nat.le_add_right _ _
have hSrc (i : Fin count) (j k : ℕ) (hk : k < memLaneWidth w 0) :
memoryWindowSource w tier (sorterCappedCap R w) R i.val z o src
(sorterSnapshotName R w base) j k < start := by
apply tierWindowSource_uses (P := fun x => x < start) R w tier base z o src i.val i.isLt
(hz.trans_le hB) (ho.trans_le hB) (fun p hp q hq => (hData p hp q hq).trans_le hB)
(fun _ _ hr => hr) j k hk
have hNames (i : Fin count) : GatesOn
(fun k => k < start ∨ (start+i.val*width ≤ k ∧ k < start+(i.val+1)*width)) (parts i) := by
have ht : start ≤ sorterGroupBase R w base i := Nat.le_add_right _ _
have hh := memSortGates_names (decodeGroupTier (sorterTierCode R w tier)) w (sorterHeight R w)
(sorterGroupBase R w base i.val) start
(fun j => memoryWindowSource w tier (sorterCappedCap R w) R i.val z o src (sorterSnapshotName R w base) j.val)
ht (fun j k hk => hSrc i j.val k hk)
rw [sorterGroupTop_eq] at hh
exact hh
have hParts (i : Fin count) : ∃ b : Assignment,
(∀ k, (k < start+i.val*width ∨ start+(i.val+1)*width ≤ k) → b k = aS k) ∧
(∀ g ∈ parts i, g.Holds b) := by
have ht : start ≤ sorterGroupBase R w base i := Nat.le_add_right _ _
have hh := memSortGates_complete (decodeGroupTier (sorterTierCode R w tier)) w (sorterHeight R w)
(sorterGroupBase R w base i.val)
(fun j => memoryWindowSource w tier (sorterCappedCap R w) R i.val z o src (sorterSnapshotName R w base) j.val)
aS (fun j k hk => (hSrc i j.val k hk).trans_le ht) (hCert i)
rw [sorterGroupTop_eq] at hh
exact hh
obtain ⟨b,hAg,hSat⟩ := memIndependentGateIntervals parts aS hNames hParts
have hTop : start ≤ sorterTierTop R w base := Nat.le_add_right _ _
refine ⟨b,fun k hk => ?_,fun g hg => ?_⟩
· rcases hk with hk|hk
· exact (hAg k (.inl (hk.trans_le hB))).trans (hSnap k (.inl hk))
· exact (hAg k (.inr hk)).trans (hSnap k (.inr (hTop.trans hk)))
· obtain ⟨i,hi,hi'⟩ := List.mem_flatMap.mp hg
exact hSat ⟨i,List.mem_range.mp hi⟩ g hi'
theorem tierBatchGates_complete (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment)
(hzBase : z < base) (hoBase : o < base)
(hData : ∀ i < R, ∀ j < memLaneWidth w 0, src i j < base)
(hz : a z = false) (ho : a o = true)
(hInit : LocalMemory.Restricted (2^w) (groupInitial (some tier)))
(hCert : sorterTierCertificate R w tier src a) :
∃ b : Assignment,
(∀ k, k < base ∨ sorterTierTop R w base ≤ k → b k = a k) ∧
(∀ g ∈ tierBatchGates R w tier base z o src, g.Holds b) := by
by_cases hs : R ≤ 2^w
· rw [sorterTierCertificate,if_pos hs] at hCert
apply tierBatchGates_finish R w tier base z o src a a hzBase hoBase hData (fun _ _ => rfl)
intro i
exact (tierWindow_small_iff R w tier base z o i.val src a hz hs).2 hCert
· rw [sorterTierCertificate,if_neg hs] at hCert
let count := sorterCount R w
let groups := fixedGroups (2^w) count (rawMemoryRows a w R src)
have hL : groups.length = count := by simp [groups]
obtain ⟨s,hS,hRest,hGroups⟩ := (memIndexedSnapshots hInit).1 hCert
let snap (i : Fin (count+1)) : LocalMemory := s (i.cast (by rw [hL]))
have h0 : snap 0 = groupInitial (some tier) := hS
have hR (i : Fin (count+1)) : LocalMemory.Restricted (2^w) (snap i) := hRest _
have hG (i : Fin count) : OptionalCertificate (fun _ => none)
(optionFrame (2^w) (snap i.castSucc) (snap i.succ) (groups[i.val]'(by rw [hL]; exact i.isLt))) :=
hGroups (i.cast hL.symm)
have hFit : ∀ i, SnapshotValuesFit (2^w) (snap i) :=
snapshotIndexed_fits snap (h0.symm ▸ snapshot_initial_fit w tier) hR hG
obtain ⟨aS,hSnap,hDecoded⟩ := sorterSnapshot_assign R w tier base z o a hs hz ho hzBase hoBase snap h0 hR hFit
have hRows : rawMemoryRows aS w R src = rawMemoryRows a w R src :=
sorterRawRows_congr R w src aS a (fun i hi j hj => hSnap _ (.inl (hData i hi j hj)))
have hzS : aS z = false := (hSnap z (.inl hzBase)).trans hz
have hoS : aS o = true := (hSnap o (.inl hoBase)).trans ho
apply tierBatchGates_finish R w tier base z o src a aS hzBase hoBase hData hSnap
intro i
apply (tierWindow_split_iff R w tier base z o src aS hzS hoS hs i).2
have hLeft := hDecoded i.castSucc
have hRight := hDecoded i.succ
simp only [Fin.val_castSucc,Fin.val_succ] at hLeft hRight
rw [hLeft,hRight,hRows]
exact hG i
theorem tierBatchGates_exact (R w tier base z o : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment)
(hzBase : z < base) (hoBase : o < base)
(hData : ∀ i < R, ∀ j < memLaneWidth w 0, src i j < base)
(hz : a z = false) (ho : a o = true)
(hInit : LocalMemory.Restricted (2^w) (groupInitial (some tier))) :
(∃ b : Assignment,
(∀ k, k < base ∨ sorterTierTop R w base ≤ k → b k = a k) ∧
(∀ g ∈ tierBatchGates R w tier base z o src, g.Holds b)) ↔
sorterTierCertificate R w tier src a := by
constructor
· rintro ⟨b,hAg,hSat⟩
have hzB : b z = false := (hAg z (.inl hzBase)).trans hz
have hoB : b o = true := (hAg o (.inl hoBase)).trans ho
have h := tierBatchGates_sound R w tier base z o src b hzB hoB hInit hSat
unfold sorterTierCertificate at h ⊢
rwa [sorterRawRows_congr R w src b a (fun i hi j hj => hAg _ (.inl (hData i hi j hj)))] at h
· exact tierBatchGates_complete R w tier base z o src a hzBase hoBase hData hz ho hInit
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).