Certificates for observed RAM memory
DefinitionCNFEncComplexity_RobsonMemoryCertificatescomplexity-theorysatisfiability
List-level soundness and completeness for RAM memory certificates. Includes injective trie labels, tiered updates, boundary snapshots, and permutation routing.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives
set_option maxHeartbeats 4000000
set_option linter.all false
/- memory certificates -/
namespace CNFEncComplexity.Robson
def atAddress (a : ℕ) (es : List MemoryAccess) : List MemoryAccess :=
es.filter (fun e => decide (e.address = a))
/-- A permutation preserving the order of every address's accesses. An address sort using
the original positions as secondary keys has precisely this property. -/
def AddressStable (es fs : List MemoryAccess) : Prop :=
∀ a, atAddress a es = atAddress a fs
def cellReplay : ℕ → List MemoryAccess → ℕ
| v, [] => v
| _, e :: es => cellReplay e.value es
def cellValid : ℕ → List MemoryAccess → Prop
| _, [] => True
| v, e :: es => (e.writes = true ∨ v = e.value) ∧ cellValid e.value es
theorem replay_apply (current : Memory) (trace : List MemoryAccess) (a : ℕ) :
replay current trace a = cellReplay (current a) (atAddress a trace) := by
induction trace generalizing current with
| nil => rfl
| cons e es ih =>
by_cases h : e.address = a
· simp [replay, atAddress, h, ih, cellReplay]
· have hh : a ≠ e.address := Ne.symm h
simp [replay, atAddress, h, ih, Function.update_of_ne hh]
theorem valid_iff_cells (current : Memory) (trace : List MemoryAccess) :
memoryValid current trace ↔ ∀ a, cellValid (current a) (atAddress a trace) := by
induction trace generalizing current with
| nil => simp [memoryValid, atAddress, cellValid]
| cons e es ih =>
simp only [memoryValid, ih]
constructor
· rintro ⟨he, hs⟩ a
by_cases h : e.address = a
· have ha := hs a
simp [Function.update, h] at ha
simpa [atAddress, cellValid, h] using And.intro (h ▸ he) ha
· simpa [atAddress, h, Function.update_of_ne (Ne.symm h)] using hs a
· intro hall
have hfirst : (e.writes = true ∨ current e.address = e.value) ∧
cellValid e.value (atAddress e.address es) := by
simpa [atAddress, cellValid] using hall e.address
refine ⟨hfirst.1, fun a => ?_⟩
by_cases h : e.address = a
· simpa [h] using hfirst.2
· simpa [atAddress, h, Function.update_of_ne (Ne.symm h)] using hall a
theorem AddressStable.valid_iff {trace sorted : List MemoryAccess}
(h : AddressStable trace sorted) (current : Memory) :
memoryValid current trace ↔ memoryValid current sorted := by
simp only [valid_iff_cells, h _]
theorem AddressStable.replay_eq {trace sorted : List MemoryAccess}
(h : AddressStable trace sorted) (current : Memory) :
replay current trace = replay current sorted := by
funext a
simp only [replay_apply, h a]
/-- A sorted trace can be checked using only each record, its immediate predecessor,
and the initial values when beginning an address block. -/
def adjacentValid (current : Memory) (trace : List MemoryAccess) : Prop :=
(trace.head?.elim True fun e => e.writes = true ∨ current e.address = e.value) ∧
trace.IsChain (fun e f =>
f.writes = true ∨ (if e.address = f.address then e.value else current f.address) = f.value)
theorem adjacentValid_iff (current : Memory) (trace : List MemoryAccess)
(ordered : trace.Pairwise (fun e f => e.address ≤ f.address)) :
adjacentValid current trace ↔ memoryValid current trace := by
induction trace generalizing current with
| nil => simp [adjacentValid, memoryValid]
| cons e es ih =>
obtain ⟨horder, hs⟩ := List.pairwise_cons.1 ordered
cases es with
| nil => simp [adjacentValid, memoryValid]
| cons f fs =>
simp only [adjacentValid, List.head?_cons, Option.elim, List.isChain_cons_cons,
memoryValid]
have hs' := ih (Function.update current e.address e.value) hs
have hprev : (if e.address = f.address then e.value else current f.address) =
Function.update current e.address e.value f.address := by
by_cases h : e.address = f.address <;> simp [h, Function.update, eq_comm]
have hchain (a b : MemoryAccess) (hf : f.address ≤ a.address) (hb : a.address ≤ b.address) :
(if a.address = b.address then a.value else current b.address) =
(if a.address = b.address then a.value
else Function.update current e.address e.value b.address) := by
by_cases heq : a.address = b.address
· simp [heq]
· have h₁ : e.address ≤ f.address := horder f (by simp)
have h₂ : b.address ≠ e.address := by omega
simp [heq, Function.update_of_ne h₂]
have hc :
(f :: fs).IsChain (fun a b => b.writes = true ∨
(if a.address = b.address then a.value else current b.address) = b.value) ↔
(f :: fs).IsChain (fun a b => b.writes = true ∨
(if a.address = b.address then a.value
else Function.update current e.address e.value b.address) = b.value) := by
have hrel (a b : MemoryAccess) (ha : a ∈ f :: fs) (hh : a.address ≤ b.address) :
(b.writes = true ∨ (if a.address = b.address then a.value else current b.address) = b.value) ↔
(b.writes = true ∨ (if a.address = b.address then a.value
else Function.update current e.address e.value b.address) = b.value) := by
have hfa : f.address ≤ a.address := by
rcases List.mem_cons.1 ha with rfl | ha
· exact Nat.le_refl _
· exact (List.pairwise_cons.1 hs).1 _ ha
rw [hchain a b hfa hh]
have pchain := hs.isChain
simp only [List.isChain_iff_getElem] at pchain ⊢
refine forall_congr' (fun i => forall_congr' (fun hi => ?_))
exact hrel _ _ (List.getElem_mem (by omega)) (pchain i hi)
have heq : memoryValid (Function.update current e.address e.value) (f :: fs) ↔
(f.writes = true ∨ (if e.address = f.address then e.value else current f.address) = f.value) ∧
(f :: fs).IsChain (fun a b => b.writes = true ∨
(if a.address = b.address then a.value else current b.address) = b.value) := by
rw [← hs', adjacentValid]
simp only [List.head?_cons, Option.elim, ← hprev, ← hc]
simp only [memoryValid] at heq
rw [heq]
theorem ordered_memory_certificate (current : Memory) (trace sorted : List MemoryAccess)
(stable : AddressStable trace sorted)
(ordered : sorted.Pairwise (fun e f => e.address ≤ f.address)) :
memoryValid current trace ↔ adjacentValid current sorted :=
(stable.valid_iff current).trans (adjacentValid_iff _ _ ordered).symm
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
def addressLE (a b : MemoryAccess) : Bool := decide (a.address ≤ b.address)
private theorem addressLE_trans (a b c : MemoryAccess) :
addressLE a b → addressLE b c → addressLE a c := by
simpa [addressLE] using (Nat.le_trans : a.address ≤ b.address → b.address ≤ c.address →
a.address ≤ c.address)
private theorem addressLE_total (a b : MemoryAccess) : (addressLE a b || addressLE b a) = true := by
simpa [addressLE] using Nat.le_total a.address b.address
def sortByAddress (trace : List MemoryAccess) : List MemoryAccess := trace.mergeSort addressLE
theorem sortByAddress_ordered (trace : List MemoryAccess) :
(sortByAddress trace).Pairwise (fun e f => e.address ≤ f.address) := by
simpa [sortByAddress, addressLE] using
List.pairwise_mergeSort addressLE_trans addressLE_total trace
theorem sortByAddress_stable (trace : List MemoryAccess) :
AddressStable trace (sortByAddress trace) := by
intro a
have hp : (atAddress a trace).Pairwise (fun e f => addressLE e f) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj _
have h₁ := List.mem_filter.1 (List.getElem_mem hi)
have h₂ := List.mem_filter.1 (List.getElem_mem hj)
simp only [decide_eq_true_eq] at h₁ h₂
simp [addressLE, h₁.2, h₂.2]
have hsub : List.Sublist (atAddress a trace) (sortByAddress trace) :=
List.sublist_mergeSort addressLE_trans addressLE_total hp
(List.filter_sublist (p := fun e : MemoryAccess => decide (e.address = a)))
have hsub' : List.Sublist (atAddress a trace) (atAddress a (sortByAddress trace)) := by
have hh := hsub.filter (fun e => decide (e.address = a))
simpa [atAddress, List.filter_filter] using hh
apply hsub'.eq_of_length
exact ((List.mergeSort_perm trace addressLE).filter (fun e => decide (e.address = a))).symm.length_eq
/-- Address first, with the chronological position to break ties. -/
def taggedLE (a b : MemoryAccess × ℕ) : Prop :=
a.1.address < b.1.address ∨ (a.1.address = b.1.address ∧ a.2 ≤ b.2)
theorem taggedLE_address {a b : MemoryAccess × ℕ} (h : taggedLE a b) :
a.1.address ≤ b.1.address := by
rcases h with h | ⟨h, _⟩ <;> omega
theorem taggedLE_time {a b : MemoryAccess × ℕ}
(haddr : a.1.address = b.1.address) (h : taggedLE a b) : a.2 ≤ b.2 := by
rcases h with h | ⟨_, h⟩ <;> omega
theorem taggedLE_trans (a b c : MemoryAccess × ℕ) :
taggedLE a b → taggedLE b c → taggedLE a c := by
unfold taggedLE
rintro (h | ⟨h, t⟩) (h' | ⟨h', t'⟩) <;> omega
theorem taggedLE_total (a b : MemoryAccess × ℕ) : taggedLE a b ∨ taggedLE b a := by
unfold taggedLE
omega
theorem tag_ordered (trace : List MemoryAccess) :
trace.zipIdx.Pairwise (fun a b => a.2 ≤ b.2) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj hij
simpa [List.getElem_zipIdx] using hij.le
/-- A sorted permutation of the records tagged by their chronological positions preserves
the order at every address. This is the witness format suited to a permutation network. -/
theorem tagged_sort_stable {trace : List MemoryAccess} {sorted : List (MemoryAccess × ℕ)}
(hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise taggedLE) :
AddressStable trace (sorted.map Prod.fst) := by
intro addr
let filterKey (a : MemoryAccess × ℕ) : Bool := decide (a.1.address = addr)
have htime₁ : (trace.zipIdx.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) :=
(tag_ordered trace).filter filterKey
have htime₂ : (sorted.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj hij
let a := (sorted.filter filterKey)[i]
let b := (sorted.filter filterKey)[j]
have ha : a ∈ sorted.filter filterKey := List.getElem_mem hi
have hb : b ∈ sorted.filter filterKey := List.getElem_mem hj
have ht : taggedLE a b :=
List.pairwise_iff_getElem.1 (horder.filter filterKey) i j hi hj hij
have heq : a.1.address = b.1.address := by
have hx := (List.mem_filter.1 ha).2
have hy := (List.mem_filter.1 hb).2
simp only [filterKey, decide_eq_true_eq] at hx hy
exact hx.trans hy.symm
exact taggedLE_time heq ht
have hlex :
trace.zipIdx.filter filterKey = sorted.filter filterKey := by
apply List.Perm.eq_of_pairwise (le := fun a b : MemoryAccess × ℕ => decide (a.2 ≤ b.2))
· intro a b ha hb hle hge
have hp₁ : a ∈ trace.zipIdx := (List.mem_filter.1 ha).1
have hp₂ : b ∈ trace.zipIdx := hperm.mem_iff.1 (List.mem_filter.1 hb).1
have heq : a.2 = b.2 := Nat.le_antisymm (of_decide_eq_true hle) (of_decide_eq_true hge)
rcases a with ⟨a,i⟩
rcases b with ⟨b,j⟩
change i = j at heq
subst j
obtain ⟨_, _, hia⟩ := List.mem_zipIdx hp₁
obtain ⟨_, _, hjb⟩ := List.mem_zipIdx hp₂
rw [hia, hjb]
· simpa using htime₁
· simpa using htime₂
· exact (hperm.filter filterKey).symm
have hh := congrArg (List.map Prod.fst) hlex
change trace.filter (fun e => decide (e.address = addr)) =
(sorted.map Prod.fst).filter (fun e => decide (e.address = addr))
calc
_ = (trace.zipIdx.map Prod.fst).filter (fun e => decide (e.address = addr)) := by
rw [List.zipIdx_map_fst]
_ = _ := by simpa only [List.filter_map, Function.comp_def, filterKey] using hh
theorem tagged_ordered_memory_certificate (current : Memory) (trace : List MemoryAccess)
(sorted : List (MemoryAccess × ℕ))
(hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise taggedLE) :
memoryValid current trace ↔ adjacentValid current (sorted.map Prod.fst) :=
ordered_memory_certificate current trace (sorted.map Prod.fst) (tagged_sort_stable hperm horder)
(List.pairwise_map.mpr (horder.imp (fun h => taggedLE_address h)))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- A checked store record is a transition between optional values at one address.
A read retains a live value. Cancellation makes the address absent in this tier,
and a store creates a single live value in its new tier. Snapshots use the same
record format, with absent boundary entries represented by absent endpoints. -/
structure StoreRecord (Addr Val : Type) where
addr : Addr
before : Option Val
after : Option Val
deriving DecidableEq
namespace StoreRecord
variable {Addr Val : Type} [DecidableEq Addr]
/-- A checked record list describes a memory transformer with exact endpoint states. -/
inductive Runs : List (StoreRecord Addr Val) → (Addr → Option Val) → (Addr → Option Val) → Prop where
| nil (mem : Addr → Option Val) : Runs [] mem mem
| cons {r : StoreRecord Addr Val} {rs : List (StoreRecord Addr Val)}
{mem finish : Addr → Option Val} :
mem r.addr = r.before →
Runs rs (Function.update mem r.addr r.after) finish →
Runs (r :: rs) mem finish
theorem runs_append {A B : List (StoreRecord Addr Val)}
{m n : Addr → Option Val} :
Runs (A ++ B) m n ↔ ∃ k, Runs A m k ∧ Runs B k n := by
induction A generalizing m with
| nil =>
simp only [List.nil_append]
constructor
· intro h
exact ⟨m,.nil _,h⟩
· rintro ⟨k,h,hr⟩
cases h
exact hr
| cons r rs ih =>
constructor
· intro h
cases h with
| cons hread hrest =>
obtain ⟨k,h₁,h₂⟩ := ih.mp hrest
exact ⟨k,.cons hread h₁,h₂⟩
· rintro ⟨k,h₁,h₂⟩
cases h₁ with
| cons hread hrest =>
exact .cons hread (ih.mpr ⟨k,hrest,h₂⟩)
theorem run_swap {r s : StoreRecord Addr Val} {L : List (StoreRecord Addr Val)}
{m n : Addr → Option Val} (hd : r.addr ≠ s.addr) :
Runs (r::s::L) m n ↔ Runs (s::r::L) m n := by
have hComm : (Function.update (Function.update m r.addr r.after) s.addr s.after) =
Function.update (Function.update m s.addr s.after) r.addr r.after := by
funext a
by_cases ha : a = r.addr
· subst a
simp [Function.update_of_ne hd]
· by_cases hb : a = s.addr
· subst a
simp [Function.update_of_ne hd.symm]
· simp [Function.update_of_ne ha, Function.update_of_ne hb]
constructor <;> intro h
· cases h with
| cons hr hs =>
cases hs with
| cons hs' hL =>
have hsb : m s.addr = s.before := by
simpa only [Function.update_of_ne hd.symm] using hs'
have hrb : (Function.update m s.addr s.after) r.addr = r.before := by
simpa only [Function.update_of_ne hd] using hr
exact .cons hsb (.cons hrb (hComm ▸ hL))
· cases h with
| cons hs hr =>
cases hr with
| cons hr' hL =>
have hrb : m r.addr = r.before := by
simpa only [Function.update_of_ne hd] using hr'
have hsb : (Function.update m r.addr r.after) s.addr = s.before := by
simpa only [Function.update_of_ne hd.symm] using hs
exact .cons hrb (.cons hsb (hComm.symm ▸ hL))
/-- The record order that matters for a memory trace is just the separate order
of records at each address. -/
def At (a : Addr) : List (StoreRecord Addr Val) → List (StoreRecord Addr Val) :=
List.filter (fun r => r.addr == a)
/-- A per-address trace is valid if it forms a chain of consecutive value states. -/
inductive Chain : List (StoreRecord Addr Val) → Option Val → Option Val → Prop where
| nil (state : Option Val) : Chain [] state state
| cons {r : StoreRecord Addr Val} {rs : List (StoreRecord Addr Val)} {start finish : Option Val} :
start = r.before → Chain rs r.after finish → Chain (r::rs) start finish
/-- Address-filtered chains characterize the exact chronological memory semantics. -/
theorem runs_iff_address_chains {xs : List (StoreRecord Addr Val)}
{m n : Addr → Option Val} :
Runs xs m n ↔ ∀ a, Chain (At a xs) (m a) (n a) := by
induction xs generalizing m with
| nil =>
constructor
· intro h
cases h
exact fun _ => .nil _
· intro h
have he : m = n := funext fun a => by
have ha := h a
change Chain [] (m a) (n a) at ha
have hs {u v : Option Val} (h : Chain ([] : List (StoreRecord Addr Val)) u v) : u = v := by
cases h
rfl
exact hs ha
subst n
exact .nil _
| cons r rs ih =>
constructor
· intro h
cases h with
| cons hRead hRest =>
have hr := ih.mp hRest
intro a
by_cases he : a = r.addr
· subst a
simp only [At,List.filter_cons,beq_self_eq_true,if_true]
have hc : Chain (At r.addr rs) r.after (n r.addr) := by simpa using hr r.addr
exact .cons hRead hc
· have he' : (r.addr == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm he)
simpa only [At,List.filter_cons,he',Bool.false_eq_true,if_false,Function.update_of_ne he] using hr a
· intro h
have hh := h r.addr
simp only [At,List.filter_cons,beq_self_eq_true,if_true] at hh
cases hh with
| cons hRead hRest =>
refine .cons hRead (ih.mpr fun a => ?_)
by_cases he : a = r.addr
· subst a
simpa [At] using hRest
· have he' : (r.addr == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm he)
simpa only [At,List.filter_cons,he',Bool.false_eq_true,if_false,Function.update_of_ne he] using h a
/-- A stable permutation grouped by address preserves memory consistency. -/
theorem runs_of_stable {xs ys : List (StoreRecord Addr Val)} {m n : Addr → Option Val}
(h : ∀ a, At a xs = At a ys) : Runs xs m n ↔ Runs ys m n := by
simp only [runs_iff_address_chains,h]
/-- Consecutive checkpoint groups compose exactly when the shared snapshot agrees. -/
theorem runs_concat_of_groups {groups : List (List (StoreRecord Addr Val))}
(trace : List (Addr → Option Val))
(h : List.Forall₂ (fun xs (mn : (Addr → Option Val) × (Addr → Option Val)) =>
Runs xs mn.1 mn.2) groups (trace.zip trace.tail)) :
∀ m n, trace.head? = some m → trace.getLast? = some n →
Runs groups.flatten m n := by
induction groups generalizing trace with
| nil =>
intro m n hm hn
cases trace with
| nil => simp at hm
| cons k ks =>
cases ks with
| nil =>
simp at hm hn
subst m
subst n
exact .nil _
| cons l ls => cases h
| cons xs groups ih =>
intro m n hm hn
cases trace with
| nil => simp at hm
| cons k ks =>
cases ks with
| nil => cases h
| cons l ls =>
simp at hm
subst m
change List.Forall₂ _ (xs::groups) ((k,l)::((l::ls).zip ls)) at h
cases h with
| cons hRun hRest =>
have hTail : Runs groups.flatten l n := ih (l::ls) hRest l n (by simp) (by simpa using hn)
exact runs_append.mpr ⟨l,hRun,hTail⟩
end StoreRecord
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- An edge in the witness dictionary of prefixes of wide binary words. The identifier
zero is reserved for the empty prefix. -/
structure WordEdge where
parent : ℕ
digit : ℕ
child : ℕ
deriving DecidableEq
namespace WordEdge
def key (e : WordEdge) : ℕ × ℕ := (e.parent,e.digit)
/-- The two sorts certify these two functional dependencies. Edges with identical
keys have identical children, and edges with identical children have identical keys. -/
structure Interned (edges : List WordEdge) : Prop where
nonzero : ∀ e ∈ edges, e.child ≠ 0
keyFn : ∀ e ∈ edges, ∀ f ∈ edges, e.key = f.key → e.child = f.child
childFn : ∀ e ∈ edges, ∀ f ∈ edges, e.child = f.child → e.key = f.key
/-- The input digit list is in reverse path order, so a cons follows one more trie edge. -/
inductive Represents (edges : List WordEdge) : List ℕ → ℕ → Prop where
| nil : Represents edges [] 0
| cons {d : ℕ} {ds : List ℕ} {parent child : ℕ} :
Represents edges ds parent → (⟨parent,d,child⟩ : WordEdge) ∈ edges →
Represents edges (d::ds) child
theorem Represents.functional {edges : List WordEdge} (hi : Interned edges)
{digits : List ℕ} {i j : ℕ} (h : Represents edges digits i)
(h' : Represents edges digits j) : i = j := by
induction h generalizing j with
| nil => cases h'; rfl
| @cons d ds a b _ h1 ih =>
cases h' with
| @cons _ _ c t h2 h3 =>
have he : a = c := ih h2
exact hi.keyFn _ h1 _ h3 (by simp [key,he])
theorem Represents.injective {edges : List WordEdge} (hi : Interned edges)
{s t : List ℕ} {i : ℕ} (h : Represents edges s i)
(h' : Represents edges t i) : s = t := by
induction h generalizing t with
| nil =>
cases h' with
| nil => rfl
| cons _ h3 => exact False.elim (hi.nonzero _ h3 rfl)
| @cons d ds a b _ h1 ih =>
cases h' with
| nil => exact False.elim (hi.nonzero _ h1 rfl)
| @cons e es c _ h2 h3 =>
have hk := hi.childFn _ h1 _ h3 rfl
have hac : a = c := congrArg Prod.fst hk
have hde : d = e := congrArg Prod.snd hk
subst c e
exact congrArg (List.cons d) (ih h2)
theorem Represents.eq_iff {edges : List WordEdge} (hi : Interned edges)
{s t : List ℕ} {i j : ℕ} (h : Represents edges s i)
(h' : Represents edges t j) : i = j ↔ s = t := by
constructor
· intro hh
subst j
exact h.injective hi h'
· intro hh
subst t
exact h.functional hi h'
private def suffixes : List ℕ → Finset (List ℕ)
| [] => ∅
| d::ds => insert (d::ds) (suffixes ds)
private theorem suffixes_nonempty {xs ys : List ℕ} (h : ys ∈ suffixes xs) : ys ≠ [] := by
induction xs with
| nil => simp [suffixes] at h
| cons x xs ih =>
rcases Finset.mem_insert.mp h with rfl | h
· simp
· exact ih h
private theorem suffixes_card_le (xs : List ℕ) : (suffixes xs).card ≤ xs.length := by
induction xs with
| nil => simp [suffixes]
| cons x xs ih =>
exact (Finset.card_insert_le ..).trans (Nat.succ_le_succ ih)
private theorem suffixes_tail {xs ys : List ℕ} (h : ys ∈ suffixes xs) :
ys.tail = [] ∨ ys.tail ∈ suffixes xs := by
induction xs with
| nil => simp [suffixes] at h
| cons x xs ih =>
rcases Finset.mem_insert.mp h with rfl | h
· cases xs with
| nil => exact Or.inl rfl
| cons a as =>
exact Or.inr (Finset.mem_insert_of_mem (Finset.mem_insert_self ..))
· rcases ih h with h | h
· exact Or.inl h
· exact Or.inr (Finset.mem_insert_of_mem h)
private def vocabulary : List (List ℕ) → Finset (List ℕ)
| [] => ∅
| w::ws => suffixes w ∪ vocabulary ws
private theorem vocabulary_card_le (words : List (List ℕ)) :
(vocabulary words).card ≤ (words.map List.length).sum := by
induction words with
| nil => simp [vocabulary]
| cons w ws ih =>
exact (Finset.card_union_le ..).trans (Nat.add_le_add (suffixes_card_le w) ih)
private theorem suffixes_subset_vocabulary {w : List ℕ} {words : List (List ℕ)}
(h : w ∈ words) : suffixes w ⊆ vocabulary words := by
induction words with
| nil => simp at h
| cons z zs ih =>
rcases List.mem_cons.1 h with rfl | h
· exact Finset.subset_union_left
· exact (ih h).trans Finset.subset_union_right
private theorem vocabulary_nonempty {words : List (List ℕ)} {ys : List ℕ}
(h : ys ∈ vocabulary words) : ys ≠ [] := by
induction words with
| nil => simp [vocabulary] at h
| cons w ws ih =>
rcases Finset.mem_union.mp h with h | h
· exact suffixes_nonempty h
· exact ih h
private theorem vocabulary_tail {words : List (List ℕ)} {ys : List ℕ}
(h : ys ∈ vocabulary words) : ys.tail = [] ∨ ys.tail ∈ vocabulary words := by
induction words with
| nil => simp [vocabulary] at h
| cons w ws ih =>
rcases Finset.mem_union.mp h with h | h
· exact (suffixes_tail h).imp_right (Finset.mem_union_left _)
· exact (ih h).imp_right (Finset.mem_union_right _)
private theorem vocabulary_full_mem {words : List (List ℕ)} {ys : List ℕ}
(h : ys ∈ words) (hne : ys ≠ []) : ys ∈ vocabulary words := by
apply suffixes_subset_vocabulary h
cases ys with
| nil => exact False.elim (hne rfl)
| cons x xs => exact Finset.mem_insert_self ..
private theorem vocabulary_label_exists (words : List (List ℕ)) :
∃ lab : List ℕ → ℕ, lab [] = 0 ∧
(∀ w ∈ vocabulary words, 0 < lab w ∧ lab w ≤ (words.map List.length).sum) ∧
(∀ u ∈ insert [] (vocabulary words), ∀ v ∈ insert [] (vocabulary words),
lab u = lab v → u = v) := by
classical
let X := vocabulary words
let enc : X ≃ Fin X.card :=
Fintype.equivFinOfCardEq (by simp)
let lab (w : List ℕ) : ℕ := if h : w ∈ X then (enc ⟨w,h⟩).val+1 else 0
have hn : [] ∉ X := fun h => vocabulary_nonempty h rfl
refine ⟨lab, dif_neg hn, ?_, ?_⟩
· intro w hw
rw [show lab w = (enc ⟨w,hw⟩).val+1 from dif_pos hw]
exact ⟨Nat.zero_lt_succ _, (enc ⟨w,hw⟩).isLt.trans_le (vocabulary_card_le words)⟩
· intro u hu v hv he
rcases Finset.mem_insert.mp hu with rfl | hu
· by_contra hh
have h v (hv : v ∈ X) : lab v ≠ 0 := by rw [show lab v = _ from dif_pos hv]; omega
exact h v ((Finset.mem_insert.mp hv).resolve_left (Ne.symm hh)) (he.symm.trans (dif_neg hn))
· have hpos : 0 < lab u := by rw [show lab u = (enc ⟨u,hu⟩).val+1 from dif_pos hu]; omega
rcases Finset.mem_insert.mp hv with rfl | hv
· rw [show lab [] = 0 from dif_neg hn] at he
omega
· have heq : (enc ⟨u,hu⟩).val+1 = (enc ⟨v,hv⟩).val+1 := by
rw [← show lab u = _ from dif_pos hu, ← show lab v = _ from dif_pos hv]
exact he
have hval : (enc ⟨u,hu⟩).val = (enc ⟨v,hv⟩).val := by omega
exact congrArg Subtype.val (enc.injective (Fin.ext hval))
/-- An arbitrary batch of words has an interned dictionary with no more records
than the total number of digits. Identifiers are bounded by that same budget. -/
theorem intern_exists (words : List (List ℕ)) :
∃ (edges : List WordEdge) (lab : List ℕ → ℕ), Interned edges ∧ edges.length ≤ (words.map List.length).sum ∧
(∀ w ∈ words, Represents edges w (lab w)) ∧
∀ e ∈ edges, max e.parent e.child ≤ (words.map List.length).sum := by
classical
obtain ⟨lab,hzero,hbound,hinj⟩ := vocabulary_label_exists words
let build (w : List ℕ) : WordEdge := ⟨lab w.tail,w.headD 0,lab w⟩
let edges := (vocabulary words).toList.map build
have htail (w : List ℕ) (hw : w ∈ vocabulary words) :
w.tail ∈ insert [] (vocabulary words) := by
rcases vocabulary_tail hw with h | h
· simp [h]
· exact Finset.mem_insert_of_mem h
have hmem (w : List ℕ) (hw : w ∈ vocabulary words) : build w ∈ edges := by
apply List.mem_map.2
exact ⟨w,Finset.mem_toList.2 hw,rfl⟩
have habst (e : WordEdge) (he : e ∈ edges) :
∃ w ∈ vocabulary words, e = build w := by
obtain ⟨w,hw,heq⟩ := List.mem_map.1 he
exact ⟨w,Finset.mem_toList.1 hw,heq.symm⟩
refine ⟨edges,lab, ⟨?_,?_,?_⟩, ?_, ?_, ?_⟩
· intro e he
obtain ⟨w,hw,rfl⟩ := habst e he
exact (hbound w hw).1.ne'
· intro e he f hf heq
obtain ⟨u,hu,rfl⟩ := habst e he
obtain ⟨v,hv,rfl⟩ := habst f hf
have h1 : lab u.tail = lab v.tail := congrArg Prod.fst heq
have h2 : u.headD 0 = v.headD 0 := congrArg Prod.snd heq
have h3 : u.tail = v.tail := hinj _ (htail _ hu) _ (htail _ hv) h1
have heq : u = v := by
cases u with
| nil => exact False.elim (vocabulary_nonempty hu rfl)
| cons x xs =>
cases v with
| nil => exact False.elim (vocabulary_nonempty hv rfl)
| cons y ys =>
have hx : x = y := h2
have hs : xs = ys := h3
rw [hx,hs]
rw [heq]
· intro e he f hf heq
obtain ⟨u,hu,rfl⟩ := habst e he
obtain ⟨v,hv,rfl⟩ := habst f hf
have h : u = v := hinj _ (Finset.mem_insert_of_mem hu) _ (Finset.mem_insert_of_mem hv) heq
rw [h]
· simpa [edges] using vocabulary_card_le words
· have code (w : List ℕ) (hw : w = [] ∨ w ∈ vocabulary words) :
Represents edges w (lab w) := by
induction w with
| nil => rw [hzero]; exact .nil
| cons d ds ih =>
have hm : d::ds ∈ vocabulary words := hw.resolve_left (by simp)
have hc : build (d::ds) ∈ edges := hmem _ hm
exact .cons (ih (vocabulary_tail hm)) hc
intro w hw
by_cases h : w = []
· exact code _ (.inl h)
· exact code _ (.inr (vocabulary_full_mem hw h))
· intro e he
obtain ⟨w,hw,rfl⟩ := habst e he
have hc : lab w ≤ (words.map List.length).sum := (hbound w hw).2
have hp : lab w.tail ≤ (words.map List.length).sum := by
rcases vocabulary_tail hw with ht | ht
· rw [ht,hzero]
exact Nat.zero_le _
· exact (hbound _ ht).2
exact max_le hp hc
end WordEdge
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- In a key-ordered list, adjacent equal-key comparisons establish a global
functional dependency. Only non-strict monotonicity and antisymmetry are used. -/
theorem functional_of_adjacent {α β γ : Type} [PartialOrder β] {rows : List α}
(key : α → β) (value : α → γ)
(ordered : rows.Pairwise (fun e f => key e ≤ key f))
(adjacent : rows.IsChain (fun e f => key e = key f → value e = value f)) :
∀ e ∈ rows, ∀ f ∈ rows, key e = key f → value e = value f := by
induction rows with
| nil => simp
| cons head tail ih =>
obtain ⟨firstLE, orderedTail⟩ := List.pairwise_cons.1 ordered
have adjTail : tail.IsChain (fun e f => key e = key f → value e = value f) := by
cases tail with
| nil => simp
| cons next rest => exact (List.isChain_cons_cons.mp adjacent).2
have htail := ih orderedTail adjTail
have headEq (f : α) (hf : f ∈ tail) (hkey : key head = key f) : value head = value f := by
cases tail with
| nil => simp at hf
| cons next rest =>
have hle : key next ≤ key f := by
rcases List.mem_cons.1 hf with rfl | hf
· exact le_rfl
· exact (List.pairwise_cons.1 orderedTail).1 _ hf
have heq : key head = key next :=
le_antisymm (firstLE next (by simp)) (hkey ▸ hle)
exact ((List.isChain_cons_cons.1 adjacent).1 heq).trans
(htail next (by simp) f hf (heq.symm.trans hkey))
intro e he f hf hkey
rcases List.mem_cons.1 he with hh | he
· subst e
rcases List.mem_cons.1 hf with hh | hf
· rw [hh]
· exact headEq _ hf hkey
· rcases List.mem_cons.1 hf with hh | hf
· subst f
exact (headEq _ he hkey.symm).symm
· exact htail e he f hf hkey
open WordEdge in
/-- Two sorted-permutation checks on the occupied chunk lanes certify canonical
interning. The key sort uses an injective packing of the parent identifier and
the next digit. -/
theorem interned_of_sorted_certificates
(edges keySort childSort : List WordEdge) {β : Type} [PartialOrder β]
(pack : (ℕ × ℕ) → β) (pack_injective : Function.Injective pack)
(nonzero : ∀ e ∈ edges, e.child ≠ 0)
(keyPerm : keySort.Perm edges) (childPerm : childSort.Perm edges)
(keyOrdered : keySort.Pairwise (fun e f => pack e.key ≤ pack f.key))
(childOrdered : childSort.Pairwise (fun e f => e.child ≤ f.child))
(keyCheck : keySort.IsChain (fun e f => pack e.key = pack f.key → e.child = f.child))
(childCheck : childSort.IsChain (fun e f => e.child = f.child → pack e.key = pack f.key)) :
WordEdge.Interned edges := by
have hkey := functional_of_adjacent (pack ∘ WordEdge.key) WordEdge.child keyOrdered keyCheck
have hchild := functional_of_adjacent WordEdge.child (pack ∘ WordEdge.key) childOrdered childCheck
refine ⟨nonzero,?_,?_⟩
· intro e he f hf h
exact hkey _ (keyPerm.mem_iff.2 he) _ (keyPerm.mem_iff.2 hf) (congrArg pack h)
· intro e he f hf h
exact pack_injective (hchild _ (childPerm.mem_iff.2 he) _ (childPerm.mem_iff.2 hf) h)
theorem WordEdge.Interned.of_subset {edges more : List WordEdge}
(h : WordEdge.Interned more) (sub : ∀ x ∈ edges, x ∈ more) :
WordEdge.Interned edges where
nonzero e he := h.nonzero e (sub e he)
keyFn e he f hf := h.keyFn e (sub e he) f (sub f hf)
childFn e he f hf := h.childFn e (sub e he) f (sub f hf)
/-- An occupied word chunk provides exactly one actual trie-edge occurrence. -/
def WordEdge.Chain (edges : List WordEdge) (digits : List ℕ) (id : ℕ) : Prop :=
(edges.map WordEdge.digit = digits) ∧
(edges.head?.elim 0 WordEdge.child = id) ∧
(edges.getLast?.elim 0 WordEdge.parent = 0) ∧
edges.IsChain (fun e f => e.parent = f.child)
theorem WordEdge.Represents.exists_chain {dict : List WordEdge} {digits : List ℕ} {id : ℕ}
(h : WordEdge.Represents dict digits id) :
∃ rows, WordEdge.Chain rows digits id ∧ ∀ e ∈ rows, e ∈ dict := by
induction h with
| nil => exact ⟨[],by simp [WordEdge.Chain],by simp⟩
| @cons d ds parent child hp he ih =>
obtain ⟨rows,⟨hmap,hfirst,hlast,hlink⟩,hsub⟩ := ih
let row : WordEdge := ⟨parent,d,child⟩
refine ⟨row::rows,⟨?_, rfl, ?_, ?_⟩,?_⟩
· simp [row,hmap]
· cases rows with
| nil => simpa using hfirst.symm
| cons first rest =>
simpa using hlast
· cases rows with
| nil => simp
| cons first rest =>
apply List.isChain_cons_cons.2
exact ⟨hfirst.symm,hlink⟩
· intro e h
rcases List.mem_cons.1 h with rfl | h
· exact he
· exact hsub _ h
/-- Reading the lane rows as a linked chain gives the exact trie certificate. -/
theorem WordEdge.Chain.represents {dict rows : List WordEdge} {digits : List ℕ} {id : ℕ}
(h : WordEdge.Chain rows digits id) (sub : ∀ e ∈ rows, e ∈ dict) :
WordEdge.Represents dict digits id := by
induction rows generalizing digits id with
| nil =>
obtain ⟨hm,hf,_,_⟩ := h
simp at hm hf
subst digits id
exact .nil
| cons e es ih =>
obtain ⟨hm,hf,hl,hlink⟩ := h
have hs : WordEdge.Chain es (es.map WordEdge.digit) e.parent := by
cases es with
| nil =>
have hr : e.parent = 0 := hl
simp [WordEdge.Chain,hr]
| cons f fs =>
obtain ⟨hrel,htail⟩ := List.isChain_cons_cons.1 hlink
exact ⟨rfl,hrel.symm,by simpa using hl,htail⟩
have hh := ih hs (fun f hf => sub f (by simp [hf]))
subst digits id
exact .cons hh (sub e (by simp))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Even labels encode short words literally. Odd labels use trie identifiers for
long words. The tag separates the two representations, including at zero. -/
inductive WordLabel (b : ℕ) (dict : List WordEdge) : ℕ → ℕ → Prop where
| small {x : ℕ} : x.size ≤ b → WordLabel b dict x (2*x)
| wide {x id : ℕ} : b < x.size → WordEdge.Represents dict (Nat.digits (2^b) x) id →
WordLabel b dict x (2*id+1)
theorem WordLabel.eq_iff {b : ℕ} {dict : List WordEdge} (good : WordEdge.Interned dict)
{x y i j : ℕ} (hx : WordLabel b dict x i) (hy : WordLabel b dict y j) :
i = j ↔ x = y := by
cases hx <;> cases hy
· omega
· constructor
· omega
· intro h
subst y
omega
· constructor
· omega
· intro h
subst y
omega
· rename_i u hu hi v hv hj
have hd := hi.eq_iff good hj
rw [Nat.digits_inj_iff] at hd
omega
theorem WordLabel.size_le {b : ℕ} {dict : List WordEdge} {x i : ℕ}
(hx : WordLabel b dict x i)
(bound : ∀ e ∈ dict, e.child < 2^b) :
i.size ≤ b+1 ∧ i.size ≤ x.size+1 := by
cases hx with
| small hx =>
have hu : 2*x < 2^(x.size+1) := by
rw [Nat.pow_succ]
have hlt := Nat.lt_size_self x
omega
have hsize := Nat.size_le.mpr hu
omega
| @wide id hx hr =>
have huAux {ds : List ℕ} {z : ℕ} (h : WordEdge.Represents dict ds z) : z < 2^b := by
cases h with
| nil => exact Nat.pow_pos (by decide)
| cons _ h => exact bound _ h
have hu := huAux hr
have hs : (2*id+1).size ≤ b+1 := by
apply Nat.size_le.mpr
rw [Nat.pow_succ]
omega
omega
/-- Supply compact labels for all words in a batch. Dictionary size and maximal ID
are at most the total digit count of the wide words, not the sum of their values. -/
theorem wordLabels_exist (b : ℕ) (words : List ℕ) :
∃ (dict : List WordEdge) (label : ℕ → ℕ),
WordEdge.Interned dict ∧ label 0 = 0 ∧
(∀ x ∈ words, WordLabel b dict x (label x)) ∧
let slots := (((words.filter fun x => b < x.size).map (Nat.digits (2^b))).map List.length).sum
dict.length ≤ slots ∧ ∀ e ∈ dict, max e.parent e.child ≤ slots := by
let wide := (words.filter fun x => b < x.size).map (Nat.digits (2^b))
obtain ⟨dict,code,hGood,hSize,hRep,hBound⟩ := WordEdge.intern_exists wide
let label (x : ℕ) : ℕ := if b < x.size then 2*code (Nat.digits (2^b) x)+1 else 2*x
refine ⟨dict,label,hGood,by simp [label],?_,hSize,hBound⟩
intro x hx
by_cases h : b < x.size
· have hm : Nat.digits (2^b) x ∈ wide := by
apply List.mem_map.2
refine ⟨x,List.mem_filter.2 ⟨hx,by simpa using h⟩,rfl⟩
simpa only [label,if_pos h] using (WordLabel.wide h (hRep _ hm))
· simpa only [label,if_neg h] using (WordLabel.small (Nat.le_of_not_gt h))
/-- The compact representation checks the same reads and writes. The store need
only agree at represented addresses. -/
structure AccessLabels (b : ℕ) (dict : List WordEdge) (e e' : MemoryAccess) : Prop where
address : WordLabel b dict e.address e'.address
value : WordLabel b dict e.value e'.value
writes : e.writes = e'.writes
def MemoryLabels (b : ℕ) (dict : List WordEdge) (mem mem' : Memory) : Prop :=
∀ a z, WordLabel b dict a z → WordLabel b dict (mem a) (mem' z)
theorem AccessLabels.update {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
(good : WordEdge.Interned dict) (agree : MemoryLabels b dict mem mem')
{e e' : MemoryAccess} (he : AccessLabels b dict e e') :
MemoryLabels b dict (Function.update mem e.address e.value)
(Function.update mem' e'.address e'.value) := by
intro a z hz
by_cases h : a = e.address
· have hz' : z = e'.address := ((hz.eq_iff good he.address).2 h)
subst a z
simpa using he.value
· have hz' : z ≠ e'.address := (hz.eq_iff good he.address).not.mpr h
simpa only [Function.update_of_ne h, Function.update_of_ne hz'] using agree a z hz
theorem AccessLabels.check_iff {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
(good : WordEdge.Interned dict) (agree : MemoryLabels b dict mem mem')
{e e' : MemoryAccess} (he : AccessLabels b dict e e') :
(e.writes = true ∨ mem e.address = e.value) ↔
(e'.writes = true ∨ mem' e'.address = e'.value) :=
or_congr (he.writes ▸ Iff.rfl) ((agree _ _ he.address).eq_iff good he.value).symm
/-- Compact labels preserve the exact logical behavior of the recorded memory
trace. Thus the tiered, sorted memory certificate can use these compact labels
while each arithmetic packet keeps its full source words. -/
theorem memoryValid_iff_compact {b : ℕ} {dict : List WordEdge} {mem mem' : Memory}
{events events' : List MemoryAccess} (good : WordEdge.Interned dict)
(agree : MemoryLabels b dict mem mem')
(hLabels : List.Forall₂ (AccessLabels b dict) events events') :
memoryValid mem events ↔ memoryValid mem' events' := by
induction hLabels generalizing mem mem' with
| nil => rfl
| cons hx _ ih =>
exact and_congr (hx.check_iff good agree) (ih (hx.update good agree))
theorem memoryValid_initial_iff_compact {b : ℕ} {dict : List WordEdge}
{events events' : List MemoryAccess} (good : WordEdge.Interned dict)
(hLabels : List.Forall₂ (AccessLabels b dict) events events') :
memoryValid (fun _ => 0) events ↔ memoryValid (fun _ => 0) events' :=
memoryValid_iff_compact good (fun _ _ _ => WordLabel.small (by simp)) hLabels
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
abbrev Tier := ℕ → ℕ → ℕ
abbrev TierRecord := StoreRecord (ℕ × ℕ) ℕ
/-- A logical address has one live value. Its physical tier is determined by
that address and value. Initial zero values have their own live records. -/
def liveMemory (tier : Tier) (mem : Memory) : (ℕ × ℕ) → Option ℕ :=
fun key => if key.1 = tier key.2 (mem key.2) then some (mem key.2) else none
theorem liveMemory_some_iff (tier : Tier) (mem : Memory) (key : ℕ × ℕ) (v : ℕ) :
liveMemory tier mem key = some v ↔ key.1 = tier key.2 v ∧ mem key.2 = v := by
unfold liveMemory
split <;> simp_all
intro he hmem
exact ‹_ ≠ _› (by simpa [hmem] using he)
/-- Attach the old value of every write. For a change of tier, cancel the old
copy before creating the new live value. The two actions share the same logical
address, allowing local checks to identify them. -/
def tieredAccess (tier : Tier) (e : MemoryAccess) (old : ℕ) : List TierRecord :=
let dest := (tier e.address e.value, e.address)
let src := (tier e.address old, e.address)
if e.writes then
if src = dest then [⟨dest, some old, some e.value⟩]
else [⟨src, some old, none⟩, ⟨dest, none, some e.value⟩]
else [⟨dest, some e.value, some e.value⟩]
theorem tieredAccess_length (tier : Tier) (e : MemoryAccess) (old : ℕ) :
(tieredAccess tier e old).length ≤ 2 := by
simp only [tieredAccess]
split <;> (try split) <;> simp
private theorem live_replace (tier : Tier) (mem : Memory) (a v : ℕ)
(h : tier a (mem a) = tier a v) :
liveMemory tier (Function.update mem a v) =
Function.update (liveMemory tier mem) (tier a v,a) (some v) := by
funext key
obtain ⟨t,b⟩ := key
by_cases hb : b = a
· subst b
by_cases ht : t = tier a v
· subst t
simp [liveMemory]
· simp [liveMemory, h, ht]
· have hk : (t,b) ≠ (tier a v,a) := by simp [hb]
simp [liveMemory, Function.update_of_ne hb, Function.update_of_ne hk]
private theorem live_move (tier : Tier) (mem : Memory) (a v : ℕ)
(h : tier a (mem a) ≠ tier a v) :
liveMemory tier (Function.update mem a v) =
Function.update (Function.update (liveMemory tier mem) (tier a (mem a),a) none)
(tier a v,a) (some v) := by
funext key
obtain ⟨t,b⟩ := key
by_cases hb : b = a
· subst b
by_cases ht : t = tier a v
· subst t
simp [liveMemory]
· by_cases hs : t = tier a (mem a)
· subst t
simp [liveMemory, h]
· simp [liveMemory, ht, hs]
· have hk : (t,b) ≠ (tier a v,a) := by simp [hb]
have hl : (t,b) ≠ (tier a (mem a),a) := by simp [hb]
simp [liveMemory, Function.update_of_ne hb, Function.update_of_ne hk, Function.update_of_ne hl]
/-- Checking one tiered action enforces exactly the RAM read condition and results
in the same logical memory update. A write's old-value witness cannot be forged
because it must name an existing live record. -/
theorem tieredAccess_sound {tier : Tier} {mem : Memory} {e : MemoryAccess}
{old : ℕ} {finish : (ℕ × ℕ) → Option ℕ}
(run : StoreRecord.Runs (tieredAccess tier e old) (liveMemory tier mem) finish) :
(e.writes = true ∨ mem e.address = e.value) ∧
(e.writes = true → old = mem e.address) ∧
finish = liveMemory tier (Function.update mem e.address e.value) := by
simp only [tieredAccess] at run
split at run
· rename_i hw
split at run
· rename_i same
cases run with
| cons hbefore rest =>
cases rest
obtain ⟨htier,hold⟩ := (liveMemory_some_iff ..).mp hbefore
change (tier e.address e.value : ℕ) = tier e.address old at htier
change mem e.address = old at hold
have heq : tier e.address (mem e.address) = tier e.address e.value := (congrArg (tier e.address) hold).trans htier.symm
exact ⟨Or.inl hw, fun _ => hold.symm, (live_replace _ _ _ _ heq).symm⟩
· rename_i diff
cases run with
| cons hbefore rest =>
cases rest with
| cons _ done =>
cases done
obtain ⟨_,hold⟩ := (liveMemory_some_iff ..).mp hbefore
change mem e.address = old at hold
have hdiff : tier e.address (mem e.address) ≠ tier e.address e.value := by
intro eq
exact diff (Prod.ext (hold ▸ eq) rfl)
subst old
exact ⟨Or.inl hw, fun _ => rfl, (live_move _ _ _ _ hdiff).symm⟩
· rename_i hw
cases run with
| cons hbefore rest =>
cases rest
obtain ⟨_,hv⟩ := (liveMemory_some_iff ..).mp hbefore
have hkeep (s : (ℕ × ℕ) → Option ℕ) (key : ℕ × ℕ) (v : ℕ)
(h : s key = some v) : Function.update s key (some v) = s := by
rw [← h, Function.update_eq_self]
refine ⟨Or.inr hv, fun h => False.elim (hw h), ?_⟩
rw [hkeep _ _ _ hbefore, ← hv, Function.update_eq_self]
theorem tieredAccess_complete (tier : Tier) (mem : Memory) (e : MemoryAccess)
(h : e.writes = true ∨ mem e.address = e.value) :
StoreRecord.Runs (tieredAccess tier e (mem e.address)) (liveMemory tier mem)
(liveMemory tier (Function.update mem e.address e.value)) := by
unfold tieredAccess
dsimp
split
· rename_i hw
split
· rename_i same
have hs : tier e.address (mem e.address) = tier e.address e.value := congrArg Prod.fst same
rw [live_replace _ _ _ _ hs]
exact .cons ((liveMemory_some_iff ..).mpr ⟨hs.symm, rfl⟩) (.nil _)
· rename_i diff
have hs : tier e.address (mem e.address) ≠ tier e.address e.value :=
fun h => diff (Prod.ext h rfl)
rw [live_move _ _ _ _ hs]
refine .cons ((liveMemory_some_iff ..).mpr ⟨rfl,rfl⟩) (.cons ?_ (.nil _))
simp [liveMemory, hs.symm]
· rename_i hw
have hv := h.resolve_left hw
rw [live_replace _ _ _ _ (congrArg (tier e.address) hv)]
exact .cons ((liveMemory_some_iff ..).mpr ⟨rfl,hv⟩) (.nil _)
/-- A witness for the old word at each write yields the chronologically ordered
tiered store records. -/
inductive TieredTrace (tier : Tier) : List MemoryAccess → List TierRecord → Prop where
| nil : TieredTrace tier [] []
| cons {e : MemoryAccess} {es : List MemoryAccess} {old : ℕ} {rs : List TierRecord} :
TieredTrace tier es rs → TieredTrace tier (e :: es) (tieredAccess tier e old ++ rs)
theorem TieredTrace.length_le {tier : Tier} {events : List MemoryAccess} {records : List TierRecord}
(expanded : TieredTrace tier events records) :
records.length ≤ 2*events.length := by
induction expanded with
| nil => simp
| @cons e es old rs hx ih =>
have hl := tieredAccess_length tier e old
simp only [List.length_append, List.length_cons]
omega
theorem TieredTrace.sound {tier : Tier} {events : List MemoryAccess} {records : List TierRecord}
(expanded : TieredTrace tier events records) (mem : Memory)
{finish : (ℕ × ℕ) → Option ℕ}
(run : StoreRecord.Runs records (liveMemory tier mem) finish) :
memoryValid mem events ∧ finish = liveMemory tier (replay mem events) := by
induction expanded generalizing mem with
| nil =>
cases run
exact ⟨trivial, rfl⟩
| cons hex ih =>
obtain ⟨mid, hr, hs⟩ := StoreRecord.runs_append.1 run
obtain ⟨hv, _, hm⟩ := tieredAccess_sound hr
subst mid
obtain ⟨hValid, hFinish⟩ := ih _ hs
exact ⟨⟨hv,hValid⟩,hFinish⟩
theorem tieredTrace_complete (tier : Tier) (events : List MemoryAccess) (mem : Memory)
(valid : memoryValid mem events) :
∃ records, TieredTrace tier events records ∧
StoreRecord.Runs records (liveMemory tier mem) (liveMemory tier (replay mem events)) := by
induction events generalizing mem with
| nil => exact ⟨[], .nil, .nil _⟩
| cons e es ih =>
obtain ⟨hr,hs⟩ := valid
obtain ⟨rs,ht,hrun⟩ := ih _ hs
exact ⟨_, .cons ht, StoreRecord.runs_append.2 ⟨_, tieredAccess_complete _ _ _ hr, hrun⟩⟩
theorem memoryValid_iff_tieredTrace (tier : Tier) (events : List MemoryAccess) (mem : Memory) :
memoryValid mem events ↔ ∃ records finish,
TieredTrace tier events records ∧ StoreRecord.Runs records (liveMemory tier mem) finish := by
constructor
· intro hv
obtain ⟨rs,hex,hr⟩ := tieredTrace_complete tier events mem hv
exact ⟨rs,_,hex,hr⟩
· rintro ⟨rs,finish,hex,hr⟩
exact (hex.sound _ hr).1
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
abbrev LocalRecord := StoreRecord ℕ ℕ
abbrev LocalMemory := ℕ → Option ℕ
def localRecord (r : TierRecord) : LocalRecord := ⟨r.addr.2,r.before,r.after⟩
/-- Pass a tier to its own verifier, preserving chronological order. -/
def atTier (j : ℕ) (records : List TierRecord) : List LocalRecord :=
(records.filter fun r => decide (r.addr.1 = j)).map localRecord
private theorem At_atTier (records : List TierRecord) (j a : ℕ) :
StoreRecord.At a (atTier j records) =
(StoreRecord.At (j,a) records).map localRecord := by
simp only [atTier, StoreRecord.At, List.filter_map, List.filter_filter]
congr 1
apply congrArg (fun f : TierRecord → Bool => records.filter f)
funext r
rcases r with ⟨⟨i,k⟩,_,_⟩
apply Bool.eq_iff_iff.2
simp [localRecord, beq_iff_eq, and_comm]
private theorem chain_map_local (rs : List TierRecord) (before after : Option ℕ) :
StoreRecord.Chain (rs.map localRecord) before after ↔
StoreRecord.Chain rs before after := by
induction rs generalizing before with
| nil => constructor <;> intro h <;> cases h <;> exact .nil _
| cons r rs ih =>
constructor
· intro h
cases h with
| cons hr hs => exact .cons hr (ih _ |>.1 hs)
· intro h
cases h with
| cons hr hs => exact .cons hr (ih _ |>.2 hs)
/-- Partitioning by tier is sound even though records from different tiers can
refer to the same logical address. Their physical keys are different. -/
theorem tier_runs_iff (records : List TierRecord) (start finish : (ℕ × ℕ) → Option ℕ) :
StoreRecord.Runs records start finish ↔
∀ j, StoreRecord.Runs (atTier j records) (fun a => start (j,a)) (fun a => finish (j,a)) := by
rw [StoreRecord.runs_iff_address_chains]
simp_rw [StoreRecord.runs_iff_address_chains, At_atTier, chain_map_local]
constructor
· intro H j a
exact H (j,a)
· intro H key
exact H key.1 key.2
def localReplay : LocalMemory → List LocalRecord → LocalMemory
| mem, [] => mem
| mem, e::es => localReplay (Function.update mem e.addr e.after) es
def localValid : LocalMemory → List LocalRecord → Prop
| _, [] => True
| mem, e::es => mem e.addr = e.before ∧
localValid (Function.update mem e.addr e.after) es
theorem localRuns_iff (start finish : LocalMemory) (records : List LocalRecord) :
StoreRecord.Runs records start finish ↔
localValid start records ∧ finish = localReplay start records := by
induction records generalizing start with
| nil =>
constructor
· intro h; cases h; exact ⟨trivial,rfl⟩
· rintro ⟨_,rfl⟩
exact .nil _
| cons e es ih =>
constructor
· intro h
cases h with
| cons he hs =>
obtain ⟨hv,hr⟩ := (ih _).1 hs
exact ⟨⟨he,hv⟩,hr⟩
· rintro ⟨⟨he,hv⟩,hr⟩
exact .cons he ((ih _).2 ⟨hv,hr⟩)
/-- Check a sorted local trace without a dynamic memory lookup. Each nonfirst
record compares only against the preceding record, or the fixed initialization
rule if it starts a new address block. -/
def localAdjacent (start : LocalMemory) (records : List LocalRecord) : Prop :=
(records.head?.elim True fun r => start r.addr = r.before) ∧
records.IsChain (fun r s =>
(if r.addr = s.addr then r.after else start s.addr) = s.before)
theorem localAdjacent_iff_localValid (start : LocalMemory) (records : List LocalRecord)
(ordered : records.Pairwise (fun r s => r.addr ≤ s.addr)) :
localAdjacent start records ↔ localValid start records := by
induction records generalizing start with
| nil => simp [localAdjacent,localValid]
| cons e es ih =>
obtain ⟨horder, hs⟩ := List.pairwise_cons.1 ordered
cases es with
| nil => simp [localAdjacent,localValid]
| cons f fs =>
simp only [localAdjacent, List.head?_cons, Option.elim, List.isChain_cons_cons,localValid]
have hs' := ih (Function.update start e.addr e.after) hs
have hprev : (if e.addr = f.addr then e.after else start f.addr) =
Function.update start e.addr e.after f.addr := by
by_cases h : e.addr = f.addr <;> simp [h, Function.update, eq_comm]
have hchain (a b : LocalRecord) (hf : f.addr ≤ a.addr) (hb : a.addr ≤ b.addr) :
(if a.addr = b.addr then a.after else start b.addr) =
(if a.addr = b.addr then a.after
else Function.update start e.addr e.after b.addr) := by
by_cases heq : a.addr = b.addr
· simp [heq]
· have h₁ : e.addr ≤ f.addr := horder f (by simp)
have h₂ : b.addr ≠ e.addr := by omega
simp [heq, Function.update_of_ne h₂]
have hc :
(f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after else start b.addr) = b.before) ↔
(f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after
else Function.update start e.addr e.after b.addr) = b.before) := by
have hrel (a b : LocalRecord) (ha : a ∈ f :: fs) (hh : a.addr ≤ b.addr) :
((if a.addr = b.addr then a.after else start b.addr) = b.before) ↔
((if a.addr = b.addr then a.after
else Function.update start e.addr e.after b.addr) = b.before) := by
have hfa : f.addr ≤ a.addr := by
rcases List.mem_cons.1 ha with rfl | ha
· exact Nat.le_refl _
· exact (List.pairwise_cons.1 hs).1 _ ha
rw [hchain a b hfa hh]
have pchain := hs.isChain
simp only [List.isChain_iff_getElem] at pchain ⊢
refine forall_congr' (fun i => forall_congr' (fun hi => ?_))
exact hrel _ _ (List.getElem_mem (by omega)) (pchain i hi)
have heq : localValid (Function.update start e.addr e.after) (f :: fs) ↔
((if e.addr = f.addr then e.after else start f.addr) = f.before) ∧
(f :: fs).IsChain (fun a b => (if a.addr = b.addr then a.after else start b.addr) = b.before) := by
rw [← hs', localAdjacent]
simp only [List.head?_cons, Option.elim, ← hprev, ← hc]
simp only [localValid] at heq
rw [heq]
/-- Lexicographic order by the address, then by the original position. The
position is supplied as a local batch index. -/
def localTaggedLE (x y : LocalRecord × ℕ) : Prop :=
x.1.addr < y.1.addr ∨ (x.1.addr = y.1.addr ∧ x.2 ≤ y.2)
theorem localTaggedLE_trans (x y z : LocalRecord × ℕ) :
localTaggedLE x y → localTaggedLE y z → localTaggedLE x z := by
unfold localTaggedLE
rintro (hx | ⟨hx,ht⟩) (hy | ⟨hy,ht'⟩) <;> omega
theorem localTaggedLE_total (x y : LocalRecord × ℕ) : localTaggedLE x y ∨ localTaggedLE y x := by
unfold localTaggedLE
omega
private theorem localTaggedLE_addr {x y : LocalRecord × ℕ} (h : localTaggedLE x y) :
x.1.addr ≤ y.1.addr := by
rcases h with h | ⟨h,_⟩ <;> omega
private theorem localTaggedLE_time {x y : LocalRecord × ℕ}
(ha : x.1.addr = y.1.addr) (h : localTaggedLE x y) : x.2 ≤ y.2 := by
rcases h with h | ⟨_,h⟩ <;> omega
private theorem same_clock {tr : List (LocalRecord × ℕ)}
(chron : tr.Pairwise (fun a b => a.2 < b.2)) {x y : LocalRecord × ℕ}
(hx : x ∈ tr) (hy : y ∈ tr) (he : x.2 = y.2) : x = y := by
obtain ⟨i,hi,hx'⟩ := List.getElem_of_mem hx
obtain ⟨j,hj,hy'⟩ := List.getElem_of_mem hy
have ht : tr[i].2 = tr[j].2 := by rw [hx',hy',he]
have hij : i = j := by
rcases Nat.lt_trichotomy i j with h|h|h
· have hh := List.pairwise_iff_getElem.1 chron i j hi hj h
omega
· exact h
· have hh := List.pairwise_iff_getElem.1 chron j i hj hi h
omega
subst j
exact hx'.symm.trans hy'
theorem localTagged_stable_general {trace sorted : List (LocalRecord × ℕ)}
(chron : trace.Pairwise (fun a b => a.2 < b.2))
(hperm : sorted.Perm trace) (horder : sorted.Pairwise localTaggedLE) :
∀ addr, StoreRecord.At addr (trace.map Prod.fst) = StoreRecord.At addr (sorted.map Prod.fst) := by
intro addr
let filterKey (a : LocalRecord × ℕ) : Bool := a.1.addr == addr
have htime₁ : (trace.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) :=
(chron.imp fun h => Nat.le_of_lt h).filter filterKey
have htime₂ : (sorted.filter filterKey).Pairwise (fun a b => a.2 ≤ b.2) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj hij
let a := (sorted.filter filterKey)[i]
let b := (sorted.filter filterKey)[j]
have ha : a ∈ sorted.filter filterKey := List.getElem_mem hi
have hb : b ∈ sorted.filter filterKey := List.getElem_mem hj
have ht : localTaggedLE a b :=
List.pairwise_iff_getElem.1 (horder.filter filterKey) i j hi hj hij
have heq : a.1.addr = b.1.addr := by
have hx := (List.mem_filter.1 ha).2
have hy := (List.mem_filter.1 hb).2
simp only [filterKey, beq_iff_eq] at hx hy
exact hx.trans hy.symm
exact localTaggedLE_time heq ht
have hlex : trace.filter filterKey = sorted.filter filterKey := by
apply List.Perm.eq_of_pairwise (le := fun a b : LocalRecord × ℕ => decide (a.2 ≤ b.2))
· intro a b ha hb hle hge
have hp₁ : a ∈ trace := (List.mem_filter.1 ha).1
have hp₂ : b ∈ trace := hperm.mem_iff.1 (List.mem_filter.1 hb).1
exact same_clock chron hp₁ hp₂ (Nat.le_antisymm (of_decide_eq_true hle) (of_decide_eq_true hge))
· simpa using htime₁
· simpa using htime₂
· exact (hperm.filter filterKey).symm
have hh := congrArg (List.map Prod.fst) hlex
simpa only [StoreRecord.At,List.filter_map,Function.comp_def,filterKey] using hh
theorem localTagged_stable {trace : List LocalRecord} {sorted : List (LocalRecord × ℕ)}
(hperm : sorted.Perm trace.zipIdx) (horder : sorted.Pairwise localTaggedLE) :
∀ addr, StoreRecord.At addr trace = StoreRecord.At addr (sorted.map Prod.fst) := by
have htime : trace.zipIdx.Pairwise (fun a b => a.2 < b.2) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj hij
simpa [List.getElem_zipIdx] using hij
simpa only [List.zipIdx_map_fst] using localTagged_stable_general htime hperm horder
theorem localSorted_exists (trace : List LocalRecord) :
∃ sorted : List (LocalRecord × ℕ), sorted.Perm trace.zipIdx ∧ sorted.Pairwise localTaggedLE := by
classical
let cmp (x y : LocalRecord × ℕ) := decide (localTaggedLE x y)
refine ⟨trace.zipIdx.mergeSort cmp,List.mergeSort_perm _ _,?_⟩
have ht (x y z : LocalRecord × ℕ) (h1 : cmp x y = true) (h2 : cmp y z = true) : cmp x z = true :=
decide_eq_true (localTaggedLE_trans x y z (of_decide_eq_true h1) (of_decide_eq_true h2))
have ho (x y : LocalRecord × ℕ) : (cmp x y || cmp y x) = true := by
simpa [cmp] using localTaggedLE_total x y
simpa only [cmp,decide_eq_true_eq] using List.pairwise_mergeSort (le := cmp) ht ho trace.zipIdx
/-- Exact validity of an arbitrary tagged sorting certificate. After sorting,
adjacent comparison is sufficient for each record. -/
theorem sortedMemory_iff (start : LocalMemory) (trace : List LocalRecord)
(sorted : List (LocalRecord × ℕ))
(perm : sorted.Perm trace.zipIdx) (ordered : sorted.Pairwise localTaggedLE) :
localAdjacent start (sorted.map Prod.fst) ↔
∃ finish, StoreRecord.Runs trace start finish := by
have htag : (sorted.map Prod.fst).Pairwise (fun a b => a.addr ≤ b.addr) :=
List.pairwise_map.mpr (ordered.imp fun h => localTaggedLE_addr h)
rw [localAdjacent_iff_localValid _ _ htag]
constructor
· intro h
let finish := localReplay start (sorted.map Prod.fst)
exact ⟨finish, (StoreRecord.runs_of_stable (localTagged_stable perm ordered)).mpr
((localRuns_iff _ _ _).2 ⟨h,rfl⟩)⟩
· rintro ⟨finish,h⟩
exact ((localRuns_iff _ _ _).1
((StoreRecord.runs_of_stable (localTagged_stable perm ordered)).mp h)).1
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- A local sort witness for one physical group. -/
def LocalCertificate (start : LocalMemory) (trace : List LocalRecord) : Prop :=
∃ sorted : List (LocalRecord × ℕ), sorted.Perm trace.zipIdx ∧
sorted.Pairwise localTaggedLE ∧ localAdjacent start (sorted.map Prod.fst)
theorem localCertificate_iff (start : LocalMemory) (records : List LocalRecord) :
LocalCertificate start records ↔ ∃ finish, StoreRecord.Runs records start finish := by
constructor
· rintro ⟨sorted,hp,ho,hc⟩
exact (sortedMemory_iff start records sorted hp ho).1 hc
· intro h
obtain ⟨sorted,hp,ho⟩ := localSorted_exists records
exact ⟨sorted,hp,ho,(sortedMemory_iff start records sorted hp ho).2 h⟩
/-- An address range provides the entire finite snapshot at a group boundary. -/
def LocalMemory.Restricted (q : ℕ) (state : LocalMemory) : Prop :=
∀ a, q ≤ a → state a = none
def beginSnapshot (q : ℕ) (state : LocalMemory) : List LocalRecord :=
(List.range q).map (fun a => ⟨a,none,state a⟩)
def endSnapshot (q : ℕ) (state : LocalMemory) : List LocalRecord :=
(List.range q).map (fun a => ⟨a,state a,none⟩)
def frameGroup (q : ℕ) (start finish : LocalMemory) (group : List LocalRecord) :
List LocalRecord :=
beginSnapshot q start ++ group ++ endSnapshot q finish
private theorem filter_range_key (a q : ℕ) :
(List.range q).filter (fun x => x == a) = if a < q then [a] else [] := by
induction q with
| zero => simp
| succ q ih =>
rw [List.range_succ,List.filter_append,ih]
by_cases h : a < q
· simp [h,show a < q+1 by omega,show q ≠ a by omega]
· by_cases he : q = a
· subst a
simp
· simp [h,he,show ¬a < q+1 by omega]
private theorem at_map_range (mk : ℕ → LocalRecord) (h : ∀ a, (mk a).addr = a) (a q : ℕ) :
StoreRecord.At a ((List.range q).map mk) = if a < q then [mk a] else [] := by
have he : ((fun r : LocalRecord => r.addr == a) ∘ mk) = (fun x => x == a) :=
funext fun x => by simp [h]
rw [StoreRecord.At,List.filter_map,he,filter_range_key]
split <;> rfl
theorem beginSnapshot_run (q : ℕ) (state : LocalMemory)
(bounded : LocalMemory.Restricted q state) :
StoreRecord.Runs (beginSnapshot q state) (fun _ => none) state := by
apply StoreRecord.runs_iff_address_chains.mpr
intro a
unfold beginSnapshot
rw [at_map_range _ (fun _ => rfl)]
split
· exact .cons rfl (.nil _)
· rename_i ha
rw [bounded a (Nat.le_of_not_gt ha)]
exact .nil _
theorem endSnapshot_run (q : ℕ) (state : LocalMemory)
(bounded : LocalMemory.Restricted q state) :
StoreRecord.Runs (endSnapshot q state) state (fun _ => none) := by
apply StoreRecord.runs_iff_address_chains.mpr
intro a
unfold endSnapshot
rw [at_map_range _ (fun _ => rfl)]
split
· exact .cons rfl (.nil _)
· rename_i ha
rw [bounded a (Nat.le_of_not_gt ha)]
exact .nil _
theorem localRun_outside {q : ℕ} {group : List LocalRecord} {start finish : LocalMemory}
(bounded : ∀ r ∈ group, r.addr < q) (initial : LocalMemory.Restricted q start)
(run : StoreRecord.Runs group start finish) :
LocalMemory.Restricted q finish := by
intro a ha
have hch := (StoreRecord.runs_iff_address_chains.1 run) a
have hnil : StoreRecord.At a group = [] := by
apply List.filter_eq_nil_iff.2
intro r hr
have hh := bounded r hr
have he : r.addr ≠ a := by omega
simp [he]
rw [hnil,initial a ha] at hch
have empty {u v : Option ℕ} (hh : StoreRecord.Chain ([] : List LocalRecord) u v) : u=v := by
cases hh
rfl
exact (empty hch).symm
private theorem endSnapshot_injective_initial (q : ℕ) (m finish state : LocalMemory)
(boundedM : LocalMemory.Restricted q m) (boundedN : LocalMemory.Restricted q state)
(run : StoreRecord.Runs (endSnapshot q state) m finish) :
m = state := by
funext a
by_cases h : a < q
· have hch := (StoreRecord.runs_iff_address_chains.1 run) a
rw [endSnapshot,at_map_range _ (fun _ => rfl),if_pos h] at hch
cases hch
assumption
· rw [boundedM a (Nat.le_of_not_gt h),boundedN a (Nat.le_of_not_gt h)]
/-- Checking a group's boundary records gives exactly its declared start and
finish states. The sorted circuit itself has a constant all-absent initialization. -/
theorem frameGroup_iff_run (q : ℕ) (start finish : LocalMemory) (group : List LocalRecord)
(bounded : ∀ r ∈ group, r.addr < q) (hs : LocalMemory.Restricted q start)
(hf : LocalMemory.Restricted q finish) :
LocalCertificate (fun _ => none) (frameGroup q start finish group) ↔
StoreRecord.Runs group start finish := by
rw [localCertificate_iff]
constructor
· rintro ⟨final,run⟩
obtain ⟨middle,run₂,run₃⟩ := StoreRecord.runs_append.1 run
obtain ⟨start',run₁,run₂⟩ := StoreRecord.runs_append.1 run₂
have hRun := beginSnapshot_run q start hs
have hStart := ((localRuns_iff _ _ _).1 run₁).2.trans
((localRuns_iff _ _ _).1 hRun).2.symm
subst start'
have hMid := endSnapshot_injective_initial q middle final finish
(localRun_outside bounded hs run₂) hf run₃
subst middle
exact run₂
· intro run
refine ⟨_, StoreRecord.runs_append.2 ⟨finish, ?_, endSnapshot_run q finish hf⟩⟩
exact StoreRecord.runs_append.2 ⟨start,beginSnapshot_run q start hs,run⟩
/-- Fixed groups, including the last padded group. The group count and capacity
depend only on the circuit shape. -/
def fixedGroups {α : Type} (capacity : ℕ) : ℕ → List α → List (List α)
| 0, _ => []
| count+1, rows => rows.take capacity :: fixedGroups capacity count (rows.drop capacity)
@[simp] theorem fixedGroups_length {α : Type} (rows : List α) (capacity count : ℕ) :
(fixedGroups capacity count rows).length = count := by
induction count generalizing rows with
| zero => rfl
| succ count ih => simp [fixedGroups,ih]
theorem fixedGroups_each_length {α : Type} (rows : List α) (capacity count : ℕ) :
∀ g ∈ fixedGroups capacity count rows, g.length ≤ capacity := by
induction count generalizing rows with
| zero => simp [fixedGroups]
| succ count ih =>
intro g hg
rcases List.mem_cons.1 hg with (rfl|hg)
· simp
· exact ih _ _ hg
theorem fixedGroups_flatten {α : Type} (rows : List α) (capacity count : ℕ)
(h : rows.length ≤ capacity * count) :
(fixedGroups capacity count rows).flatten = rows := by
induction count generalizing rows with
| zero =>
simp at h
simp [h,fixedGroups]
| succ count ih =>
have hd : (rows.drop capacity).length ≤ capacity*count := by
rw [List.length_drop]
rw [Nat.mul_succ] at h
omega
simp only [fixedGroups,List.flatten_cons,ih _ hd,List.take_append_drop]
/-- Snapshot witnesses for fixed groups, with each boundary checked exactly once
as a finish and once as a start. -/
inductive SnapshotCertificate (q : ℕ) : List (List LocalRecord) → LocalMemory → Prop where
| nil (m : LocalMemory) : SnapshotCertificate q [] m
| cons {xs : List LocalRecord} {rest : List (List LocalRecord)} {m n : LocalMemory} :
LocalMemory.Restricted q n →
LocalCertificate (fun _ => none) (frameGroup q m n xs) →
SnapshotCertificate q rest n → SnapshotCertificate q (xs::rest) m
theorem snapshotCertificate_iff (q : ℕ) (groups : List (List LocalRecord)) (start : LocalMemory)
(bounded : ∀ group ∈ groups, ∀ r ∈ group, r.addr < q)
(hStart : LocalMemory.Restricted q start) :
SnapshotCertificate q groups start ↔ ∃ finish, StoreRecord.Runs groups.flatten start finish := by
induction groups generalizing start with
| nil => exact ⟨fun _ => ⟨_,.nil _⟩,fun _ => .nil _⟩
| cons group gs ih =>
have hGroup := bounded group (by simp)
have hRest : ∀ g ∈ gs, ∀ r ∈ g, r.addr < q :=
fun g hg => bounded g (List.mem_cons_of_mem _ hg)
constructor
· intro h
cases h with
| cons hn cert rest =>
obtain ⟨finish,run⟩ := (ih _ hRest hn).1 rest
exact ⟨finish,StoreRecord.runs_append.2 ⟨_,
(frameGroup_iff_run _ _ _ _ hGroup hStart hn).1 cert,run⟩⟩
· rintro ⟨finish,run⟩
obtain ⟨mid,run₁,run₂⟩ := StoreRecord.runs_append.1 run
have hm := localRun_outside hGroup hStart run₁
exact .cons hm ((frameGroup_iff_run _ _ _ _ hGroup hStart hm).2 run₁)
((ih _ hRest hm).2 ⟨finish,run₂⟩)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
def activeTagged (rows : List (Option LocalRecord × ℕ)) : List (LocalRecord × ℕ) :=
rows.filterMap (fun row => row.1.map (fun active => (active,row.2)))
theorem activeTagged_chron (rows : List (Option LocalRecord × ℕ))
(ordered : rows.Pairwise (fun a b => a.2 < b.2)) :
(activeTagged rows).Pairwise (fun a b => a.2 < b.2) := by
apply ordered.filterMap
intro x y hlt u hx v hy
rcases x with ⟨ox,i⟩
rcases y with ⟨oy,j⟩
cases ox <;> cases oy <;> simp_all
rw [←hx,←hy]
exact hlt
theorem activeTagged_of_slots (rows : List (Option LocalRecord)) (offset : ℕ) :
(activeTagged (rows.zipIdx offset)).map Prod.fst = rows.filterMap id := by
induction rows generalizing offset with
| nil => rfl
| cons r rs ih =>
rw [List.zipIdx_cons]
cases r <;> simp_all [activeTagged]
/-- A fixed network may permute all rows, including blanks. Occupied records
carry their original physical row numbers. No compaction is needed for their
timestamps, since gaps do not change the chronological order. -/
theorem slotSorted_iff (initial : LocalMemory) (rows : List (Option LocalRecord))
(sorted : List (Option LocalRecord × ℕ))
(hperm : sorted.Perm rows.zipIdx)
(horder : (activeTagged sorted).Pairwise localTaggedLE) :
localAdjacent initial ((activeTagged sorted).map Prod.fst) ↔
∃ final, StoreRecord.Runs (rows.filterMap id) initial final := by
have htime : rows.zipIdx.Pairwise (fun a b => a.2 < b.2) := by
apply List.pairwise_iff_getElem.2
intro i j hi hj hij
simpa [List.getElem_zipIdx] using hij
have hchron := activeTagged_chron rows.zipIdx htime
have hd : (activeTagged sorted).Perm (activeTagged rows.zipIdx) := hperm.filterMap _
have hs := localTagged_stable_general hchron hd horder
simp only [activeTagged_of_slots] at hs
have htag : ((activeTagged sorted).map Prod.fst).Pairwise (fun a b => a.addr ≤ b.addr) :=
List.pairwise_map.mpr (horder.imp fun h => localTaggedLE_addr h)
rw [localAdjacent_iff_localValid _ _ htag]
constructor
· intro hv
exact ⟨_, (StoreRecord.runs_of_stable hs).mpr ((localRuns_iff _ _ _).2 ⟨hv,rfl⟩)⟩
· rintro ⟨f,hr⟩
exact ((localRuns_iff _ _ _).1 ((StoreRecord.runs_of_stable hs).mp hr)).1
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Place occupied records before empty slots, then use local address and time. -/
def slotTaggedLE (x y : Option LocalRecord × ℕ) : Prop :=
match x.1,y.1 with
| some a,some b => localTaggedLE (a,x.2) (b,y.2)
| none,some _ => False
| _,none => True
theorem slotTaggedLE_trans (x y z : Option LocalRecord × ℕ) :
slotTaggedLE x y → slotTaggedLE y z → slotTaggedLE x z := by
rcases x with ⟨x,i⟩
rcases y with ⟨y,j⟩
rcases z with ⟨z,k⟩
cases x <;> cases y <;> cases z <;>
simp [slotTaggedLE]
exact localTaggedLE_trans _ _ _
theorem slotTaggedLE_total (x y : Option LocalRecord × ℕ) :
slotTaggedLE x y ∨ slotTaggedLE y x := by
rcases x with ⟨x,i⟩
rcases y with ⟨y,j⟩
cases x <;> cases y <;> simp [slotTaggedLE,localTaggedLE_total]
private theorem occupied_ordered {rows : List (Option LocalRecord × ℕ)}
(ho : rows.Pairwise slotTaggedLE) : (activeTagged rows).Pairwise localTaggedLE := by
apply ho.filterMap
intro x y h u hx v hy
rcases x with ⟨x,i⟩
rcases y with ⟨y,j⟩
cases x <;> cases y <;> simp_all [slotTaggedLE]
def slotBefore (initial : LocalMemory) (r s : Option LocalRecord × ℕ) : Prop :=
match r.1,s.1 with
| some a,some b => (if a.addr = b.addr then a.after else initial b.addr) = b.before
| _,_ => True
def slotsAdjacent (initial : LocalMemory) (rows : List (Option LocalRecord × ℕ)) : Prop :=
(rows.head?.bind Prod.fst |>.elim True fun r => initial r.addr = r.before) ∧
rows.IsChain (slotBefore initial)
private theorem no_active_after_blank {tail : List (Option LocalRecord × ℕ)} {j : ℕ}
(h : (none,j) :: tail |>.Pairwise slotTaggedLE) :
activeTagged tail = [] := by
apply List.filterMap_eq_nil_iff.2
intro x hx
have hp := (List.pairwise_cons.1 h).1 x hx
rcases x with ⟨r,i⟩
cases r <;> simp_all [slotTaggedLE]
private theorem slotsChain_iff_active (initial : LocalMemory)
(rows : List (Option LocalRecord × ℕ)) (hord : rows.Pairwise slotTaggedLE) :
rows.IsChain (slotBefore initial) ↔
((activeTagged rows).map Prod.fst).IsChain
(fun a b => (if a.addr = b.addr then a.after else initial b.addr) = b.before) := by
induction rows with
| nil => simp [activeTagged]
| cons e es ih =>
obtain ⟨r,j⟩ := e
have hTail := (List.pairwise_cons.1 hord).2
cases r with
| none =>
have hactive : activeTagged ((none,j) :: es) = [] := no_active_after_blank (tail := es) hord
rw [hactive]
simp only [List.map_nil,List.isChain_nil]
apply iff_true_intro
apply List.isChain_iff_getElem.2
intro i hi
have hs : ∀ x ∈ (none,j) :: es, x.1 = none := by
intro x hx
rcases List.mem_cons.1 hx with rfl | hx
· rfl
· have hp := (List.pairwise_cons.1 hord).1 x hx
cases x with
| mk r i => cases r <;> simp_all [slotTaggedLE]
unfold slotBefore
rw [hs _ (List.getElem_mem (by omega))]
cases ((none,j)::es)[i+1].1 <;> trivial
| some r =>
cases es with
| nil => simp [activeTagged]
| cons f fs =>
obtain ⟨s,k⟩ := f
cases s with
| none =>
have hp : activeTagged ((none,k) :: fs) = [] := no_active_after_blank (tail := fs) hTail
have hactive : activeTagged ((some r,j) :: (none,k) :: fs) = [(r,j)] :=
congrArg (List.cons (r,j)) hp
rw [hactive]
have htail := (ih hTail).2 (by simp [hp])
simp [slotBefore,htail,List.isChain_cons_cons]
| some s =>
have ht := ih hTail
simp only [activeTagged,List.filterMap_cons,Option.map,List.map_cons] at ht ⊢
simp only [List.isChain_cons_cons,slotBefore]
exact and_congr Iff.rfl ht
private theorem slotsAdjacent_iff_active (initial : LocalMemory)
(rows : List (Option LocalRecord × ℕ)) (hord : rows.Pairwise slotTaggedLE) :
slotsAdjacent initial rows ↔ localAdjacent initial ((activeTagged rows).map Prod.fst) := by
unfold slotsAdjacent localAdjacent
apply and_congr _ (slotsChain_iff_active initial rows hord)
cases rows with
| nil => rfl
| cons row rs =>
obtain ⟨r,i⟩ := row
cases r with
| none =>
have hactive : activeTagged ((none,i)::rs) = [] := no_active_after_blank (tail := rs) hord
simp [hactive]
| some r => rfl
def OptionalCertificate (initial : LocalMemory) (rows : List (Option LocalRecord)) : Prop :=
∃ sorted : List (Option LocalRecord × ℕ),
sorted.Perm rows.zipIdx ∧ sorted.Pairwise slotTaggedLE ∧ slotsAdjacent initial sorted
/-- Empty fixed lanes require no tests beyond sorted order. Chronological
adjacency is tested without removing them in the circuit. -/
theorem optionalCertificate_iff (initial : LocalMemory) (rows : List (Option LocalRecord)) :
OptionalCertificate initial rows ↔ ∃ finish, StoreRecord.Runs (rows.filterMap id) initial finish := by
constructor
· rintro ⟨sorted,hp,ho,ha⟩
exact (slotSorted_iff initial rows sorted hp (occupied_ordered ho)).1
((slotsAdjacent_iff_active initial sorted ho).1 ha)
· intro hw
classical
let cmp (x y : Option LocalRecord × ℕ) := decide (slotTaggedLE x y)
let sorted := rows.zipIdx.mergeSort cmp
have ht (x y z : Option LocalRecord × ℕ) (h1 : cmp x y = true) (h2 : cmp y z = true) :
cmp x z = true := decide_eq_true (slotTaggedLE_trans x y z
(of_decide_eq_true h1) (of_decide_eq_true h2))
have ho (x y : Option LocalRecord × ℕ) : (cmp x y || cmp y x) = true := by
simpa [cmp] using slotTaggedLE_total x y
have hsort : sorted.Pairwise slotTaggedLE := by
simpa only [cmp,decide_eq_true_eq] using List.pairwise_mergeSort (le := cmp) ht ho rows.zipIdx
have hp : sorted.Perm rows.zipIdx := List.mergeSort_perm _ _
have ha := (slotSorted_iff initial rows sorted hp (occupied_ordered hsort)).2 hw
exact ⟨sorted,hp,hsort,(slotsAdjacent_iff_active initial sorted hsort).2 ha⟩
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- The snapshot rows occupy fixed lanes; the middle lanes may be empty. -/
def optionFrame (q : ℕ) (start finish : LocalMemory) (rows : List (Option LocalRecord)) :
List (Option LocalRecord) :=
(beginSnapshot q start).map some ++ rows ++ (endSnapshot q finish).map some
theorem optionFrame_length (q : ℕ) (start finish : LocalMemory)
(rows : List (Option LocalRecord)) :
(optionFrame q start finish rows).length = q+rows.length+q := by
simp [optionFrame,beginSnapshot,endSnapshot,Nat.add_assoc]
theorem optionFrame_iff (q : ℕ) (start finish : LocalMemory) (rows : List (Option LocalRecord))
(bounded : ∀ r ∈ rows.filterMap id, r.addr < q)
(hs : LocalMemory.Restricted q start) (hf : LocalMemory.Restricted q finish) :
OptionalCertificate (fun _ => none) (optionFrame q start finish rows) ↔
StoreRecord.Runs (rows.filterMap id) start finish := by
rw [optionalCertificate_iff, ← frameGroup_iff_run _ _ _ _ bounded hs hf,localCertificate_iff]
simp [optionFrame,frameGroup,List.filterMap_append,List.filterMap_map]
/-- The group endpoints are represented by a sequence of finite snapshots, not by
linking all global memory values to all events. -/
inductive OptionSnapshotCertificate (q : ℕ) :
List (List (Option LocalRecord)) → LocalMemory → Prop where
| nil (m : LocalMemory) : OptionSnapshotCertificate q [] m
| cons {xs : List (Option LocalRecord)} {rest : List (List (Option LocalRecord))} {m n : LocalMemory} :
LocalMemory.Restricted q n →
OptionalCertificate (fun _ => none) (optionFrame q m n xs) →
OptionSnapshotCertificate q rest n → OptionSnapshotCertificate q (xs::rest) m
theorem optionSnapshotCertificate_iff (q : ℕ) (groups : List (List (Option LocalRecord)))
(start : LocalMemory)
(bounded : ∀ r ∈ groups.flatten.filterMap id, r.addr < q)
(hStart : LocalMemory.Restricted q start) :
OptionSnapshotCertificate q groups start ↔
∃ finish, StoreRecord.Runs (groups.flatten.filterMap id) start finish := by
induction groups generalizing start with
| nil => exact ⟨fun _ => ⟨_,.nil _⟩,fun _ => .nil _⟩
| cons group gs ih =>
simp only [List.flatten_cons,List.filterMap_append,List.mem_append] at bounded ⊢
have hGroup (r : LocalRecord) (hr : r ∈ group.filterMap id) := bounded r (.inl hr)
have hRest (r : LocalRecord) (hr : r ∈ gs.flatten.filterMap id) := bounded r (.inr hr)
constructor
· intro h
cases h with
| cons hn cert rest =>
obtain ⟨finish,run⟩ := (ih _ hRest hn).1 rest
exact ⟨finish,StoreRecord.runs_append.2 ⟨_,
(optionFrame_iff _ _ _ _ hGroup hStart hn).1 cert,run⟩⟩
· rintro ⟨finish,run⟩
obtain ⟨mid,run₁,run₂⟩ := StoreRecord.runs_append.1 run
have hm := localRun_outside hGroup hStart run₁
exact .cons hm ((optionFrame_iff _ _ _ _ hGroup hStart hm).2 run₁)
((ih _ hRest hm).2 ⟨finish,run₂⟩)
/-- With at most one group, use the known initialization and no snapshots. Otherwise
split the fixed chronological lanes before testing each group. -/
def TierBatchCertificate (q count : ℕ) (rows : List (Option LocalRecord)) (start : LocalMemory) :
Prop :=
if rows.length ≤ q then OptionalCertificate start rows
else OptionSnapshotCertificate q (fixedGroups q count rows) start
theorem tierBatchCertificate_iff (q count : ℕ) (rows : List (Option LocalRecord)) (start : LocalMemory)
(capacity : rows.length ≤ q*count)
(bounded : ∀ r ∈ rows.filterMap id, r.addr < q)
(hStart : LocalMemory.Restricted q start) :
TierBatchCertificate q count rows start ↔
∃ finish, StoreRecord.Runs (rows.filterMap id) start finish := by
unfold TierBatchCertificate
split
· exact optionalCertificate_iff start rows
· have hf := fixedGroups_flatten rows q count capacity
have hb : ∀ r ∈ (fixedGroups q count rows).flatten.filterMap id, r.addr < q := hf.symm ▸ bounded
have h := optionSnapshotCertificate_iff q (fixedGroups q count rows) start hb hStart
rw [hf] at h
exact h
theorem finite_tier_runs_iff (levels : ℕ) (records : List TierRecord) (start : (ℕ × ℕ) → Option ℕ)
(levelBound : ∀ r ∈ records, r.addr.1 < levels) :
(∃ finish, StoreRecord.Runs records start finish) ↔
∀ j < levels, ∃ finish, StoreRecord.Runs (atTier j records) (fun a => start (j,a)) finish := by
constructor
· rintro ⟨finish,hr⟩ j _
exact ⟨fun a => finish (j,a),(tier_runs_iff ..).1 hr j⟩
· intro h
classical
let finish (key : ℕ × ℕ) :=
if bound : key.1 < levels then (h key.1 bound).choose key.2 else start key
refine ⟨finish,(tier_runs_iff ..).2 fun j => ?_⟩
by_cases hj : j < levels
· simpa only [finish,dif_pos hj] using (h j hj).choose_spec
· have hnil : atTier j records = [] := by
unfold atTier
have hnone : (records.filter fun r => decide (r.addr.1 = j)) = [] := by
apply List.filter_eq_nil_iff.2
intro r hr
have hb := levelBound r hr
have hneq : r.addr.1 ≠ j := by omega
simp [hneq]
simp [hnone]
simpa only [hnil,finish,dif_neg hj] using (StoreRecord.Runs.nil (fun a => start (j,a)))
/-- Exact bounded memory verifier, over finite groups of chronologically ordered
physical lanes. It works with the compact labels from the word dictionary. -/
theorem finiteTiersCertificate_iff (levels : ℕ) (records : List TierRecord)
(start : (ℕ × ℕ) → Option ℕ) (q count : ℕ → ℕ)
(rows : ℕ → List (Option LocalRecord))
(levels_ok : ∀ r ∈ records, r.addr.1 < levels)
(projection : ∀ j < levels, (rows j).filterMap id = atTier j records)
(capacity : ∀ j < levels, (rows j).length ≤ q j * count j)
(bounded : ∀ j < levels, ∀ r ∈ atTier j records, r.addr < q j)
(start_ok : ∀ j < levels, LocalMemory.Restricted (q j) (fun a => start (j,a))) :
(∀ j < levels, TierBatchCertificate (q j) (count j) (rows j) (fun a => start (j,a))) ↔
∃ finish, StoreRecord.Runs records start finish := by
rw [finite_tier_runs_iff levels records start levels_ok]
refine forall_congr' fun j => forall_congr' fun hj => ?_
rw [tierBatchCertificate_iff _ _ _ _ (capacity j hj) ?_ (start_ok j hj), projection j hj]
intro r hr
exact bounded j hj r (projection j hj ▸ hr)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- An address and value use the narrowest dyadic width that contains their bits
and a leading marker. -/
def bitTier (address value : ℕ) : ℕ := (max address.size value.size).size
theorem bitTier_width (address value : ℕ) :
address.size < 2^bitTier address value ∧ value.size < 2^bitTier address value :=
⟨(le_max_left ..).trans_lt (Nat.lt_size_self _),
(le_max_right ..).trans_lt (Nat.lt_size_self _)⟩
theorem bitTier_le {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
bitTier a v ≤ b.size :=
Nat.size_le_size (max_le ha hv)
theorem bitTier_initial_restricted (j : ℕ) :
LocalMemory.Restricted (2^(2^j)) (fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
intro a h
have he : j ≠ bitTier a 0 := by
intro heq
have hsize := (bitTier_width a 0).1
rw [← heq] at hsize
have hA := Nat.size_le.mp hsize.le
omega
simp [liveMemory,he]
/-- Every actual tier record fits that tier's address and word width. -/
structure TierRecordFits (maxWidth : ℕ) (r : TierRecord) : Prop where
level : r.addr.1 ≤ maxWidth.size
address : r.addr.2.size < 2^r.addr.1
before : ∀ v, r.before = some v → v.size < 2^r.addr.1
after : ∀ v, r.after = some v → v.size < 2^r.addr.1
private theorem fits_read {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
TierRecordFits b (⟨(bitTier a v,a),some v,some v⟩ : TierRecord) := by
obtain ⟨h1,h2⟩ := bitTier_width a v
exact ⟨bitTier_le ha hv,h1,
fun _ he => Option.some.inj he ▸ h2,
fun _ he => Option.some.inj he ▸ h2⟩
private theorem fits_replace {a old v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b)
(same : bitTier a old = bitTier a v) :
TierRecordFits b (⟨(bitTier a v,a),some old,some v⟩ : TierRecord) := by
obtain ⟨h1,h2⟩ := bitTier_width a v
exact ⟨bitTier_le ha hv,h1,
fun _ he => Option.some.inj he ▸ (same ▸ (bitTier_width a old).2),
fun _ he => Option.some.inj he ▸ h2⟩
private theorem fits_cancel {a old b : ℕ} (ha : a.size ≤ b) (hv : old.size ≤ b) :
TierRecordFits b (⟨(bitTier a old,a),some old,none⟩ : TierRecord) := by
obtain ⟨h1,h2⟩ := bitTier_width a old
exact ⟨bitTier_le ha hv,h1,
fun _ he => Option.some.inj he ▸ h2,fun v he => by change none = some v at he; contradiction⟩
private theorem fits_install {a v b : ℕ} (ha : a.size ≤ b) (hv : v.size ≤ b) :
TierRecordFits b (⟨(bitTier a v,a),none,some v⟩ : TierRecord) := by
obtain ⟨h1,h2⟩ := bitTier_width a v
exact ⟨bitTier_le ha hv,h1,fun v he => by change none = some v at he; contradiction,
fun _ he => Option.some.inj he ▸ h2⟩
theorem tieredAccess_fits {e : MemoryAccess} {old b : ℕ}
(ha : e.address.size ≤ b) (hv : e.value.size ≤ b) (ho : old.size ≤ b) :
∀ r ∈ tieredAccess bitTier e old, TierRecordFits b r := by
intro r hr
unfold tieredAccess at hr
dsimp only at hr
split at hr
· split at hr
· rename_i hs
have hs' : bitTier e.address old = bitTier e.address e.value := congrArg Prod.fst hs
obtain rfl := List.mem_singleton.1 hr
exact fits_replace ha hv hs'
· simp only [List.mem_cons,List.not_mem_nil,or_false] at hr
rcases hr with rfl|rfl
· exact fits_cancel ha ho
· exact fits_install ha hv
· obtain rfl := List.mem_singleton.1 hr
exact fits_read ha hv
/-- Completeness for bounded compact words. Every generated tier record has both
its old and its new value within its dyadic word width. -/
theorem tieredTrace_complete_bounded (b : ℕ) (events : List MemoryAccess) (m : Memory)
(valid : memoryValid m events)
(start : ∀ a, (m a).size ≤ b)
(widths : ∀ e ∈ events, e.address.size ≤ b ∧ e.value.size ≤ b) :
∃ records, TieredTrace bitTier events records ∧
StoreRecord.Runs records (liveMemory bitTier m) (liveMemory bitTier (replay m events)) ∧
∀ r ∈ records, TierRecordFits b r := by
induction events generalizing m with
| nil => exact ⟨[],.nil,.nil _,by simp⟩
| cons e es ih =>
obtain ⟨hread,htail⟩ := valid
obtain ⟨ha,hv⟩ := widths e (by simp)
let m' := Function.update m e.address e.value
have hm' (a : ℕ) : (m' a).size ≤ b := by
by_cases he : a=e.address
· subst a; simpa [m'] using hv
· simpa only [m',Function.update_of_ne he] using start a
have hWidth (x : MemoryAccess) (hx : x ∈ es) := widths x (List.mem_cons_of_mem _ hx)
obtain ⟨rs,hex,hr,hfit⟩ := ih m' htail hm' hWidth
refine ⟨_,.cons (old := m e.address) hex,
StoreRecord.runs_append.2 ⟨liveMemory bitTier m',tieredAccess_complete _ _ _ hread,hr⟩,?_⟩
intro r h
rcases List.mem_append.1 h with h|h
· exact tieredAccess_fits ha hv (start e.address) r h
· exact hfit r h
theorem atTier_address_bounded {records : List TierRecord} {b j : ℕ}
(fits : ∀ r ∈ records, TierRecordFits b r) :
∀ r ∈ atTier j records, r.addr < 2^(2^j) := by
intro r hr
obtain ⟨r',hr',rfl⟩ := List.mem_map.1 hr
obtain ⟨hm,hj⟩ := List.mem_filter.1 hr'
simp only [decide_eq_true_eq] at hj
have ha := (fits r' hm).address
rw [hj] at ha
exact Nat.size_le.mp ha.le
/-- The exact compact memory verifier, for chronological slot rows of the
declared fixed shape. Bit widths imply the finite address and tier bounds. -/
theorem compactMemoryCertificate_iff {b : ℕ} {physical : List TierRecord}
(fits : ∀ r ∈ physical, TierRecordFits (b+1) r)
(count : ℕ → ℕ) (rows : ℕ → List (Option LocalRecord))
(projection : ∀ j < (b+1).size+1, (rows j).filterMap id = atTier j physical)
(capacity : ∀ j < (b+1).size+1, (rows j).length ≤ 2^(2^j)*count j) :
(∀ j < (b+1).size+1,
TierBatchCertificate (2^(2^j)) (count j) (rows j)
(fun a => liveMemory bitTier (fun _=>0) (j,a))) ↔
∃ final, StoreRecord.Runs physical (liveMemory bitTier (fun _=>0)) final := by
exact finiteTiersCertificate_iff _ _ _ _ _ _
(fun r hr => Nat.lt_succ_of_le (fits r hr).level)
projection capacity
(fun _ _ => atTier_address_bounded fits)
(fun j _ => bitTier_initial_restricted j)
theorem compactMemoryCertificate_sound {b : ℕ} {dict : List WordEdge}
{original compact : List MemoryAccess} (good : WordEdge.Interned dict)
(labels : List.Forall₂ (AccessLabels b dict) original compact)
{physical : List TierRecord} (expanded : TieredTrace bitTier compact physical)
(fits : ∀ r ∈ physical, TierRecordFits (b+1) r)
(count : ℕ → ℕ) (rows : ℕ → List (Option LocalRecord))
(projection : ∀ j < (b+1).size+1, (rows j).filterMap id = atTier j physical)
(capacity : ∀ j < (b+1).size+1, (rows j).length ≤ 2^(2^j)*count j)
(certificate : ∀ j < (b+1).size+1,
TierBatchCertificate (2^(2^j)) (count j) (rows j)
(fun a => liveMemory bitTier (fun _=>0) (j,a))) :
memoryValid (fun _=>0) original := by
obtain ⟨final,run⟩ :=
(compactMemoryCertificate_iff fits count rows projection capacity).1 certificate
exact (memoryValid_initial_iff_compact good labels).2 (expanded.sound _ run).1
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Raw and compact records have the same control flag and labels for each
observed word. The raw old field is immaterial on a read. -/
structure ObservedLabels (b : ℕ) (dict : List WordEdge) (r r' : ObservedAccess) : Prop where
action : AccessLabels b dict r.action r'.action
old : r.action.writes = true → WordLabel b dict r.old r'.old
theorem observedMemoryValid_iff_labels {b : ℕ} {dict : List WordEdge} {m m' : Memory}
{rows rows' : List ObservedAccess} (good : WordEdge.Interned dict)
(agree : MemoryLabels b dict m m') (h : List.Forall₂ (ObservedLabels b dict) rows rows') :
observedMemoryValid m rows ↔ observedMemoryValid m' rows' := by
induction h generalizing m m' with
| nil => rfl
| @cons r r' rest rest' hrow _ ih =>
refine and_congr ?_ (ih (hrow.action.update good agree))
have ha := agree _ _ hrow.action.address
cases hw : r.action.writes with
| false =>
have hw' : r'.action.writes = false := hrow.action.writes.symm.trans hw
simpa [hw,hw'] using (ha.eq_iff good hrow.action.value).symm
| true =>
have hw' : r'.action.writes = true := hrow.action.writes.symm.trans hw
simpa [hw,hw'] using (ha.eq_iff good (hrow.old hw)).symm
theorem observedMemoryValid_initial_iff_labels {b : ℕ} {dict : List WordEdge}
{rows rows' : List ObservedAccess} (good : WordEdge.Interned dict)
(h : List.Forall₂ (ObservedLabels b dict) rows rows') :
observedMemoryValid (fun _ => 0) rows ↔ observedMemoryValid (fun _ => 0) rows' :=
observedMemoryValid_iff_labels good (fun _ _ _ => WordLabel.small (by simp)) h
def tieredObservations (tier : Tier) (rows : List ObservedAccess) : List TierRecord :=
rows.flatMap fun row => tieredAccess tier row.action row.old
theorem tieredObservations_length (tier : Tier) (rows : List ObservedAccess) :
(tieredObservations tier rows).length ≤ 2*rows.length := by
induction rows with
| nil => simp [tieredObservations]
| cons r rs ih =>
have hr := tieredAccess_length tier r.action r.old
change (tieredAccess tier r.action r.old ++ tieredObservations tier rs).length ≤ _
simp only [List.length_append,List.length_cons]
omega
theorem tieredObservations_sound {tier : Tier} {m : Memory} {rows : List ObservedAccess}
{finish : (ℕ × ℕ) → Option ℕ}
(run : StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m) finish) :
observedMemoryValid m rows ∧ finish = liveMemory tier (replay m (rows.map ObservedAccess.action)) := by
induction rows generalizing m with
| nil => cases run; exact ⟨trivial,rfl⟩
| cons row tail ih =>
change StoreRecord.Runs (tieredAccess tier row.action row.old ++ tieredObservations tier tail) _ _ at run
obtain ⟨mid, first, last⟩ := StoreRecord.runs_append.mp run
obtain ⟨he,hold,rfl⟩ := tieredAccess_sound first
obtain ⟨ht,hf⟩ := ih last
refine ⟨⟨?_,ht⟩,hf⟩
cases hw : row.action.writes with
| false => simpa [hw] using (he.resolve_left (by simp [hw]))
| true => simpa [hw] using (hold hw).symm
theorem tieredObservations_complete (tier : Tier) (m : Memory) (rows : List ObservedAccess)
(h : observedMemoryValid m rows) :
StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m)
(liveMemory tier (replay m (rows.map ObservedAccess.action))) := by
induction rows generalizing m with
| nil => exact .nil _
| cons row tail ih =>
obtain ⟨he,ht⟩ := h
change StoreRecord.Runs (tieredAccess tier row.action row.old ++ tieredObservations tier tail) _ _
apply StoreRecord.runs_append.mpr
refine ⟨liveMemory tier (Function.update m row.action.address row.action.value),?_,ih _ ht⟩
cases hw : row.action.writes with
| false =>
have hh : m row.action.address = row.action.value := by simpa [hw] using he
have hlocal := tieredAccess_complete tier m row.action (Or.inr hh)
simpa [tieredAccess,hw] using hlocal
| true =>
have hh : m row.action.address = row.old := by simpa [hw] using he
rw [← hh]
exact tieredAccess_complete tier m row.action (Or.inl hw)
theorem observedMemoryValid_iff_tieredObservations (tier : Tier) (m : Memory)
(rows : List ObservedAccess) : observedMemoryValid m rows ↔ ∃ finish,
StoreRecord.Runs (tieredObservations tier rows) (liveMemory tier m) finish :=
⟨fun h => ⟨_,tieredObservations_complete _ _ _ h⟩, fun ⟨_,run⟩ => (tieredObservations_sound run).1⟩
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- A long word contributes at most twice its binary length divided by the
number of bits in each trie digit. -/
theorem labelDigitWeight {b x : ℕ} (hb : 0 < b) (hx : b < x.size) :
b*((Nat.digits (2^b) x).length) ≤ 2*x.size := by
let q := (x.size-1)/b+1
have hmod := Nat.mod_lt (x.size-1) hb
have he := Nat.div_add_mod (x.size-1) b
have hq : x.size ≤ b*q := by
unfold q
rw [Nat.mul_add,Nat.mul_one]
omega
have hxq : x < (2^b)^q := by
rw [← Nat.pow_mul]
exact Nat.size_le.mp hq
have hb' : 1 < 2^b := one_lt_pow₀ (by decide) (Nat.ne_zero_of_lt hb)
have hlen := (Nat.digits_length_le_iff hb' x).2 hxq
refine (Nat.mul_le_mul_left b hlen).trans ?_
unfold q
rw [Nat.mul_add,Nat.mul_one]
have hp := Nat.div_mul_le_self (x.size-1) b
rw [Nat.mul_comm ((x.size-1)/b)] at hp
omega
def labelEntries (b : ℕ) (words : List ℕ) : ℕ :=
(((words.filter fun x => b < x.size).map (Nat.digits (2^b))).map List.length).sum
theorem labelEntries_budget {b : ℕ} (hb : 0 < b) (words : List ℕ) :
b*labelEntries b words ≤ 2*(words.map Nat.size).sum := by
induction words with
| nil => simp [labelEntries]
| cons x xs ih =>
unfold labelEntries at ih ⊢
rw [List.filter_cons]
by_cases hx : b < x.size
· simp only [decide_eq_true_eq, hx, if_true, List.map_cons,List.sum_cons,Nat.mul_add]
exact Nat.add_le_add (labelDigitWeight hb hx) ih
· simp only [decide_eq_true_eq,hx,if_false,List.map_cons,List.sum_cons,Nat.mul_add]
exact ih.trans (Nat.le_add_left _ _)
theorem wordLabels_exist_bounded (words : List ℕ) {B : ℕ}
(hB : (words.map Nat.size).sum ≤ B) (b : ℕ) (hb : 0 < b) (hLarge : 2*B < 2^b) :
∃ (dict : List WordEdge) (label : ℕ → ℕ),
WordEdge.Interned dict ∧ label 0 = 0 ∧
dict.length ≤ labelEntries b words ∧
(∀ e ∈ dict, max e.parent e.child < 2^b) ∧
∀ x ∈ words, WordLabel b dict x (label x) ∧ (label x).size ≤ b+1 ∧ (label x).size ≤ x.size+1 := by
obtain ⟨d,l,hGood,hl0,hword,hd,hBound⟩ := wordLabels_exist b words
have hs : labelEntries b words ≤ 2*B := by
calc
_ ≤ b*labelEntries b words := by simpa using (Nat.mul_le_mul_right (labelEntries b words) hb)
_ ≤ 2*(words.map Nat.size).sum := labelEntries_budget hb words
_ ≤ _ := Nat.mul_le_mul_left _ hB
have hChild (e : WordEdge) (he : e ∈ d) : max e.parent e.child < 2^b :=
((hBound e he).trans hs).trans_lt hLarge
exact ⟨d,l,hGood,hl0,hd,hChild,fun x hx => ⟨hword x hx,
(hword x hx).size_le (fun e he => (le_max_right ..).trans_lt (hChild e he))⟩⟩
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
private theorem bitSum_lt (f : ℕ → Bool) (m : ℕ) :
((List.range m).map fun k => (f k).toNat*2^k).sum < 2^m := by
induction m with
| zero => simp
| succ m ih =>
rw [List.range_succ,List.map_append,List.sum_append,List.map_singleton,List.sum_singleton,pow_succ]
cases h : f m <;> simp [h] <;> omega
theorem portWord_size (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) (f : ℕ) :
(portWord α n t s f).size ≤ 2^s.2 :=
Nat.size_le.mpr (bitSum_lt _ _)
theorem layoutSlot_end {t : ℕ} {s : ℕ × ℕ} (h : s ∈ layoutSlots t) :
s.1+2^s.2 ≤ layoutHorizon t := by
rcases s with ⟨a,j⟩
obtain ⟨ha,hj,hm⟩ := layout_mem.mp h
let q := 2^(layoutHeight t-j)
have hh : layoutHorizon t = 2^j*q := by
unfold layoutHorizon q
rw [← pow_add,Nat.add_sub_of_le hj]
have he := Nat.div_add_mod a (2^j)
rw [hm,Nat.add_zero] at he
have hquot : a / 2^j < q := by
apply Nat.lt_of_mul_lt_mul_left (a := 2^j)
rw [he,← hh]
exact ha
change a+2^j ≤ layoutHorizon t
calc
a+2^j = 2^j*(a/2^j+1) := by rw [Nat.mul_add,Nat.mul_one,he]
_ ≤ 2^j*q := Nat.mul_le_mul_left _ (Nat.succ_le_of_lt hquot)
_ = layoutHorizon t := hh.symm
theorem widths_le_of_pairwise {ls : List (ℕ × ℕ)} {lo hi : ℕ}
(h : ls.Pairwise (fun s r => s.1+2^s.2 ≤ r.1))
(hLo : ∀ s ∈ ls, lo ≤ s.1) (hHi : ∀ s ∈ ls, s.1+2^s.2 ≤ hi) (hI : lo ≤ hi) :
(ls.map fun s => 2^s.2).sum ≤ hi-lo := by
induction ls generalizing lo with
| nil => simp
| cons s rest ih =>
obtain ⟨hs,hr⟩ := List.pairwise_cons.mp h
have hL := hLo s (by simp)
have hH := hHi s (by simp)
have hSum := ih hr hs (fun r hr' => hHi r (List.mem_cons_of_mem _ hr')) hH
simp only [List.map_cons,List.sum_cons]
omega
theorem liveWidths_le {α : Assignment} {n t : ℕ} (h : SlotsWellFormed α n t) :
((liveSlots α n t).map fun s => 2^s.2).sum ≤ layoutHorizon t := by
simpa using widths_le_of_pairwise (lo := 0) h.1 (fun _ _ => Nat.zero_le _)
(fun _ hs => layoutSlot_end (List.mem_filter.mp hs).1) (Nat.zero_le _)
theorem portMemory_sizes {α : Assignment} {n t : ℕ} {s : ℕ × ℕ}
{r : ObservedAccess} {i : ℕ} (hr : portMemory α n t s i = some r) :
r.action.address.size ≤ 2^s.2 ∧ r.action.value.size ≤ 2^s.2 ∧ r.old.size ≤ 2^s.2 := by
dsimp only [portMemory] at hr
split at hr
· obtain rfl := Option.some.inj hr
exact ⟨portWord_size ..,portWord_size ..,portWord_size ..⟩
· contradiction
def observationWords (rows : List ObservedAccess) : List ℕ :=
rows.flatMap fun r => [r.action.address,r.action.value,r.old]
theorem slotObservationWord_budget (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
((observationWords (slotRows α n t s)).map Nat.size).sum ≤ 9*2^s.2 := by
have hBound : ∀ r ∈ slotRows α n t s,
r.action.address.size + r.action.value.size + r.old.size ≤ 3*2^s.2 := by
intro r hr
obtain ⟨i,_,hi⟩ := List.mem_filterMap.mp hr
obtain ⟨ha,hv,ho⟩ := portMemory_sizes hi
omega
have hLen : (slotRows α n t s).length ≤ 3 := by
simpa [slotRows] using (List.length_filterMap_le (f := portMemory α n t s) (l := List.range 3))
have haux (rows : List ObservedAccess) (h : ∀ r ∈ rows,
r.action.address.size + r.action.value.size + r.old.size ≤ 3*2^s.2) :
((observationWords rows).map Nat.size).sum ≤ rows.length*(3*2^s.2) := by
induction rows with
| nil => simp [observationWords]
| cons r rest ih =>
have h₁ := h r (by simp)
have h₂ := ih (fun q hq => h q (List.mem_cons_of_mem _ hq))
change (r.action.address.size+(r.action.value.size+(r.old.size+
((observationWords rest).map Nat.size).sum))) ≤ (rest.length+1)* (3*2^s.2)
rw [Nat.add_mul,Nat.one_mul]
omega
exact (haux _ hBound).trans (by simpa [← Nat.mul_assoc] using Nat.mul_le_mul_right (3*2^s.2) hLen)
private theorem wordSum_append (xs ys : List ObservedAccess) :
((observationWords (xs++ys)).map Nat.size).sum =
((observationWords xs).map Nat.size).sum+((observationWords ys).map Nat.size).sum := by
simp [observationWords,List.flatMap_append]
theorem memoryStream_word_budget {α : Assignment} {n t : ℕ} (h : SlotsWellFormed α n t) :
((observationWords (memoryStream α n t)).map Nat.size).sum ≤ 9*layoutHorizon t := by
have he : (liveSlots α n t).flatMap (slotRows α n t) = memoryStream α n t := by
change ((layoutSlots t).filter (slotLive α n t)).flatMap (slotRows α n t) =
(layoutSlots t).flatMap (slotRows α n t)
have hi (ls : List (ℕ×ℕ)) (hL : ∀ s ∈ ls, slotLive α n t s = false → slotRows α n t s = []) :
(ls.filter (slotLive α n t)).flatMap (slotRows α n t) = ls.flatMap (slotRows α n t) := by
induction ls with
| nil => rfl
| cons s ss ih =>
have hS := ih (fun u hu => hL u (List.mem_cons_of_mem _ hu))
cases hw : slotLive α n t s
· simp [hw,hS,hL s (by simp) hw]
· simp [hw,hS]
exact hi _ (fun s hs hw => (h.2 s hs hw).2)
have hSum (ls : List (ℕ×ℕ)) :
((observationWords (ls.flatMap (slotRows α n t))).map Nat.size).sum ≤
9*(ls.map fun s => 2^s.2).sum := by
induction ls with
| nil => simp [observationWords]
| cons s ss ih =>
rw [List.flatMap_cons, wordSum_append,List.map_cons,List.sum_cons,Nat.mul_add]
exact Nat.add_le_add (slotObservationWord_budget α n t s) ih
rw [← he]
exact (hSum _).trans (Nat.mul_le_mul_left _ (liveWidths_le h))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
def compactRow (f : ℕ → ℕ) (r : ObservedAccess) : ObservedAccess :=
⟨⟨f r.action.address,f r.action.value,r.action.writes⟩,f r.old⟩
theorem compactRow_fits {b : ℕ} {rows : List ObservedAccess} {r : ObservedAccess}
{f : ℕ → ℕ} (hr : r ∈ rows) (h : ∀ x ∈ observationWords rows, (f x).size ≤ b+1) :
(f r.action.address).size ≤ b+1 ∧ (f r.action.value).size ≤ b+1 ∧ (f r.old).size ≤ b+1 := by
have hwords : ∀ x ∈ [r.action.address,r.action.value,r.old], x ∈ observationWords rows :=
fun x hx => List.mem_flatMap.mpr ⟨r,hr,hx⟩
exact ⟨h _ (hwords _ (by simp)),h _ (hwords _ (by simp)),h _ (hwords _ (by simp))⟩
theorem compactRows_labels {b : ℕ} {dict : List WordEdge} {rows : List ObservedAccess}
{f : ℕ → ℕ} (h : ∀ x ∈ observationWords rows, WordLabel b dict x (f x)) :
List.Forall₂ (ObservedLabels b dict) rows (rows.map (compactRow f)) := by
induction rows with
| nil => exact .nil
| cons r rr ih =>
refine .cons ⟨⟨h _ ?_,h _ ?_,rfl⟩,fun _ => h _ ?_⟩ (ih ?_)
· exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
· exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
· exact List.mem_flatMap.mpr ⟨r,by simp,by simp⟩
· intro x hx
obtain ⟨s,hs,hmem⟩ := List.mem_flatMap.mp hx
exact h _ (List.mem_flatMap.mpr ⟨s,List.mem_cons_of_mem _ hs,hmem⟩)
/-- On a well-formed layout, the fixed log-width parameter suffices to hold all
distinct prefixes and the total number of required rows is proportional to
the occupied payload divided by that width. -/
theorem memoryStream_labels {α : Assignment} {n t b : ℕ} (h : SlotsWellFormed α n t)
(hb : 0 < b) (hWide : 18*layoutHorizon t < 2^b) :
let rows := memoryStream α n t
∃ (dict : List WordEdge) (label : ℕ → ℕ),
WordEdge.Interned dict ∧ label 0 = 0 ∧
(∀ e ∈ dict, max e.parent e.child < 2^b) ∧
(∀ x ∈ observationWords rows,
WordLabel b dict x (label x) ∧ (label x).size ≤ b+1 ∧ (label x).size ≤ x.size+1) ∧
b*dict.length ≤ 18*layoutHorizon t := by
dsimp only
let W := observationWords (memoryStream α n t)
let M := layoutHorizon t
have hlt : 2*(9*M) < 2^b := by
rw [show 2*(9*M)=18*M by omega]
exact hWide
have hW : (W.map Nat.size).sum ≤ 9*M := memoryStream_word_budget h
obtain ⟨d,f,hGood,hZero,hNum,hId,hLabel⟩ := wordLabels_exist_bounded W hW b hb hlt
refine ⟨d,f,hGood,hZero,hId,hLabel,?_⟩
have hB := (Nat.mul_le_mul_left b hNum).trans ((labelEntries_budget hb W).trans (Nat.mul_le_mul_left 2 hW))
exact hB.trans (by dsimp [M]; omega)
/-- A compact record from a slot of width 2^j enters at most tier j+2,
including the tag and rounding to the next dyadic width. -/
theorem bounded_tier_of_slot {j a v : ℕ} (ha : a.size ≤ 2^j+1)
(hv : v.size ≤ 2^j+1) : bitTier a v ≤ j+2 := by
refine (bitTier_le ha hv).trans ?_
apply Nat.size_le.mpr
rw [Nat.pow_add]
simp only [show (2:ℕ)^2=4 by decide]
have hp : 0 < 2^j := by positivity
omega
theorem tieredRow_eligible {s : ℕ × ℕ} {r : ObservedAccess} {f : ℕ → ℕ}
(ha : (f r.action.address).size ≤ 2^s.2+1)
(hv : (f r.action.value).size ≤ 2^s.2+1)
(ho : (f r.old).size ≤ 2^s.2+1) :
∀ row ∈ tieredAccess bitTier (compactRow f r).action (compactRow f r).old,
row.addr.1 ≤ s.2+2 := by
have hDest := bounded_tier_of_slot ha hv
have hSrc := bounded_tier_of_slot ha ho
intro row hr
unfold tieredAccess at hr
dsimp only at hr
split at hr
· split at hr
· obtain rfl := List.mem_singleton.mp hr
exact hDest
· simp only [List.mem_cons,List.not_mem_nil,or_false] at hr
rcases hr with rfl|rfl
· exact hSrc
· exact hDest
· obtain rfl := List.mem_singleton.mp hr
exact hDest
theorem tieredObservations_fits {b : ℕ} {rows : List ObservedAccess} {f : ℕ → ℕ}
(h : ∀ x ∈ observationWords rows, (f x).size ≤ b+1) :
∀ r ∈ tieredObservations bitTier (rows.map (compactRow f)), TierRecordFits (b+1) r := by
intro row hr
obtain ⟨r',h',h''⟩ := List.mem_flatMap.mp hr
obtain ⟨raw,hRaw,rfl⟩ := List.mem_map.mp h'
obtain ⟨ha,hv,ho⟩ := compactRow_fits hRaw h
exact tieredAccess_fits ha hv ho row h''
/-- Exact checking of fixed chronological compact tier lanes by their batched
sort-and-snapshot certificates. Compact labels preserve even the old values
claimed at overwrites. -/
theorem observed_compactBatches_iff {b : ℕ} {dict : List WordEdge} {raw packed : List ObservedAccess}
(good : WordEdge.Interned dict) (labels : List.Forall₂ (ObservedLabels b dict) raw packed)
(fits : ∀ r ∈ tieredObservations bitTier packed, TierRecordFits (b+1) r)
(count : ℕ → ℕ) (lanes : ℕ → List (Option LocalRecord))
(proj : ∀ j < (b+1).size+1,
(lanes j).filterMap id = atTier j (tieredObservations bitTier packed))
(cap : ∀ j < (b+1).size+1, (lanes j).length ≤ 2^(2^j)*count j) :
observedMemoryValid (fun _ => 0) raw ↔
∀ j < (b+1).size+1, TierBatchCertificate (2^(2^j)) (count j) (lanes j)
(fun a => liveMemory bitTier (fun _ => 0) (j,a)) :=
(observedMemoryValid_initial_iff_labels good labels).trans
((observedMemoryValid_iff_tieredObservations bitTier (fun _ => 0) packed).trans
(compactMemoryCertificate_iff fits count lanes proj cap).symm)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
/-- The dyadic slot and local chunk number for a given tier and physical lane. -/
def chunkLaneSource (b j i : ℕ) : (ℕ × ℕ) × ℕ :=
let q := 2^(j-b)
((i/q*2^j,j),i%q)
def physicalChunkLane (b a k : ℕ) : ℕ := a/2^b+k
theorem chunkLaneSource_point {b j i : ℕ} (h : b ≤ j) :
let s := (chunkLaneSource b j i).1
let k := (chunkLaneSource b j i).2
2^b*i=s.1+2^b*k ∧ s.1 ≤ 2^b*i ∧ 2^b*i < s.1+2^s.2 := by
let q := 2^(j-b)
have hq : 0 < q := Nat.pow_pos (by decide)
have hB : 0 < 2^b := Nat.pow_pos (by decide)
have hW : 2^j=2^b*q := by
unfold q
rw [← Nat.pow_add,Nat.add_sub_of_le h]
have hEq : 2^b*i=i/q*2^j+2^b*(i%q) := by
calc
_ = 2^b*(q*(i/q)+i%q) := congrArg (2^b*·) (Nat.div_add_mod i q).symm
_ = _ := by rw [hW]; ring
have hmod := Nat.mul_lt_mul_of_pos_left (Nat.mod_lt i hq) hB
change 2^b*i=i/q*2^j+2^b*(i%q) ∧
i/q*2^j ≤ 2^b*i ∧ 2^b*i < i/q*2^j+2^j
rw [← hW] at hmod
omega
theorem chunkLaneSource_mem {t b j i : ℕ} (hb : b ≤ j) (hj : j ≤ layoutHeight t)
(hi : i < layoutHorizon t / 2^b) :
(chunkLaneSource b j i).1 ∈ layoutSlots t := by
obtain ⟨_,hlo,_⟩ := chunkLaneSource_point (i := i) hb
have hB : 0 < 2^b := Nat.pow_pos (by decide)
have hh := Nat.mul_lt_mul_of_pos_left hi hB
have he := Nat.div_add_mod (layoutHorizon t) (2^b)
have hHi : 2^b*i < layoutHorizon t := by omega
apply layout_mem.mpr
exact ⟨hlo.trans_lt hHi,hj,Nat.mul_mod_left _ _⟩
theorem chunkLaneSource_chunk_lt (b j i : ℕ) :
(chunkLaneSource b j i).2 < 2^(j-b) :=
Nat.mod_lt _ (Nat.pow_pos (by decide))
theorem chunkLaneSource_inverse {b j a k : ℕ} (hb : b ≤ j)
(ha : a % 2^j = 0) (hk : k < 2^(j-b)) :
chunkLaneSource b j (physicalChunkLane b a k) = ((a,j),k) := by
let q := 2^(j-b)
have hq : 0 < q := Nat.pow_pos (by decide)
have hB : 0 < 2^b := Nat.pow_pos (by decide)
have hW : 2^j=2^b*q := by
unfold q
rw [← Nat.pow_add,Nat.add_sub_of_le hb]
have hA : 2^j*(a/2^j)=a := by
simpa [ha] using Nat.div_add_mod a (2^j)
have hA' : a/2^b = q*(a/2^j) := by
calc
_ = (2^j*(a/2^j))/2^b := congrArg (fun n : ℕ => n/2^b) hA.symm
_ = (2^b*(q*(a/2^j)))/2^b := by rw [hW,Nat.mul_assoc]
_ = _ := Nat.mul_div_cancel_left _ hB
unfold chunkLaneSource physicalChunkLane
dsimp only
change ((((a/2^b+k)/q)*2^j,j),(a/2^b+k)%q) = _
rw [hA',Nat.mul_add_div hq,Nat.mul_add_mod,Nat.div_eq_of_lt hk,
Nat.add_zero,Nat.mod_eq_of_lt hk,Nat.mul_comm (a/2^j),hA]
theorem physicalChunkLane_lt {t b j a k : ℕ} (hS : (a,j) ∈ layoutSlots t)
(hb : b ≤ j) (hk : k < 2^(j-b)) :
physicalChunkLane b a k < layoutHorizon t/2^b := by
obtain ⟨_,hj,ha⟩ := layout_mem.mp hS
have hEq := chunkLaneSource_inverse hb ha hk
have hP := chunkLaneSource_point (i := physicalChunkLane b a k) hb
rw [hEq] at hP
have hEnd := layoutSlot_end hS
have hlt : 2^b*physicalChunkLane b a k < layoutHorizon t := hP.2.2.trans_le hEnd
have hDiv : 2^b ∣ layoutHorizon t := Nat.pow_dvd_pow _ (hb.trans hj)
have hE : 2^b*(layoutHorizon t/2^b) = layoutHorizon t := by
simpa [Nat.mod_eq_zero_of_dvd hDiv] using
Nat.div_add_mod (layoutHorizon t) (2^b)
have hPos : 0 < 2^b := Nat.pow_pos (by decide)
apply (Nat.mul_lt_mul_left hPos).mp
simpa only [hE] using hlt
/-- Two occupied slots containing the same time point must be the same slot. -/
theorem liveSlot_unique_point {α : Assignment} {n t x : ℕ} (h : SlotsWellFormed α n t)
{s r : ℕ × ℕ} (hs : s ∈ liveSlots α n t) (hr : r ∈ liveSlots α n t)
(hsx : s.1 ≤ x ∧ x < s.1+2^s.2) (hrx : r.1 ≤ x ∧ x < r.1+2^r.2) : s=r := by
obtain ⟨i,hi,his⟩ := List.mem_iff_getElem.mp hs
obtain ⟨j,hj,hjr⟩ := List.mem_iff_getElem.mp hr
have hp := List.pairwise_iff_getElem.mp h.1
rcases lt_trichotomy i j with hlt | he | hgt
· have he := hp i j hi hj hlt
rw [his,hjr] at he
omega
· subst j
exact his.symm.trans hjr
· have he := hp j i hj hi hgt
rw [his,hjr] at he
omega
/-- Candidate tiers can share every physical lane; at most one contributes
from the occupied schedule for any given lane. -/
theorem chunkLaneSource_unique {α : Assignment} {n t b i j k : ℕ}
(h : SlotsWellFormed α n t) (hj : b ≤ j) (hk : b ≤ k)
(hJ : (chunkLaneSource b j i).1 ∈ liveSlots α n t)
(hK : (chunkLaneSource b k i).1 ∈ liveSlots α n t) : j=k := by
have hPJ := (chunkLaneSource_point (i := i) hj).2
have hPK := (chunkLaneSource_point (i := i) hk).2
exact congrArg Prod.snd (liveSlot_unique_point h hJ hK hPJ hPK)
/-- One candidate per physical lane per eligible tier, independent of the trace. -/
def chunkPoolSources (t b : ℕ) : List ((ℕ × ℕ) × ℕ) :=
((List.range (layoutHeight t+1-b)).map (fun j => b+j)).flatMap (fun j =>
(List.range (layoutHorizon t/2^b)).map (chunkLaneSource b j))
theorem chunkPoolSources_length (t b : ℕ) :
(chunkPoolSources t b).length = (layoutHeight t+1-b)*(layoutHorizon t/2^b) := by
have h (ls : List ℕ) :
(ls.flatMap (fun j =>
(List.range (layoutHorizon t/2^b)).map (chunkLaneSource b j))).length =
ls.length*(layoutHorizon t/2^b) := by
induction ls with
| nil => simp
| cons i is ih =>
simp [ih,Nat.succ_mul,Nat.add_comm]
rw [chunkPoolSources,h]
simp
theorem chunkPoolSources_wire_budget (t b width factor : ℕ) (hw : width ≤ factor*2^b) :
(chunkPoolSources t b).length*width ≤ factor*(layoutHeight t+1)*layoutHorizon t := by
have hq := Nat.div_mul_le_self (layoutHorizon t) (2^b)
have hh := Nat.sub_le (layoutHeight t+1) b
rw [chunkPoolSources_length]
calc
_ ≤ ((layoutHeight t+1-b)*(layoutHorizon t/2^b))*(factor*2^b) :=
Nat.mul_le_mul_left _ hw
_ = factor*(layoutHeight t+1-b)*((layoutHorizon t/2^b)*2^b) := by ring
_ ≤ _ := Nat.mul_le_mul (Nat.mul_le_mul_left _ hh) hq
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
/-- Reserve room for the short/long tag and tier rounding by permitting a row
to move up two tiers. Narrowen its lane spacing accordingly. -/
def tierLane (j a : ℕ) : ℕ := physicalChunkLane (j-2) a 0
theorem tierLane_lt {t j a k : ℕ} (hs : (a,k) ∈ layoutSlots t) (hj : j ≤ k+2) :
tierLane j a < layoutHorizon t / 2^(j-2) := by
exact physicalChunkLane_lt hs (by omega) (Nat.pow_pos (by decide))
theorem tierLane_occupied_unique {a c k l j n t : ℕ} {α : Assignment}
(h : SlotsWellFormed α n t)
(hs : (a,k) ∈ liveSlots α n t) (hr : (c,l) ∈ liveSlots α n t)
(hk : j ≤ k+2) (hl : j ≤ l+2)
(hEq : tierLane j a = tierLane j c) :
(a,k)=(c,l) := by
have hm {x y : ℕ} (hxy : (x,y) ∈ liveSlots α n t) :
x % 2^y = 0 := (layout_mem.mp (List.mem_filter.mp hxy).1).2.2
have hbk : j-2 ≤ k := by omega
have hbl : j-2 ≤ l := by omega
have hKa : chunkLaneSource (j-2) k (tierLane j a) = ((a,k),0) :=
chunkLaneSource_inverse hbk (hm hs) (Nat.pow_pos (by decide))
have hLc : chunkLaneSource (j-2) l (tierLane j c) = ((c,l),0) :=
chunkLaneSource_inverse hbl (hm hr) (Nat.pow_pos (by decide))
have hP := chunkLaneSource_point (i := tierLane j a) hbk
have hQ := chunkLaneSource_point (i := tierLane j c) hbl
rw [hKa] at hP
rw [hLc,← hEq] at hQ
exact liveSlot_unique_point h hs hr hP.2 hQ.2
private def slotBitLanes (t : ℕ) : List ((ℕ × ℕ) × ℕ) :=
(layoutSlots t).flatMap fun s => (List.range (2^s.2)).map (s,·)
private theorem slotBitLanes_nodup (t : ℕ) : (slotBitLanes t).Nodup := by
unfold slotBitLanes
rw [List.nodup_flatMap]
constructor
· intro s _
exact List.nodup_range.map (fun _ _ he => (Prod.mk.inj he).2)
· apply (layout_nodup t).imp
intro s r hsr
apply List.disjoint_left.mpr
intro q hq hQ
obtain ⟨u,_,rfl⟩ := List.mem_map.mp hq
obtain ⟨v,_,hv⟩ := List.mem_map.mp hQ
exact hsr (Prod.mk.inj hv).1.symm
private theorem slotBitLanes_subset (t : ℕ) : slotBitLanes t ⊆ chunkPoolSources t 0 := by
intro x hx
obtain ⟨s,hs,hX⟩ := List.mem_flatMap.mp hx
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hX
rcases s with ⟨a,k⟩
obtain ⟨ha,hk,hAlign⟩ := layout_mem.mp hs
simp only [List.mem_range] at hj
have hk' : j < 2^(k-0) := by simpa using hj
have hR := physicalChunkLane_lt (b := 0) hs (Nat.zero_le _) hk'
unfold chunkPoolSources
apply List.mem_flatMap.mpr
refine ⟨k,?_,?_⟩
· simp
omega
· apply List.mem_map.mpr
exact ⟨physicalChunkLane 0 a j,List.mem_range.mpr hR,
chunkLaneSource_inverse (Nat.zero_le _) hAlign hk'⟩
theorem layoutSlots_totalWidth_le (t : ℕ) :
((layoutSlots t).map fun s => 2^s.2).sum ≤ (layoutHeight t+1)*layoutHorizon t := by
have h := (slotBitLanes_nodup t).length_le_of_subset (slotBitLanes_subset t)
simpa [slotBitLanes,List.length_flatMap,chunkPoolSources_length] using h
/-- A potential record from a width 2^k slot can have a destination tier j
among 0 through k+2. Generate exactly these candidates. -/
def tierPoolCandidates (t : ℕ) : List ((ℕ × ℕ) × ℕ) :=
(layoutSlots t).flatMap fun s => (List.range (s.2+3)).map (s,·)
private theorem rangeWidthSum (n : ℕ) :
((List.range n).map (fun k => (2:ℕ)^k)).sum+1 = 2^n := by
induction n with
| zero => decide
| succ n ih =>
rw [List.range_succ,List.map_append,List.sum_append,List.map_singleton,List.sum_singleton,Nat.pow_succ]
omega
theorem tierPoolCandidates_totalWidth (t : ℕ) :
((tierPoolCandidates t).map fun x => 2^x.2).sum ≤
8*(layoutHeight t+1)*layoutHorizon t := by
unfold tierPoolCandidates
rw [List.map_flatMap]
have split {α : Type} (f : α → List ℕ) (xs : List α) :
(xs.flatMap f).sum = (xs.map fun x => (f x).sum).sum := by
induction xs with
| nil => rfl
| cons x xs ih => simp [List.sum_append,ih]
rw [split]
have h : ((layoutSlots t).map
(fun s => (((List.range (s.2+3)).map (s,·)).map (fun x => (2:ℕ)^x.2)).sum)).sum ≤
((layoutSlots t).map fun s => 8*2^s.2).sum := by
apply List.sum_le_sum
intro s _
simp only [List.map_map,Function.comp_def]
have hh := rangeWidthSum (s.2+3)
rw [Nat.pow_add] at hh
omega
rw [List.sum_map_mul_left] at h
exact h.trans (by
rw [Nat.mul_assoc]
exact Nat.mul_le_mul_left _ (layoutSlots_totalWidth_le t))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- Require each cut list to contain exactly one true flag. The Boolean prefix
accumulators use one gate and one clause per lane, without testing pairs of lanes. -/
def cutMarkerGates (markers : List ℕ) (acc : ℕ → ℕ) : List Gate :=
.pin (acc 0) false :: .pin (acc markers.length) true ::
(markers.zipIdx.flatMap fun p =>
[.disj (acc (p.2+1)) (acc p.2) p.1,
.assert [.Neg (acc p.2),.Neg p.1]])
theorem cutMarkerGates_length (markers : List ℕ) (acc : ℕ → ℕ) :
(cutMarkerGates markers acc).length = 2+2*markers.length := by
unfold cutMarkerGates
simp only [List.length_cons]
have H {α : Type} (xs : List α) (f : α → List Gate) (h : ∀ x, (f x).length = 2) :
(xs.flatMap f).length = 2*xs.length := by
induction xs with
| nil => rfl
| cons y ys ih => simp [h,ih,Nat.mul_succ] <;> omega
rw [H _ _ (fun _ => rfl),List.length_zipIdx]
omega
private theorem marker_mem_zipIdx (markers : List ℕ) (i : Fin markers.length) :
(markers[i.val],i.val) ∈ markers.zipIdx := by
have hh := List.getElem_mem (l := markers.zipIdx) (n := i.val) (by simpa using i.isLt)
simpa using hh
theorem cutMarkerGates_local (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment) :
(∀ g ∈ cutMarkerGates markers acc, g.Holds α) ↔
α (acc 0) = false ∧ α (acc markers.length) = true ∧
∀ i : Fin markers.length,
α (acc (i.val+1)) = (α (acc i.val) || α markers[i.val]) ∧
¬ (α (acc i.val) = true ∧ α markers[i.val] = true) := by
constructor
· intro h
refine ⟨h (.pin (acc 0) false) (by simp [cutMarkerGates]),
h (.pin (acc markers.length) true) (by simp [cutMarkerGates]),?_⟩
intro i
have hmem := marker_mem_zipIdx markers i
have g1 : Gate.disj (acc (i.val+1)) (acc i.val) markers[i.val] ∈
cutMarkerGates markers acc := by
simp only [cutMarkerGates,List.mem_cons]
exact Or.inr (Or.inr (List.mem_flatMap.mpr ⟨_,hmem,by simp⟩))
have g2 : Gate.assert [.Neg (acc i.val),.Neg markers[i.val]] ∈
cutMarkerGates markers acc := by
simp only [cutMarkerGates,List.mem_cons]
exact Or.inr (Or.inr (List.mem_flatMap.mpr ⟨_,hmem,by simp⟩))
have h2 := h _ g2
refine ⟨h _ g1,?_⟩
cases hA : α (acc i.val) <;> cases hB : α markers[i.val] <;>
simp_all [Gate.Holds,satisfiesClause,satisfiesLiteral]
· rintro ⟨h0,h1,h⟩ g hg
simp only [cutMarkerGates,List.mem_cons] at hg
rcases hg with rfl | rfl | hg
· exact h0
· exact h1
· obtain ⟨⟨r,j⟩,hR,hM⟩ := List.mem_flatMap.mp hg
obtain ⟨i,hi,hI⟩ := List.mem_iff_getElem.mp hR
have hi' : i < markers.length := by simpa using hi
have he : (markers[i]'hi',i)=(r,j) := by simpa using hI
obtain ⟨he₁,he₂⟩ := Prod.mk.inj he
subst r
subst j
have hj := h ⟨i,hi'⟩
rcases List.mem_cons.mp hM with rfl | hM
· exact hj.1
· have hLast := List.mem_singleton.mp hM
subst g
have hN := hj.2
cases hA : α (acc i) <;> cases hB : α (markers[i]'hi') <;>
simp_all [Gate.Holds,satisfiesClause,satisfiesLiteral]
/-- Exact meaning of the enabled markers without mentioning their prefix wires. -/
def OneCut (α : Assignment) (markers : List ℕ) : Prop :=
∃ j : Fin markers.length, ∀ i : Fin markers.length,
α markers[i.val] = decide (i=j)
private theorem prefixEq (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
(h0 : α (acc 0)=false)
(h : ∀ i : Fin markers.length,
α (acc (i.val+1)) = (α (acc i.val) || α markers[i.val]))
(m : ℕ) (hm : m ≤ markers.length) :
α (acc m)=true ↔ ∃ k : Fin markers.length, k.val < m ∧ α markers[k.val]=true := by
induction m with
| zero => simp [h0]
| succ m ih =>
let i : Fin markers.length := ⟨m,by omega⟩
have he := h i
change α (acc (m+1)) = (α (acc m) || α markers[i.val]) at he
rw [he,Bool.or_eq_true,ih (by omega)]
constructor
· rintro (⟨k,hk,hK⟩ | hI)
· exact ⟨k,by omega,hK⟩
· exact ⟨i,by simp [i],hI⟩
· rintro ⟨k,hk,hK⟩
by_cases e : k.val=m
· have hh : k=i := Fin.ext e
exact Or.inr (hh ▸ hK)
· exact Or.inl ⟨k,by omega,hK⟩
theorem cutMarkerGates_sound (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ cutMarkerGates markers acc, g.Holds α) : OneCut α markers := by
obtain ⟨h0,hN,h⟩ := (cutMarkerGates_local markers acc α).mp h
have hEq := prefixEq markers acc α h0 (fun i => (h i).1)
obtain ⟨j,hj,hJT⟩ := (hEq _ le_rfl).mp hN
refine ⟨j,?_⟩
intro i
by_cases e : i=j
· subst i
simpa using hJT
· have hI : α markers[i.val] ≠ true := by
intro hTrue
have hi' : i.val ≠ j.val := fun hEq => e (Fin.ext hEq)
rcases Nat.lt_or_gt_of_ne hi' with hLt | hGt
· exact (h j).2 ⟨(hEq j.val j.isLt.le).mpr ⟨i,hLt,hTrue⟩,hJT⟩
· exact (h i).2 ⟨(hEq i.val i.isLt.le).mpr ⟨j,hGt,hJT⟩,hTrue⟩
cases he : α markers[i.val] <;> simp_all
def cutPrefix (α : Assignment) (markers : List ℕ) (i : ℕ) : Bool :=
(markers.take i).any α
theorem cutPrefix_true (α : Assignment) (markers : List ℕ) (i : ℕ) :
cutPrefix α markers i = true ↔
∃ k : Fin markers.length, k.val < i ∧ α markers[k.val]=true := by
unfold cutPrefix
rw [List.any_eq_true]
constructor
· rintro ⟨v,hv,hT⟩
obtain ⟨j,hj,rfl⟩ := List.mem_iff_getElem.mp hv
have hi : j < i := by rw [List.length_take] at hj; omega
have hLength : j < markers.length := by rw [List.length_take] at hj; omega
exact ⟨⟨j,hLength⟩,hi, by simpa using hT⟩
· rintro ⟨j,hi,hT⟩
have hj : j.val < (markers.take i).length := by
rw [List.length_take]; exact lt_min hi j.isLt
exact ⟨(markers.take i)[j.val]'hj,List.getElem_mem hj,by simpa using hT⟩
theorem cutMarkerGates_complete (markers : List ℕ) (acc : ℕ → ℕ) (α : Assignment)
(h : OneCut α markers)
(hAcc : ∀ i ≤ markers.length, α (acc i)=cutPrefix α markers i) :
∀ g ∈ cutMarkerGates markers acc, g.Holds α := by
obtain ⟨j,h⟩ := h
apply (cutMarkerGates_local markers acc α).mpr
refine ⟨(hAcc 0 (by omega)).trans rfl,?_,?_⟩
· rw [hAcc _ le_rfl,cutPrefix_true]
exact ⟨j,j.isLt, by simp [h j]⟩
· intro i
refine ⟨?_,?_⟩
· rw [hAcc (i.val+1) (by omega),hAcc i.val i.isLt.le]
unfold cutPrefix
rw [List.take_succ_eq_append_getElem i.isLt,List.any_append]
simp
· rintro ⟨hPrev,hTrue⟩
rw [hAcc i.val i.isLt.le,cutPrefix_true] at hPrev
obtain ⟨k,hlt,hK⟩ := hPrev
have e : k=j := of_decide_eq_true ((h k).symm.trans hK)
have f : i=j := of_decide_eq_true ((h i).symm.trans hTrue)
rw [e,f] at hlt
exact (Nat.lt_irrefl _ hlt)
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- A candidate lane consists of an enable bit and a fixed-width payload. -/
abbrev GatherCandidate (w : ℕ) := ℕ × (Fin w → ℕ)
def guardEqual (guard src dest : ℕ) : List Gate :=
[.assert [.Neg guard,.Neg src,.Pos dest],
.assert [.Neg guard,.Pos src,.Neg dest]]
theorem guardEqual_exact (a : Assignment) (guard src dest : ℕ) :
(∀ g ∈ guardEqual guard src dest, g.Holds a) ↔
(a guard=true → a src=a dest) := by
cases hc : a guard <;> cases hs : a src <;> cases hd : a dest <;>
simp [guardEqual,Gate.Holds,satisfiesClause,satisfiesLiteral,hc,hs,hd]
def gatherEntry {w : ℕ} (acc : ℕ → ℕ) (out : Fin w → ℕ)
(j : ℕ) (candidate : GatherCandidate w) : List Gate :=
.disj (acc (j+1)) (acc j) candidate.1 ::
.assert [.Neg (acc j), .Neg candidate.1] ::
(List.finRange w).flatMap (fun i => guardEqual candidate.1 (candidate.2 i) (out i))
def gatherGates {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (candidates : List (GatherCandidate w)) : List Gate :=
.pin (acc 0) false :: .copy active (acc candidates.length) ::
(List.finRange candidates.length).flatMap (fun j => gatherEntry acc out j.val candidates[j.val])
private theorem gatherEntry_exact (a : Assignment) {w : ℕ} (acc : ℕ → ℕ)
(out : Fin w → ℕ) (j : ℕ) (c : GatherCandidate w) :
(∀ g ∈ gatherEntry acc out j c, g.Holds a) ↔
a (acc (j+1)) = (a (acc j) || a c.1) ∧
¬(a (acc j)=true ∧ a c.1=true) ∧
(a c.1=true → ∀ i, a (c.2 i) = a (out i)) := by
have hn : Gate.Holds a (.assert [.Neg (acc j),.Neg c.1]) ↔ ¬(a (acc j)=true ∧ a c.1=true) := by
cases hP : a (acc j) <;> cases hC : a c.1 <;>
simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hP,hC]
constructor
· intro h
refine ⟨h (.disj (acc (j+1)) (acc j) c.1) (by simp [gatherEntry]),hn.mp (h _ (by simp [gatherEntry])),?_⟩
intro hg i
apply (guardEqual_exact a c.1 (c.2 i) (out i)).mp _ hg
intro g hG
exact h g (List.mem_cons_of_mem _ (List.mem_cons_of_mem _
(List.mem_flatMap.mpr ⟨i,List.mem_finRange _,hG⟩)))
· rintro ⟨hOr,hA,hEq⟩ g hg
simp only [gatherEntry,List.mem_cons] at hg
rcases hg with rfl | rfl | hg
· exact hOr
· exact hn.mpr hA
· obtain ⟨i,_,hG⟩ := List.mem_flatMap.mp hg
exact (guardEqual_exact _ _ _ _).mpr (fun h => hEq h i) _ hG
theorem gatherGates_local (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (candidates : List (GatherCandidate w)) :
(∀ g ∈ gatherGates active acc out candidates, g.Holds a) ↔
a (acc 0)=false ∧ a active=a (acc candidates.length) ∧
∀ j : Fin candidates.length,
a (acc (j.val+1)) = (a (acc j.val) || a candidates[j.val].1) ∧
¬(a (acc j.val)=true ∧ a candidates[j.val].1=true) ∧
(a candidates[j.val].1=true → ∀ i, a (candidates[j.val].2 i) = a (out i)) := by
constructor
· intro h
refine ⟨h (.pin (acc 0) false) (by simp [gatherGates]),
h (.copy active (acc candidates.length)) (by simp [gatherGates]),?_⟩
intro j
apply (gatherEntry_exact a acc out j.val candidates[j.val]).mp
intro g hG
exact h g (List.mem_cons_of_mem _ (List.mem_cons_of_mem _
(List.mem_flatMap.mpr ⟨j,List.mem_finRange _,hG⟩)))
· rintro ⟨hPin,hCopy,hLocal⟩ g hg
simp only [gatherGates,List.mem_cons] at hg
rcases hg with rfl | rfl | hg
· exact hPin
· exact hCopy
· obtain ⟨j,_,hG⟩ := List.mem_flatMap.mp hg
exact (gatherEntry_exact a acc out j.val candidates[j.val]).mpr (hLocal j) g hG
/-- The prefix oracle can see exactly whether some prior candidate is enabled. -/
def GatherSeen (a : Assignment) {w : ℕ} (cs : List (GatherCandidate w)) (j : ℕ) : Prop :=
∃ k : Fin cs.length, k.val < j ∧ a cs[k.val].1=true
private theorem GatherSeen_succ (a : Assignment) {w : ℕ} (cs : List (GatherCandidate w))
(i : Fin cs.length) :
GatherSeen a cs (i.val+1) ↔ GatherSeen a cs i.val ∨ a cs[i.val].1=true := by
constructor
· rintro ⟨k,hk,hK⟩
by_cases h : k=i
· subst k
exact Or.inr hK
· have hh : k.val ≠ i.val := fun he => h (Fin.ext he)
exact Or.inl ⟨k,by omega,hK⟩
· rintro (⟨k,hK,hQ⟩ | hQ)
· exact ⟨k,by omega,hQ⟩
· exact ⟨i,by omega,hQ⟩
private theorem gather_prefix_sound (a : Assignment) {w : ℕ} (acc : ℕ → ℕ)
(cs : List (GatherCandidate w)) (h₀ : a (acc 0)=false)
(hS : ∀ j : Fin cs.length,
a (acc (j.val+1)) = (a (acc j.val) || a cs[j.val].1)) :
∀ j ≤ cs.length, a (acc j)=true ↔ GatherSeen a cs j := by
intro j
induction j with
| zero => simp [h₀,GatherSeen]
| succ j ih =>
intro hj
let i : Fin cs.length := ⟨j,by omega⟩
change a (acc (i.val+1))=true ↔ GatherSeen a cs (i.val+1)
rw [hS i,GatherSeen_succ,Bool.or_eq_true,ih (by omega)]
theorem gatherGates_sound (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (cs : List (GatherCandidate w))
(h : ∀ g ∈ gatherGates active acc out cs, g.Holds a) :
(a active=true ↔ ∃ i : Fin cs.length, a cs[i.val].1=true) ∧
(∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j) ∧
(∀ i : Fin cs.length, a cs[i.val].1=true → ∀ k, a (cs[i.val].2 k)=a (out k)) := by
obtain ⟨h₀,hLast,hStep⟩ := (gatherGates_local a active acc out cs).mp h
have hSeen := gather_prefix_sound a acc cs h₀ (fun i => (hStep i).1)
refine ⟨?_,?_,fun i => (hStep i).2.2⟩
· rw [hLast,hSeen _ le_rfl]
exact ⟨fun ⟨i,_,hI⟩ => ⟨i,hI⟩,fun ⟨i,hI⟩ => ⟨i,i.isLt,hI⟩⟩
· intro i j hI hJ
rcases lt_trichotomy i.val j.val with hlt | he | hgt
· exact False.elim ((hStep j).2.1 ⟨(hSeen _ j.isLt.le).2 ⟨i,hlt,hI⟩,hJ⟩)
· exact Fin.ext he
· exact False.elim ((hStep i).2.1 ⟨(hSeen _ i.isLt.le).2 ⟨j,hgt,hJ⟩,hI⟩)
theorem gatherGates_complete (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (cs : List (GatherCandidate w))
(hA : a active=true ↔ ∃ i : Fin cs.length, a cs[i.val].1=true)
(hU : ∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j)
(hV : ∀ i : Fin cs.length, a cs[i.val].1=true → ∀ k, a (cs[i.val].2 k)=a (out k))
(hP : ∀ j ≤ cs.length, a (acc j)=true ↔ GatherSeen a cs j) :
∀ g ∈ gatherGates active acc out cs, g.Holds a := by
refine (gatherGates_local a active acc out cs).mpr ⟨?_,?_,?_⟩
· have h := hP 0 (by omega)
simp [GatherSeen] at h
cases he : a (acc 0) <;> simp_all
· apply Bool.eq_iff_iff.mpr
rw [hA,hP _ le_rfl]
exact ⟨fun ⟨i,hI⟩ => ⟨i,i.isLt,hI⟩,fun ⟨i,_,hI⟩ => ⟨i,hI⟩⟩
· intro i
refine ⟨?_,?_,hV i⟩
· apply Bool.eq_iff_iff.mpr
rw [Bool.or_eq_true,hP _ (by omega),hP _ i.isLt.le]
exact GatherSeen_succ a cs i
· rintro ⟨hI,hJ⟩
obtain ⟨j,hJlt,hE⟩ := (hP _ i.isLt.le).mp hI
exact (Nat.ne_of_lt hJlt) (congrArg Fin.val (hU j i hE hJ))
private theorem constantFlatMapLength {α β : Type} (f : α → List β) (k : ℕ)
(hf : ∀ x, (f x).length=k) (l : List α) :
(l.flatMap f).length = k*l.length := by
induction l with
| nil => simp
| cons x xs ih => simp [hf,ih,Nat.mul_succ,Nat.add_comm]
theorem gatherGates_length {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (cs : List (GatherCandidate w)) :
(gatherGates active acc out cs).length = 2+(2+2*w)*cs.length := by
have hEntry (j : Fin cs.length) : (gatherEntry acc out j.val cs[j.val]).length=2+2*w := by
simp only [gatherEntry,List.length_cons]
rw [constantFlatMapLength _ 2 (fun _ => rfl),List.length_finRange]
omega
simp only [gatherGates,List.length_cons]
rw [constantFlatMapLength _ (2+2*w) hEntry,List.length_finRange]
omega
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Toggle the second channel of a pair exactly when its control is true. -/
def pairSwitch {A : Type} (controls : A → Bool) : A × Bool ≃ A × Bool where
toFun p := (p.1, if controls p.1 then !p.2 else p.2)
invFun p := (p.1, if controls p.1 then !p.2 else p.2)
left_inv := by rintro ⟨a,b⟩; by_cases h : controls a <;> simp [h]
right_inv := by rintro ⟨a,b⟩; by_cases h : controls a <;> simp [h]
private theorem pairSwitch_fst {A : Type} (c : A → Bool) (q : A × Bool) :
(pairSwitch c q).1 = q.1 := rfl
private theorem route_one_side {A : Type} [Finite A] (σ : A × Bool ≃ A × Bool) :
∃ (e : A ≃ A) (left right : A → Bool),
∀ a, σ (a,left a) = (e a,right (e a)) := by
classical
let N (a : A) : Finset A := {(σ (a,false)).1, (σ (a,true)).1}
have hall (s : Finset A) : s.card ≤ (s.biUnion N).card := by
have hs : (s ×ˢ (Finset.univ : Finset Bool)).map σ.toEmbedding ⊆
(s.biUnion N) ×ˢ Finset.univ := by
intro x hx
obtain ⟨⟨a,b⟩,hi,rfl⟩ := Finset.mem_map.mp hx
refine Finset.mem_product.mpr ⟨?_,Finset.mem_univ _⟩
apply Finset.mem_biUnion.mpr
exact ⟨a,(Finset.mem_product.mp hi).1,by cases b <;> simp [N]⟩
have h := Finset.card_le_card hs
simp only [Finset.card_map,Finset.card_product,Finset.card_univ,Fintype.card_bool] at h
omega
obtain ⟨f,hf,hm⟩ := (Finset.all_card_le_biUnion_card_iff_existsInjective' N).mp hall
let e := Equiv.ofBijective f ⟨hf, Finite.surjective_of_injective hf⟩
have hex (a : A) : ∃ b : Bool, (σ (a,b)).1 = e a := by
have h := hm a
change f a ∈ N a at h
simp only [N, Finset.mem_insert, Finset.mem_singleton] at h
rcases h with h | h
· exact ⟨false,h.symm⟩
· exact ⟨true,h.symm⟩
choose left hleft using hex
let right (a : A) := (σ (e.symm a,left (e.symm a))).2
refine ⟨e,left,right,?_⟩
intro a
exact Prod.ext (hleft a) (by simp [right])
/-- Any permutation of paired wires splits into one column of pair switches, then
independent permutations of the two channels, then one more column of switches. -/
theorem split_pair_permutation {A : Type} [Finite A] (σ : A × Bool ≃ A × Bool) :
∃ (entry exit : A → Bool) (middle : Bool → A ≃ A),
∀ p, let x := pairSwitch entry p
σ p = pairSwitch exit (middle x.2 x.1, x.2) := by
classical
obtain ⟨e,l,r,hr⟩ := route_one_side σ
let σ' := ((pairSwitch l).trans σ).trans (pairSwitch r).symm
have hzero (a : A) : σ' (a,false) = (e a,false) := by
change (pairSwitch r).symm (σ (pairSwitch l (a,false))) = _
have h : pairSwitch l (a,false) = (a,l a) := by cases h : l a <;> simp [pairSwitch,h]
rw [h,hr]
cases h : r (e a) <;> simp [pairSwitch,h]
have hone (a : A) : (σ' (a,true)).2 = true := by
cases h : (σ' (a,true)).2
· have h' : σ' (a,true) = σ' (e.symm (σ' (a,true)).1,false) := by
rw [hzero,e.apply_symm_apply]
exact Prod.ext rfl h
have h'' := congrArg Prod.snd (σ'.injective h')
exact Bool.noConfusion h''
· rfl
let f (a : A) := (σ' (a,true)).1
have hinj : Function.Injective f := by
intro x y hxy
have h : σ' (x,true) = σ' (y,true) := Prod.ext hxy ((hone x).trans (hone y).symm)
exact congrArg Prod.fst (σ'.injective h)
let e₁ := Equiv.ofBijective f ⟨hinj,Finite.surjective_of_injective hinj⟩
let middle (b : Bool) := if b then e₁ else e
have hs (p : A × Bool) : σ' p = (middle p.2 p.1,p.2) := by
obtain ⟨a,b⟩ := p
cases b
· exact hzero a
· exact Prod.ext rfl (hone a)
refine ⟨l,r,middle,?_⟩
intro p
let x := pairSwitch l p
have hx : pairSwitch l x = p := (pairSwitch l).symm_apply_apply p
have f := hs x
change (pairSwitch r).symm (σ (pairSwitch l x)) = _ at f
rw [hx] at f
exact (Equiv.symm_apply_eq _).mp f
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Wires are numbered recursively in pairs. -/
def Wire : ℕ → Type
| 0 => Unit
| h+1 => Wire h × Bool
instance (h : ℕ) : Fintype (Wire h) := by
induction h with
| zero => exact inferInstanceAs (Fintype Unit)
| succ h inst =>
letI := inst
exact inferInstanceAs (Fintype (Wire h × Bool))
theorem wire_card (h : ℕ) : Fintype.card (Wire h) = 2^h := by
induction h with
| zero => rfl
| succ h ih =>
change Fintype.card (Wire h × Bool) = _
rw [Fintype.card_prod, Fintype.card_bool, ih, pow_succ]
/-- Switch settings for a recursive permutation network. Each nontrivial level adds
one entry column and one exit column, and recursively routes both channels. -/
def Setting : ℕ → Type
| 0 => Unit
| h+1 => (Wire h → Bool) × (Bool → Setting h) × (Wire h → Bool)
/-- Every switch setting induces a permutation of wires. -/
def routing : (h : ℕ) → Setting h → (Wire h ≃ Wire h)
| 0, _ => Equiv.refl _
| h+1, (entry,mid,exit) =>
let interior : Wire h × Bool ≃ Wire h × Bool :=
{ toFun := fun q => (routing h (mid q.2) q.1,q.2)
invFun := fun q => ((routing h (mid q.2)).symm q.1,q.2)
left_inv := by rintro ⟨x,b⟩; simp
right_inv := by rintro ⟨x,b⟩; simp }
((pairSwitch entry).trans interior).trans (pairSwitch exit)
theorem routing_succ {h : ℕ} (entry : Wire h → Bool) (mid : Bool → Setting h)
(exit : Wire h → Bool) (x : Wire h × Bool) :
routing (h+1) (entry,mid,exit) x =
pairSwitch exit (routing h (mid (pairSwitch entry x).2) (pairSwitch entry x).1,
(pairSwitch entry x).2) := rfl
/-- A network of height h routes every permutation of its two-to-the-h wires. -/
theorem routing_universal (h : ℕ) (σ : Wire h ≃ Wire h) :
∃ setting : Setting h, routing h setting = σ := by
induction h with
| zero =>
refine ⟨(),Equiv.ext fun _ => ?_⟩
apply Subsingleton.elim (α := Unit)
| succ h ih =>
obtain ⟨entry,exit,mid,hσ⟩ := split_pair_permutation (A := Wire h) σ
choose c hc using fun b => ih (mid b)
refine ⟨(entry,c,exit), Equiv.ext fun q => ?_⟩
let q' : Wire h × Bool := q
let z := pairSwitch entry q'
have h₁ := routing_succ entry c exit q'
have h₂ : pairSwitch exit (routing h (c z.2) z.1,z.2) = σ q' := by
rw [hc]
exact (hσ q').symm
exact h₁.trans h₂
/-- The network has two columns of half as many switches as there are wires and
two copies of the preceding network. -/
def switchCount : ℕ → ℕ
| 0 => 0
| h+1 => 2^h+2*switchCount h+2^h
theorem switchCount_exact (h : ℕ) : switchCount h = h*2^h := by
induction h with
| zero => rfl
| succ h ih => rw [switchCount,ih,pow_succ]; ring
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
private def wires : (h : ℕ) → List (Wire h)
| 0 => [()]
| h+1 => (wires h).flatMap fun x => [(x,false),(x,true)]
private theorem wires_length (h : ℕ) : (wires h).length = 2^h := by
induction h with
| zero => rfl
| succ h ih =>
change ((wires h).flatMap (fun x => [(x,false),(x,true)])).length = 2^(h+1)
rw [List.length_flatMap]
change ((wires h).map (Function.const _ 2)).sum = _
rw [List.map_const,List.sum_replicate,ih,pow_succ]
exact nsmul_eq_mul _ _
private theorem wires_mem (h : ℕ) (x : Wire h) : x ∈ wires h := by
induction h with
| zero =>
change x ∈ ([()] : List Unit)
cases x
exact List.mem_cons_self
| succ h ih =>
let y : Wire h × Bool := x
change y ∈ (wires h).flatMap fun a => [(a,false),(a,true)]
apply List.mem_flatMap.mpr
refine ⟨y.1,ih _,?_⟩
rcases y with ⟨a,b⟩
cases b <;> simp
/-- Labels for all internal variables. Two endpoint arrays and the switches for the
outer columns are local to a node. The remaining variables belong to the two child networks. -/
def RouteAux (B : Type) : ℕ → Type
| 0 => Empty
| h+1 => (Bool × Wire h) ⊕ ((Bool × (Wire (h+1) × B)) ⊕ (Bool × RouteAux B h))
inductive RouteVar (h : ℕ) (B : Type) where
| input (wire : Wire h) (bit : B)
| output (wire : Wire h) (bit : B)
| aux (name : RouteAux B h)
def RouteVar.control {h : ℕ} {B : Type} (side : Bool) (wire : Wire h) : RouteVar (h+1) B :=
.aux (.inl (side,wire))
def RouteVar.internal {h : ℕ} {B : Type} (side : Bool) (wire : Wire (h+1)) (bit : B) :
RouteVar (h+1) B := .aux (.inr (.inl (side,wire,bit)))
def RouteVar.embed {h : ℕ} {B : Type} (channel : Bool) : RouteVar h B → RouteVar (h+1) B
| .input wire bit => .internal false (wire,channel) bit
| .output wire bit => .internal true (wire,channel) bit
| .aux name => .aux (.inr (.inr (channel,name)))
/-- Copy and conditional move are the only elementary gates needed for routing. -/
inductive RouteGate (V : Type) where
| copy (out src : V)
| mux (out selector crossed straight : V)
def RouteGate.rename {V W : Type} (f : V → W) : RouteGate V → RouteGate W
| .copy out src => .copy (f out) (f src)
| .mux out s yes no => .mux (f out) (f s) (f yes) (f no)
def RouteGate.Valid {V : Type} (val : V → Bool) : RouteGate V → Prop
| .copy out src => val out = val src
| .mux out s yes no => val out = (if val s then val yes else val no)
theorem RouteGate.valid_rename {V W : Type} (f : V → W) (val : W → Bool) (g : RouteGate V) :
(g.rename f).Valid val ↔ g.Valid (val ∘ f) := by cases g <;> rfl
private def column {h : ℕ} {B : Type} (bits : List B) (exit : Bool) :
List (RouteGate (RouteVar (h+1) B)) :=
(wires h).flatMap fun a =>
[false,true].flatMap fun b =>
bits.map fun j =>
(if exit then
.mux (.output (a,b) j) (.control true a) (.internal true (a,!b) j) (.internal true (a,b) j)
else .mux (.internal false (a,b) j) (.control false a) (.input (a,!b) j) (.input (a,b) j))
/-- Explicit replicated gate list with a constant number of gates per bit at each level. -/
def routeGates {B : Type} (bits : List B) :
(h : ℕ) → List (RouteGate (RouteVar h B))
| 0 => bits.map fun j => .copy (.output () j) (.input () j)
| h+1 => column bits false ++
(routeGates bits h).map (RouteGate.rename (RouteVar.embed false)) ++
(routeGates bits h).map (RouteGate.rename (RouteVar.embed true)) ++ column bits true
private theorem column_length {h : ℕ} {B : Type} (bits : List B) (side : Bool) :
(column (h:=h) bits side).length = 2^(h+1)*bits.length := by
unfold column
rw [List.length_flatMap]
simp only [List.length_map, List.length_flatMap, List.map_cons, List.map_nil, List.sum_cons,
List.sum_nil, Nat.add_zero]
change ((wires h).map (Function.const _ (bits.length+bits.length))).sum = _
rw [List.map_const,List.sum_replicate,wires_length,pow_succ]
ring
theorem routeGates_length {B : Type} (bits : List B) (h : ℕ) :
(routeGates bits h).length = (2*h+1)*2^h*bits.length := by
induction h with
| zero => simp [routeGates]
| succ h ih =>
simp only [routeGates,List.length_append,List.length_map,column_length,ih,pow_succ]
ring
private theorem match_column {h : ℕ} {B : Type} {bits : List B}
(v : RouteVar (h+1) B → Bool) (side : Bool)
(hv : ∀ g ∈ column bits side, g.Valid v)
(a : Wire h) (b : Bool) {j : B} (hj : j ∈ bits) :
(if side then v (.output (a,b) j) else v (.internal false (a,b) j)) =
(if v (.control side a) then
if side then v (.internal true (a,!b) j) else v (.input (a,!b) j)
else if side then v (.internal true (a,b) j) else v (.input (a,b) j)) := by
have he : (if side then
RouteGate.mux (.output (a,b) j) (.control true a) (.internal true (a,!b) j) (.internal true (a,b) j)
else .mux (.internal false (a,b) j) (.control false a) (.input (a,!b) j) (.input (a,b) j))
∈ column bits side := by
unfold column
apply List.mem_flatMap.mpr
refine ⟨a,wires_mem h a,?_⟩
apply List.mem_flatMap.mpr
exact ⟨b,by cases b <;> simp,List.mem_map.mpr ⟨j,hj,rfl⟩⟩
have hh := hv _ he
cases side <;> exact hh
/-- Every satisfying assignment to the routing gates realizes a permutation on records. -/
theorem routeGates_sound {B : Type} {bits : List B} (h : ℕ)
(v : RouteVar h B → Bool) (hG : ∀ g ∈ routeGates bits h, g.Valid v) :
∃ setting : Setting h, ∀ x j, j ∈ bits →
v (.output (routing h setting x) j) = v (.input x j) := by
induction h with
| zero =>
refine ⟨(),?_⟩
intro x j hj
cases x
exact hG _ (List.mem_map.mpr ⟨j,hj,rfl⟩)
| succ h ih =>
let entry (i : Wire h) := v (.control false i)
let exit (i : Wire h) := v (.control true i)
let child (b : Bool) (x : RouteVar h B) := v (RouteVar.embed b x)
have left (g) (hg : g ∈ column bits false) : g.Valid v :=
hG g (by simp [routeGates,hg])
have right (g) (hg : g ∈ column bits true) : g.Valid v :=
hG g (by simp [routeGates,hg])
have hc (b : Bool) : ∀ g ∈ routeGates bits h, g.Valid (child b) := by
intro g hg
apply (g.valid_rename (RouteVar.embed b) v).mp
have hm : g.rename (RouteVar.embed b) ∈ (routeGates bits h).map
(RouteGate.rename (RouteVar.embed b)) := List.mem_map.mpr ⟨g,hg,rfl⟩
cases b <;> exact hG _ (by simp [routeGates,hm])
choose mid hm using fun b => ih (child b) (hc b)
refine ⟨(entry,mid,exit),?_⟩
intro x j hj
let q : Wire h × Bool := x
let z := pairSwitch entry q
let a := routing h (mid z.2) z.1
let y := pairSwitch exit (a,z.2)
have he : routing (h+1) (entry,mid,exit) x = y := routing_succ entry mid exit q
rw [he]
have hin : v (.internal false z j) = v (.input q j) := by
rcases q with ⟨b,u⟩
have hh := match_column v false left b (if entry b then !u else u) hj
change v (.internal false (b,if entry b then !u else u) j) =
(if entry b then v (.input (b,!(if entry b then !u else u)) j)
else v (.input (b,if entry b then !u else u) j)) at hh
dsimp only [z,pairSwitch,Equiv.coe_fn_mk]
by_cases he : entry b <;> simpa [he] using hh
have hout : v (.output y j) = v (.internal true (a,z.2) j) := by
have hh := match_column v true right a (if exit a then !z.2 else z.2) hj
change v (.output (a,if exit a then !z.2 else z.2) j) =
(if exit a then v (.internal true (a,!(if exit a then !z.2 else z.2)) j)
else v (.internal true (a,if exit a then !z.2 else z.2) j)) at hh
dsimp only [y,pairSwitch,Equiv.coe_fn_mk]
by_cases he : exit a <;> simpa [he] using hh
exact hout.trans ((hm z.2 z.1 j hj).trans hin)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
private theorem pairSwitch_involutive {A : Type} (c : A → Bool) (p : A × Bool) :
pairSwitch c (pairSwitch c p) = p := (pairSwitch c).symm_apply_apply p
/-- All routing permutations can be realized with arbitrarily prescribed input records. -/
theorem routeGates_complete {B : Type} (bits : List B) (h : ℕ) (s : Setting h)
(input : Wire h → B → Bool) :
∃ v : RouteVar h B → Bool, (∀ g ∈ routeGates bits h, g.Valid v) ∧
(∀ x j, v (.input x j) = input x j) ∧
∀ x j, j ∈ bits → v (.output (routing h s x) j) = input x j := by
induction h with
| zero =>
let v : RouteVar 0 B → Bool
| .input a b | .output a b => input a b
| .aux e => Empty.elim e
refine ⟨v,?_,fun _ _ => rfl,fun _ _ _ => rfl⟩
intro g hg
obtain ⟨j,_,rfl⟩ := List.mem_map.mp hg
rfl
| succ h ih =>
let ss : (Wire h → Bool) × (Bool → Setting h) × (Wire h → Bool) := s
let entry := ss.1
let mid := ss.2.1
let exit := ss.2.2
let childInput (b : Bool) (a : Wire h) (j : B) := input (pairSwitch entry (a,b)) j
choose cv hcv hcin hcout using fun b => ih (mid b) (childInput b)
let v : RouteVar (h+1) B → Bool
| .input x j => input x j
| .output x j =>
let y := pairSwitch exit x
cv y.2 (.output y.1 j)
| .aux (.inl (b,x)) => if b then exit x else entry x
| .aux (.inr (.inl (b,x,j))) =>
if b then cv x.2 (.output x.1 j) else cv x.2 (.input x.1 j)
| .aux (.inr (.inr (b,x))) => cv b (.aux x)
have hv (b : Bool) : v ∘ RouteVar.embed b = cv b := by
funext x
cases x <;> rfl
have hleft : ∀ g ∈ column bits false, g.Valid v := by
intro g hg
obtain ⟨a,ha,h⟩ := List.mem_flatMap.mp hg
obtain ⟨b,hb,hh⟩ := List.mem_flatMap.mp h
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hh
change cv b (.input a j) = (if entry a then input (a,!b) j else input (a,b) j)
rw [hcin b a j]
unfold childInput
by_cases he : entry a <;> simp [pairSwitch,he]
have hright : ∀ g ∈ column bits true, g.Valid v := by
intro g hg
obtain ⟨a,ha,h⟩ := List.mem_flatMap.mp hg
obtain ⟨b,hb,hh⟩ := List.mem_flatMap.mp h
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hh
change cv (pairSwitch exit (a,b)).2 (.output (pairSwitch exit (a,b)).1 j) =
(if exit a then cv (!b) (.output a j) else cv b (.output a j))
by_cases he : exit a <;> simp [pairSwitch,he]
refine ⟨v,?_,fun _ _ => rfl,?_⟩
· intro g hg
simp only [routeGates,List.mem_append] at hg
rcases hg with ((hg|hg)|hg)|hg
· exact hleft _ hg
· obtain ⟨g0,hg0,rfl⟩ := List.mem_map.mp hg
exact (g0.valid_rename _ _).mpr (by rw [hv]; exact hcv false g0 hg0)
· obtain ⟨g0,hg0,rfl⟩ := List.mem_map.mp hg
exact (g0.valid_rename _ _).mpr (by rw [hv]; exact hcv true g0 hg0)
· exact hright _ hg
· intro x j hj
let q : Wire h × Bool := x
let z := pairSwitch entry q
have he : routing (h+1) s x = pairSwitch exit (routing h (mid z.2) z.1,z.2) := by
have hx : (entry,mid,exit) = s := by cases ss; rfl
exact hx ▸ routing_succ entry mid exit q
change cv (pairSwitch exit (routing (h+1) s x)).2
(.output (pairSwitch exit (routing (h+1) s x)).1 j) = input q j
rw [he,pairSwitch_involutive]
have hh := hcout z.2 z.1 j hj
change _ = input (pairSwitch entry z) j at hh
rw [show pairSwitch entry z = q from pairSwitch_involutive entry q] at hh
exact hh
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- Translate symbolic routing constraints into the mission's local gate language. -/
def RouteGate.named {V : Type} (name : V → ℕ) : RouteGate V → Gate
| .copy out src => .copy (name out) (name src)
| .mux out sel crossed straight => .mux (name out) (name sel) (name crossed) (name straight)
theorem RouteGate.named_correct {V : Type} (name : V → ℕ) (α : Assignment)
(g : RouteGate V) : (g.named name).Holds α ↔ g.Valid (α ∘ name) := by cases g <;> rfl
def routeCNF (height width : ℕ) (name : RouteVar height (Fin width) → ℕ) : Formula :=
RobsonCNF.compile ((routeGates (List.finRange width) height).map (RouteGate.named name))
theorem routeCNF_size (height width : ℕ) (name : RouteVar height (Fin width) → ℕ) :
(routeCNF height width name).length ≤ 4*((2*height+1)*2^height*width) := by
unfold routeCNF
apply (length_compile _).trans
rw [List.length_map, routeGates_length]
simp
/-- The endpoint assignments extend to a satisfying assignment of the network if and
only if the output records are a permutation of the input records. -/
theorem routeCNF_spec (height width : ℕ) (name : RouteVar height (Fin width) → ℕ)
(hname : Function.Injective name) (input output : Wire height → Fin width → Bool) :
(∃ α : Assignment, Satisfies α (routeCNF height width name) ∧
(∀ i j, α (name (.input i j)) = input i j) ∧
∀ i j, α (name (.output i j)) = output i j) ↔
∃ σ : Wire height ≃ Wire height, ∀ i j, output (σ i) j = input i j := by
constructor
· rintro ⟨α,hα,hin,hout⟩
have hg : ∀ g ∈ routeGates (List.finRange width) height, g.Valid (α ∘ name) := by
intro g hm
have h := (compile_correct _ _).mp hα (g.named name) (List.mem_map.mpr ⟨g,hm,rfl⟩)
exact (g.named_correct name α).mp h
obtain ⟨s,hs⟩ := routeGates_sound height (α ∘ name) hg
refine ⟨routing height s,fun i j => ?_⟩
exact (hout _ _).symm.trans ((hs _ _ (by simp)).trans (hin _ _))
· rintro ⟨σ,hσ⟩
obtain ⟨s,hs⟩ := routing_universal height σ
obtain ⟨v,hg,hI,hO⟩ := routeGates_complete (List.finRange width) height s input
classical
let α := Function.extend name v (fun _ => false)
have ha : α ∘ name = v := Function.extend_comp hname _ _
refine ⟨α,?_,?_,?_⟩
· apply (compile_correct _ _).mpr
intro g hm
obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hm
apply (r.named_correct name α).mpr
rw [ha]
exact hg r hr
· intro i j
exact (congrFun ha (.input i j)).trans (hI i j)
· intro i j
have hh := hO (σ.symm i) j (by simp)
rw [hs,σ.apply_symm_apply] at hh
have ho := hσ (σ.symm i) j
rw [σ.apply_symm_apply] at ho
exact (congrFun ha (.output i j)).trans (hh.trans ho.symm)
/-- Wires have an explicit position label. -/
def wireLabel : (h : ℕ) → Wire h ≃ Fin (2^h)
| 0 => {toFun := fun _ => 0, invFun := fun _ => (),
left_inv := by intro x; cases x; rfl, right_inv := by intro i; apply Fin.ext; omega}
| h+1 => ((wireLabel h).prodCongr finTwoEquiv.symm).trans
(finProdFinEquiv.trans (finCongr (by rw [pow_succ])))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
def auxCount (w : ℕ) : ℕ → ℕ
| 0 => 0
| h+1 => 2 * 2^h + (2 * (2^(h+1)*w) + 2*auxCount w h)
def auxLabel (w : ℕ) : (h : ℕ) → RouteAux (Fin w) h ≃ Fin (auxCount w h)
| 0 => {toFun := Empty.elim, invFun := Fin.elim0, left_inv := fun x => Empty.elim x, right_inv := fun x => Fin.elim0 x}
| h+1 =>
(Equiv.sumCongr
((finTwoEquiv.symm.prodCongr (wireLabel h)).trans finProdFinEquiv)
((Equiv.sumCongr
((finTwoEquiv.symm.prodCongr (((wireLabel (h+1)).prodCongr (Equiv.refl _)).trans
finProdFinEquiv)).trans finProdFinEquiv)
((finTwoEquiv.symm.prodCongr (auxLabel w h)).trans finProdFinEquiv)).trans
finSumFinEquiv)).trans finSumFinEquiv
/-- Computable numeric labels with an input block, an output block, and distinct
internal variables. -/
def routeLabel (h w : ℕ) : RouteVar h (Fin w) ≃
Fin (2^h*w+(2^h*w+auxCount w h)) := by
let split : RouteVar h (Fin w) ≃
((Wire h × Fin w) ⊕ ((Wire h × Fin w) ⊕ RouteAux (Fin w) h)) :=
{ toFun := fun v => match v with
| .input i j => .inl (i,j)
| .output i j => .inr (.inl (i,j))
| .aux v => .inr (.inr v)
invFun := fun v => match v with
| .inl (i,j) => .input i j
| .inr (.inl (i,j)) => .output i j
| .inr (.inr v) => .aux v
left_inv := by intro v; cases v <;> rfl
right_inv := by rintro (⟨i,j⟩|⟨i,j⟩|v) <;> rfl }
let endpoint := ((wireLabel h).prodCongr (Equiv.refl (Fin w))).trans finProdFinEquiv
exact split.trans ((Equiv.sumCongr endpoint
((Equiv.sumCongr endpoint (auxLabel w h)).trans finSumFinEquiv)).trans finSumFinEquiv)
theorem auxCount_exact (h w : ℕ) : auxCount w h = h*2^h*(1+2*w) := by
induction h with
| zero => simp [auxCount]
| succ h ih => rw [auxCount, ih, pow_succ]; ring
def concreteRouteCNF (base h w : ℕ) : CookLevin.Formula :=
routeCNF h w (fun i => base+(routeLabel h w i).val)
theorem concreteRouteCNF_spec (base h w : ℕ) (input output : Wire h → Fin w → Bool) :
(∃ α : CookLevin.Assignment, CookLevin.Satisfies α (concreteRouteCNF base h w) ∧
(∀ i j, α (base+(routeLabel h w (.input i j)).val) = input i j) ∧
∀ i j, α (base+(routeLabel h w (.output i j)).val) = output i j) ↔
∃ σ : Wire h ≃ Wire h, ∀ i j, output (σ i) j = input i j :=
routeCNF_spec h w _ (fun _ _ he =>
(routeLabel h w).injective (Fin.ext (Nat.add_left_cancel he))) input output
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- Ceiling division gives the number of consecutive groups of at most 2^b records. -/
def groupCount (b n : ℕ) : ℕ := (n+2^b-1)/2^b
/-- Two boundary snapshots of 2^b records each and 2^b event slots fit in 2^(b+2)
wires. A single group has no internal boundaries, so it only pads its event slots. -/
def groupHeight (b n : ℕ) : ℕ := if n ≤ 2^b then slotLevel n else b+2
theorem groupHeight_le (b n : ℕ) : groupHeight b n ≤ b+2 := by
unfold groupHeight
split
· rename_i h
have hs : n-1 < 2^b := by
have hp : 0 < (2:ℕ)^b := Nat.pow_pos (by decide)
omega
exact (Nat.size_le.mpr hs).trans (by omega)
· exact le_rfl
theorem group_capacity (b n : ℕ) (hN : 0 < n) :
n ≤ groupCount b n * 2^groupHeight b n := by
let B := (2:ℕ)^b
have hB : 0 < B := Nat.pow_pos (by decide)
have hAlign : n ≤ groupCount b n * B := alignedStart_lower hB
by_cases hn : n ≤ B
· have hone : groupCount b n = 1 := by
apply Nat.div_eq_of_lt_le
· simp [groupCount,B]
omega
· simp [groupCount,B,two_mul] at *
omega
simp only [groupHeight,show n ≤ 2^b from hn,if_true,hone,one_mul]
exact le_slotWidth n
· have hcap : B ≤ 2^groupHeight b n := by
rw [groupHeight,if_neg hn]
exact Nat.pow_le_pow_right (by decide) (by omega)
exact hAlign.trans (Nat.mul_le_mul_left _ hcap)
theorem grouped_wire_budget (b n : ℕ) (hN : 0 < n) :
groupCount b n * 2^groupHeight b n ≤ 8*n := by
let B := (2:ℕ)^b
have hB : 0 < B := Nat.pow_pos (by decide)
have hAlign : groupCount b n * B < n+B := alignedStart_upper hB
by_cases hn : n ≤ B
· have hONE : groupCount b n = 1 := by
change (n+B-1)/B = 1
apply Nat.div_eq_of_lt_le <;> omega
simp only [groupHeight,show n ≤ 2^b from hn,if_true,hONE,one_mul]
exact (slotWidth_le_double hN).trans (by omega)
· have hpow : (2:ℕ)^groupHeight b n = 4*B := by
rw [groupHeight,if_neg hn,pow_add]
unfold B
ring
rw [hpow]
have hEq : groupCount b n*(4*B) = 4*(groupCount b n*B) := by ring
rw [hEq]
omega
/-- A bound for one width tier. Timestamps are local to each group, so each record
spends O(b) bits on its address, its value, and that timestamp. -/
theorem grouped_routing_budget (b n word : ℕ) (hN : 0 < n) :
groupCount b n * (2*groupHeight b n+1) * 2^groupHeight b n * word ≤
8*n*(2*b+5)*word := by
have hh := groupHeight_le b n
have hg := grouped_wire_budget b n hN
have hh' : 2*groupHeight b n+1 ≤ 2*b+5 := by omega
calc
_ = (groupCount b n * 2^groupHeight b n) * (2*groupHeight b n+1) * word := by ring
_ ≤ _ := Nat.mul_le_mul_right _ (Nat.mul_le_mul hg hh')
/-- Sum of the widths of every tier through level h. -/
theorem tierWidths_sum (h : ℕ) :
∑ j ∈ Finset.range (h+1), (2:ℕ)^j = 2^(h+1)-1 := by
induction h with
| zero => simp
| succ h ih =>
rw [Finset.sum_range_succ,ih,pow_succ (2:ℕ) (h+1)]
have hP : 0 < (2:ℕ)^(h+1) := Nat.pow_pos (by decide)
omega
/-- Summing a per-tier cost linear in the dyadic width costs only twice the largest
width. In particular bounded-word routing does not spend a second logarithmic
factor on all the tiers simultaneously. -/
theorem sum_tier_costs (T C h : ℕ) (cost : ℕ → ℕ)
(hc : ∀ j < h+1, cost j ≤ C*T*2^j) :
(∑ j ∈ Finset.range (h+1),cost j) ≤ 2*C*T*2^h := by
calc
_ ≤ ∑ j ∈ Finset.range (h+1), C*T*2^j :=
Finset.sum_le_sum fun j hj => hc j (Finset.mem_range.mp hj)
_ = C*T*(2^(h+1)-1) := by rw [← Finset.mul_sum,tierWidths_sum]
_ ≤ _ := by
rw [pow_succ]
have hEq : C*T*(2^h*2) = 2*C*T*2^h := by ring
exact (Nat.mul_le_mul_left _ (Nat.sub_le _ _)).trans_eq hEq
end CNFEncComplexity.Robson
/- router numeric interface -/
namespace CNFEncComplexity.Robson
abbrev routeWireList (h : ℕ) : List (Wire h) := wires h
abbrev routeSide {h : ℕ} {B : Type} (bits : List B) (b : Bool) :
List (RouteGate (RouteVar (h+1) B)) := column bits b
theorem routeGates_succ_eq {B : Type} (bits : List B) (h : ℕ) :
routeGates bits (h+1) = routeSide bits false ++
(routeGates bits h).map (RouteGate.rename (RouteVar.embed false)) ++
(routeGates bits h).map (RouteGate.rename (RouteVar.embed true)) ++ routeSide bits true := rfl
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).