Correctness of the trie dictionary for RAM word labels
DefinitionCNFEncComplexity_RobsonMemoryTrieDictionarySoundnesscomplexity-theorysatisfiability
The pooled trie verifies both functional dependencies. Its gates exactly certify injective packed labels for all observed memory words.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieSlots
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonTrieSort -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
structure TrieRowPort where
present : ℕ
parent : ℕ → ℕ
digit : ℕ → ℕ
child : ℕ → ℕ
def TrieRowPort.edge (a : Assignment) (B : ℕ) (r : TrieRowPort) : WordEdge :=
⟨wireValue a r.parent B,wireValue a r.digit B,wireValue a r.child B⟩
def TrieRowPort.decode (a : Assignment) (B : ℕ) (r : TrieRowPort) : Option WordEdge :=
if a r.present then some (r.edge a B) else none
def packTrieKey (B : ℕ) (e : WordEdge) : ℕ := e.digit+2^B*e.parent
theorem packTrieKey_eq {B : ℕ} {e f : WordEdge}
(he : e.digit < 2^B) (hf : f.digit < 2^B) :
packTrieKey B e = packTrieKey B f ↔ e.key = f.key := by
have hp : 0 < (2:ℕ)^B := by positivity
constructor
· intro h
have hd : e.digit = f.digit := by
have hmod := congrArg (fun n => n % 2^B) h
simpa [packTrieKey,Nat.add_mod,Nat.mod_eq_of_lt he,Nat.mod_eq_of_lt hf] using hmod
have hpa : e.parent = f.parent := by
unfold packTrieKey at h
rw [hd,Nat.add_left_cancel_iff] at h
exact Nat.eq_of_mul_eq_mul_left hp h
exact Prod.ext hpa hd
· intro h
have h1 := congrArg Prod.fst h
have h2 := congrArg Prod.snd h
change e.parent = f.parent at h1
change e.digit = f.digit at h2
simp [packTrieKey,h1,h2]
/-- Two passes order by different parts of the same edge record. -/
def trieSortPrimary (B : ℕ) (byChild : Bool) (e : WordEdge) : ℕ :=
if byChild then e.child else packTrieKey B e
def trieSortPayload (B : ℕ) (byChild : Bool) (e : WordEdge) : ℕ :=
trieSortPrimary B (!byChild) e
def trieSortWire (B : ℕ) (byChild : Bool) (r : TrieRowPort) : ℕ → ℕ :=
if byChild then r.child else joinKey r.digit r.parent B
def trieSortWidth (B : ℕ) (byChild : Bool) : ℕ := if byChild then B else B+B
theorem trieSortWire_value (a : Assignment) (B : ℕ) (c : Bool) (r : TrieRowPort) :
wireValue a (trieSortWire B c r) (trieSortWidth B c) =
trieSortPrimary B c (r.edge a B) := by
cases c
· simp [trieSortWire,trieSortWidth,trieSortPrimary,TrieRowPort.edge,packTrieKey,wireValue_joinKey]
· rfl
def trieFunctional (B : ℕ) (c : Bool) (e f : WordEdge) : Prop :=
trieSortPrimary B c e ≤ trieSortPrimary B c f ∧
(trieSortPrimary B c e = trieSortPrimary B c f →
trieSortPayload B c e = trieSortPayload B c f)
def trieOptOrdered {α : Type} (r : α → α → Prop) : Option α → Option α → Prop
| some a,some b => r a b
| none,some _ => False
| _,none => True
def trieRowPair (base B : ℕ) (c : Bool) (l r : TrieRowPort) : List Gate :=
let n := trieSortWidth B c
let m := trieSortWidth B (!c)
let next := base+4*(n+1)
compareCircuit base n (trieSortWire B c l) (trieSortWire B c r) ++
compareCircuit next m (trieSortWire B (!c) l) (trieSortWire B (!c) r) ++
[.assert [.Pos l.present,.Neg r.present],
.assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
.assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]]
theorem trieRowPair_length (base B : ℕ) (c : Bool) (l r : TrieRowPort) :
(trieRowPair base B c l r).length = 12*B+7 := by
cases c <;> simp [trieRowPair,trieSortWidth,length_compareCircuit] <;> omega
private theorem trieRowPair_assertions (a : Assignment) (base B : ℕ) (c : Bool)
(l r : TrieRowPort)
(h1 : ∀ g ∈ compareCircuit base (trieSortWidth B c)
(trieSortWire B c l) (trieSortWire B c r), g.Holds a)
(h2 : ∀ g ∈ compareCircuit (base+4*(trieSortWidth B c+1)) (trieSortWidth B (!c))
(trieSortWire B (!c) l) (trieSortWire B (!c) r), g.Holds a) :
let n := trieSortWidth B c
let m := trieSortWidth B (!c)
let next := base+4*(n+1)
(∀ g ∈ [Gate.assert [.Pos l.present,.Neg r.present],
.assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
.assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]], g.Holds a) ↔
trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
let n := trieSortWidth B c
let m := trieSortWidth B (!c)
let next := base+4*(n+1)
have hKey := compareCircuit_outputs base n _ _ a h1 n le_rfl
have hVal := (compareCircuit_outputs next m _ _ a h2 m le_rfl).2
have hlt : a (ltWire base n) =
decide (trieSortPrimary B c (l.edge a B) < trieSortPrimary B c (r.edge a B)) := by
simpa only [n,trieSortWire_value] using hKey.1
have heq : a (eqWire base n) =
decide (trieSortPrimary B c (l.edge a B) = trieSortPrimary B c (r.edge a B)) := by
simpa only [n,trieSortWire_value] using hKey.2
have hpay : a (eqWire next m) =
decide (trieSortPayload B c (l.edge a B) = trieSortPayload B c (r.edge a B)) := by
have he (x : TrieRowPort) : wireValue a (trieSortWire B (!c) x) m =
trieSortPayload B c (x.edge a B) := trieSortWire_value a B (!c) x
rwa [he l,he r] at hVal
change (∀ g ∈ [Gate.assert [.Pos l.present,.Neg r.present],
.assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
.assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]], g.Holds a) ↔ _
cases hL : a l.present <;> cases hR : a r.present <;>
simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hL,hR,TrieRowPort.decode,trieOptOrdered,
trieFunctional,hlt,heq,hpay] <;> omega
theorem trieRowPair_sound (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
(h : ∀ g ∈ trieRowPair base B c l r, g.Holds a) :
trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
simp only [trieRowPair,List.forall_mem_append] at h
exact (trieRowPair_assertions a base B c l r h.1.1 h.1.2).mp h.2
@[simp] theorem trieRowPair_exact (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
(h1 : ∀ g ∈ compareCircuit base (trieSortWidth B c)
(trieSortWire B c l) (trieSortWire B c r), g.Holds a)
(h2 : ∀ g ∈ compareCircuit (base+4*(trieSortWidth B c+1)) (trieSortWidth B (!c))
(trieSortWire B (!c) l) (trieSortWire B (!c) r), g.Holds a) :
(∀ g ∈ trieRowPair base B c l r, g.Holds a) ↔
trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
simp only [trieRowPair,List.forall_mem_append]
constructor
· exact fun h => (trieRowPair_assertions a base B c l r h1 h2).mp h.2
· exact fun h => ⟨⟨h1,h2⟩,(trieRowPair_assertions a base B c l r h1 h2).mpr h⟩
def trieNonzeroGates (B : ℕ) (r : TrieRowPort) : List Gate :=
[.assert (.Neg r.present :: (List.range B).map fun i => .Pos (r.child i))]
theorem trieNonzero_exact (a : Assignment) (B : ℕ) (r : TrieRowPort) :
(∀ g ∈ trieNonzeroGates B r, g.Holds a) ↔
∀ e, r.decode a B = some e → e.child ≠ 0 := by
have hBits : wireValue a r.child B ≠ 0 ↔ ∃ i < B, a (r.child i) = true := by
constructor
· intro h
by_contra! hh
have hz : ∀ i < B, a (r.child i) = false := by
intro i hi; cases hab : a (r.child i) <;> simp_all
have hZero (n : ℕ) (hn : ∀ i < n, a (r.child i) = false) : wireValue a r.child n = 0 := by
induction n with
| zero => rfl
| succ n ih =>
have hv := ih (fun i hi => hn i (by omega))
simp [wireValue,hn n (by omega),hv]
exact h (hZero B hz)
· rintro ⟨i,hi,ht⟩ hz
rw [← wireValue_testBit a r.child hi,hz] at ht
simp at ht
cases hp : a r.present <;>
simp [trieNonzeroGates,TrieRowPort.decode,TrieRowPort.edge,Gate.Holds,satisfiesClause,
satisfiesLiteral,hp,List.any_map,List.any_eq_true,hBits]
end CNFEncComplexity.Robson
/- RobsonTrieOrder -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem filterNone {α : Type} (r : α → α → Prop) (rs : List (Option α))
(h : (none::rs).IsChain (trieOptOrdered r)) : rs.filterMap id = [] := by
induction rs with
| nil => rfl
| cons o os ih =>
obtain ⟨h₁,h₂⟩ := List.isChain_cons_cons.mp h
cases o with
| none => simpa using ih h₂
| some e => exact False.elim h₁
theorem trieOpt_filter_chain {α : Type} (r : α → α → Prop) (rs : List (Option α))
(h : rs.IsChain (trieOptOrdered r)) : (rs.filterMap id).IsChain r := by
induction rs with
| nil => simp
| cons a as ih =>
cases as with
| nil => cases a <;> simp
| cons b bs =>
obtain ⟨h₁,h₂⟩ := List.isChain_cons_cons.mp h
cases a with
| none =>
change (List.filterMap id (b::bs)).IsChain r
rw [filterNone _ _ h]
simp
| some a =>
cases b with
| none =>
change (a::List.filterMap id bs).IsChain r
rw [filterNone _ _ h₂]
simp
| some b =>
change (a::b::List.filterMap id bs).IsChain r
exact List.isChain_cons_cons.mpr ⟨h₁,ih h₂⟩
/-- The dictionary checker uses only the two permutations and their adjacent
constraints. Neither pass has to compare all pairs of word labels. -/
theorem trieDictionary_sound (B : ℕ) (input byKey byChild : List (Option WordEdge))
(hShape : ∀ e ∈ input.filterMap id, e.digit < 2^B)
(hZero : ∀ e ∈ input.filterMap id, e.child ≠ 0)
(hKey : byKey.Perm input) (hChild : byChild.Perm input)
(hKeyCheck : byKey.IsChain (trieOptOrdered (trieFunctional B false)))
(hChildCheck : byChild.IsChain (trieOptOrdered (trieFunctional B true))) :
WordEdge.Interned (input.filterMap id) := by
have hk := trieOpt_filter_chain _ _ hKeyCheck
have hc := trieOpt_filter_chain _ _ hChildCheck
have hk' (e f : WordEdge) (h : trieFunctional B false e f) :
packTrieKey B e ≤ packTrieKey B f ∧ (packTrieKey B e = packTrieKey B f → e.child=f.child) := h
have hc' (e f : WordEdge) (h : trieFunctional B true e f) :
e.child ≤ f.child ∧ (e.child=f.child → packTrieKey B e = packTrieKey B f) := h
have hKeyFunc := functional_of_adjacent (packTrieKey B) WordEdge.child
(hk.imp (fun {e f} h => (hk' e f h).1)).pairwise (hk.imp (fun {e f} h => (hk' e f h).2))
have hChildFunc := functional_of_adjacent WordEdge.child (packTrieKey B)
(hc.imp (fun {e f} h => (hc' e f h).1)).pairwise (hc.imp (fun {e f} h => (hc' e f h).2))
refine ⟨hZero,?_,?_⟩
· intro e he f hf hh
exact hKeyFunc e ((hKey.filterMap id).mem_iff.mpr he) f ((hKey.filterMap id).mem_iff.mpr hf)
((packTrieKey_eq (hShape e he) (hShape f hf)).mpr hh)
· intro e he f hf hh
exact (packTrieKey_eq (hShape e he) (hShape f hf)).mp
(hChildFunc e ((hChild.filterMap id).mem_iff.mpr he) f ((hChild.filterMap id).mem_iff.mpr hf) hh)
def trieOptionalLE (B : ℕ) (c : Bool) (e f : Option WordEdge) : Bool :=
match e,f with
| some e,some f => decide (trieSortPrimary B c e ≤ trieSortPrimary B c f)
| none,some _ => false
| _,none => true
private theorem trieOptionalLE_trans (B : ℕ) (c : Bool) (e f g : Option WordEdge)
(hef : trieOptionalLE B c e f = true) (hfg : trieOptionalLE B c f g = true) :
trieOptionalLE B c e g = true := by
cases e <;> cases f <;> cases g <;> simp_all [trieOptionalLE]
exact le_trans hef hfg
private theorem trieOptionalLE_total (B : ℕ) (c : Bool) (e f : Option WordEdge) :
(trieOptionalLE B c e f || trieOptionalLE B c f e) = true := by
cases e <;> cases f <;> simp [trieOptionalLE,le_total]
theorem trieOptionalLE_functional {B : ℕ} {c : Bool} {e f : Option WordEdge}
{edges : List WordEdge} (hDict : WordEdge.Interned edges)
(hShape : ∀ e ∈ edges, e.digit < 2^B)
(he : ∀ r, e = some r → r ∈ edges) (hf : ∀ r, f = some r → r ∈ edges)
(h : trieOptionalLE B c e f = true) :
trieOptOrdered (trieFunctional B c) e f := by
cases e <;> cases f <;> simp_all [trieOptionalLE,trieOptOrdered]
rename_i p q
refine ⟨h,?_⟩
cases c
· exact fun hEq => hDict.keyFn _ he _ hf
((packTrieKey_eq (hShape _ he) (hShape _ hf)).mp hEq)
· exact fun hEq => (packTrieKey_eq (hShape _ he) (hShape _ hf)).mpr
(hDict.childFn _ he _ hf hEq)
/-- Choose a routing permutation by sorting source indices. Sorting indices
retains duplicates in the values, so no cardinality or tie ambiguity arises. -/
theorem trieSort_exists_permutation {N : ℕ} (B : ℕ) (c : Bool)
(rows : Fin N → Option WordEdge)
(hDict : WordEdge.Interned ((List.ofFn rows).filterMap id))
(hShape : ∀ e ∈ (List.ofFn rows).filterMap id, e.digit < 2^B) :
∃ σ : Fin N ≃ Fin N,
(List.ofFn (fun i => rows (σ.symm i))).IsChain (trieOptOrdered (trieFunctional B c)) := by
let le := fun i j : Fin N => trieOptionalLE B c (rows i) (rows j)
let sorted := (List.finRange N).mergeSort le
have hp := List.mergeSort_perm (List.finRange N) le
have hL : sorted.length = N := hp.length_eq.trans List.length_finRange
have hn : sorted.Nodup := hp.nodup_iff.mpr (List.nodup_finRange N)
let f : Fin N → Fin N := fun i => sorted.get (Fin.cast hL.symm i)
have hf : Function.Injective f := by
intro i j h
exact (Fin.cast_injective hL.symm) ((List.Nodup.get_inj_iff hn).mp h)
let σ := Equiv.ofBijective f ⟨hf,Finite.injective_iff_surjective.mp hf⟩
refine ⟨σ.symm,?_⟩
have hindices := List.pairwise_mergeSort
(fun i j k => trieOptionalLE_trans B c (rows i) (rows j) (rows k))
(fun i j => trieOptionalLE_total B c (rows i) (rows j)) (List.finRange N)
have hSorted : (sorted.map rows).IsChain (trieOptOrdered (trieFunctional B c)) := by
apply List.Pairwise.isChain
rw [List.pairwise_map]
exact hindices.imp (fun {i j} hij =>
trieOptionalLE_functional hDict hShape (fun e he =>
List.mem_filterMap.mpr ⟨rows i,List.mem_ofFn.mpr ⟨i,rfl⟩,he⟩)
(fun e he => List.mem_filterMap.mpr ⟨rows j,List.mem_ofFn.mpr ⟨j,rfl⟩,he⟩)
hij)
have he : List.ofFn (fun i => rows (σ.symm.symm i)) = sorted.map rows := by
simp only [Equiv.symm_symm]
apply List.ext_getElem
· simp [hL]
· intro i hi hj
simp only [List.getElem_ofFn,List.getElem_map]
rfl
rw [he]
exact hSorted
end CNFEncComplexity.Robson
/- RobsonTrieSortList -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def TrieRowPort.below (r : TrieRowPort) (B base : ℕ) : Prop :=
r.present < base ∧ ∀ i < B, r.parent i < base ∧ r.digit i < base ∧ r.child i < base
theorem TrieRowPort.below_mono {r : TrieRowPort} {B base base' : ℕ} (h : r.below B base)
(hbase : base ≤ base') : r.below B base' :=
⟨h.1.trans_le hbase, fun i hi =>
let hi' := h.2 i hi
⟨hi'.1.trans_le hbase,hi'.2.1.trans_le hbase,hi'.2.2.trans_le hbase⟩⟩
theorem TrieRowPort.decode_frame {r : TrieRowPort} {B base : ℕ} {a b : Assignment} (h : r.below B base)
(hAgree : ∀ i < base, a i = b i) : r.decode a B = r.decode b B := by
have hp := wireValue_congr (n := B) (key := r.parent) (fun i hi => hAgree _ (h.2 i hi).1)
have hd := wireValue_congr (n := B) (key := r.digit) (fun i hi => hAgree _ (h.2 i hi).2.1)
have hc := wireValue_congr (n := B) (key := r.child) (fun i hi => hAgree _ (h.2 i hi).2.2)
simp [TrieRowPort.decode,TrieRowPort.edge,hAgree _ h.1,hp,hd,hc]
private theorem trieSortWire_below {r : TrieRowPort} {B base : ℕ} (h : r.below B base) (c : Bool)
(i : ℕ) (hi : i < trieSortWidth B c) :
trieSortWire B c r i < base := by
cases c
· change i < B+B at hi
change joinKey r.digit r.parent B i < base
by_cases him : i < B
· exact show (if i < B then r.digit i else r.parent (i-B)) < base from
by rw [if_pos him]; exact (h.2 i him).2.1
· exact show (if i < B then r.digit i else r.parent (i-B)) < base from
by rw [if_neg him]; exact (h.2 (i-B) (by omega)).1
· exact (h.2 i hi).2.2
def triePairSpan (B : ℕ) := 12*B+8
private theorem trieSortWidth_sum (B : ℕ) (c : Bool) :
trieSortWidth B c + trieSortWidth B (!c) = 3*B := by
cases c <;> simp [trieSortWidth] <;> omega
theorem trieRowPair_names (base B : ℕ) (c : Bool) (l r : TrieRowPort)
(hL : l.below B base) (hR : r.below B base)
(g : Gate) (hg : g ∈ trieRowPair base B c l r) (i : ℕ)
(hi : i ∈ RobsonCNF.Gate.names g) : i < base+triePairSpan B := by
let n := trieSortWidth B c
let m := trieSortWidth B (!c)
let next := base+4*(n+1)
have hSum : n+m=3*B := trieSortWidth_sum _ _
have hN : base ≤ next := Nat.le_add_right _ _
simp only [trieRowPair,List.mem_append] at hg
rcases hg with (hg|hg)|hg
· have h := compareCircuit_names_lt base n _ _ (trieSortWire_below hL c)
(trieSortWire_below hR c) g hg i hi
unfold triePairSpan
omega
· have h := compareCircuit_names_lt next m _ _ (trieSortWire_below (TrieRowPort.below_mono hL hN) (!c))
(trieSortWire_below (TrieRowPort.below_mono hR hN) (!c)) g hg i hi
change i < base+4*(n+1)+4*m+2 at h
unfold triePairSpan
omega
· have ha := hL.1
have hb := hR.1
simp only [List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl|rfl|rfl <;>
simp only [RobsonCNF.Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,
List.mem_nil_iff,or_false,ltWire,eqWire] at hi <;>
unfold triePairSpan <;>
dsimp only [n,m,next] at hSum <;>
omega
/-- Both scratch comparators for a pair extend below-scratch rows and preserve
all names outside their allocated interval. -/
theorem trieRowPair_extend (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
(hL : l.below B base) (hR : r.below B base)
(hCheck : trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B)) :
∃ b : Assignment, (∀ i, i < base ∨ base+triePairSpan B ≤ i → b i = a i) ∧
∀ g ∈ trieRowPair base B c l r, g.Holds b := by
let n := trieSortWidth B c
let m := trieSortWidth B (!c)
let next := base+4*(n+1)
have hSum : n+m=3*B := trieSortWidth_sum _ _
have hN : base ≤ next := Nat.le_add_right _ _
obtain ⟨a₁,hFrame₁,hFirst⟩ := compareCircuit_extends_interval base n _ _ a
(trieSortWire_below hL c) (trieSortWire_below hR c)
obtain ⟨a₂,hFrame₂,hSecond⟩ := compareCircuit_extends_interval next m _ _ a₁
(trieSortWire_below (TrieRowPort.below_mono hL hN) (!c)) (trieSortWire_below (TrieRowPort.below_mono hR hN) (!c))
have hNext : next = base+4*(n+1) := rfl
have hFr (i : ℕ) (hi : i < base ∨ base+triePairSpan B ≤ i) : a₂ i = a i := by
unfold triePairSpan at hi
rcases hi with h|h
· exact (hFrame₂ _ (.inl (h.trans_le hN))).trans (hFrame₁ _ (.inl h))
· exact (hFrame₂ _ (.inr (by omega))).trans (hFrame₁ _ (.inr (by omega)))
refine ⟨a₂,hFr,?_⟩
have hFirst' : ∀ g ∈ compareCircuit base n (trieSortWire B c l) (trieSortWire B c r),
g.Holds a₂ := by
intro g hg
refine (g.holds_congr a₂ a₁ (fun i hi => hFrame₂ i (.inl ?_))).mpr (hFirst g hg)
have h := compareCircuit_names_lt base n _ _ (trieSortWire_below hL c)
(trieSortWire_below hR c) g hg i hi
omega
apply (trieRowPair_exact a₂ base B c l r hFirst' hSecond).mpr
rw [TrieRowPort.decode_frame hL (fun i hi => hFr i (.inl hi)),
TrieRowPort.decode_frame hR (fun i hi => hFr i (.inl hi))]
exact hCheck
/-- Consecutive positions have disjoint comparator scratch intervals. -/
def trieSortCheckGates (B : ℕ) (c : Bool) : ℕ → List TrieRowPort → List Gate
| base,l::r::rs => trieRowPair base B c l r ++ trieSortCheckGates B c (base+triePairSpan B) (r::rs)
| _,_ => []
theorem trieSortCheckGates_length (B : ℕ) (c : Bool) (base : ℕ) (rows : List TrieRowPort) :
(trieSortCheckGates B c base rows).length ≤ rows.length*(12*B+7) := by
induction rows generalizing base with
| nil => simp [trieSortCheckGates]
| cons l xs ih =>
cases xs with
| nil => simp [trieSortCheckGates]
| cons r rs =>
have h := ih (base+triePairSpan B)
rw [trieSortCheckGates,List.length_append,trieRowPair_length,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
theorem trieSortCheckGates_sound (a : Assignment) (B : ℕ) (c : Bool) (base : ℕ) (rows : List TrieRowPort)
(h : ∀ g ∈ trieSortCheckGates B c base rows, g.Holds a) :
(rows.map (TrieRowPort.decode a B)).IsChain (trieOptOrdered (trieFunctional B c)) := by
induction rows generalizing base with
| nil => simp
| cons l xs ih =>
cases xs with
| nil => simp
| cons r rs =>
rw [trieSortCheckGates,List.forall_mem_append] at h
exact List.isChain_cons_cons.mpr ⟨trieRowPair_sound a base B c l r h.1,ih _ h.2⟩
theorem trieSortCheckGates_extend (a : Assignment) (B : ℕ) (c : Bool) (base : ℕ)
(rows : List TrieRowPort) (hN : ∀ r ∈ rows, r.below B base)
(hCheck : (rows.map (TrieRowPort.decode a B)).IsChain (trieOptOrdered (trieFunctional B c))) :
∃ b : Assignment,
(∀ i, i < base ∨ base+rows.length*triePairSpan B ≤ i → b i = a i) ∧
∀ g ∈ trieSortCheckGates B c base rows, g.Holds b := by
induction rows generalizing base a with
| nil => exact ⟨a,fun _ _ => rfl,by simp [trieSortCheckGates]⟩
| cons l xs ih =>
cases xs with
| nil => exact ⟨a,fun _ _ => rfl,by simp [trieSortCheckGates]⟩
| cons r rs =>
let next := base+triePairSpan B
have hNext : base ≤ next := Nat.le_add_right _ _
have hL := hN l List.mem_cons_self
have hR := hN r (List.mem_cons_of_mem _ List.mem_cons_self)
obtain ⟨hLocal,hRest⟩ := List.isChain_cons_cons.mp hCheck
obtain ⟨a₁,hF₁,hPair⟩ := trieRowPair_extend a base B c l r hL hR hLocal
have hR' : ((r::rs).map (TrieRowPort.decode a₁ B)).IsChain
(trieOptOrdered (trieFunctional B c)) := by
convert hRest using 1
apply List.map_congr_left
intro d hd
exact TrieRowPort.decode_frame (hN d (List.mem_cons_of_mem _ hd)) (fun i hi => hF₁ i (.inl hi))
obtain ⟨a₂,hF₂,hSuffix⟩ := ih a₁ next
(fun d hd => TrieRowPort.below_mono (hN d (List.mem_cons_of_mem _ hd)) hNext) hR'
refine ⟨a₂,?_,?_⟩
· intro i hi
rcases hi with h|h
· exact (hF₂ _ (.inl (h.trans_le hNext))).trans (hF₁ _ (.inl h))
· dsimp [next] at hF₂
rw [List.length_cons,Nat.add_mul,Nat.one_mul] at h
have hh : base+triePairSpan B+(r::rs).length*triePairSpan B ≤ i := by omega
exact (hF₂ _ (.inr hh)).trans (hF₁ _ (.inr (by omega)))
· rw [trieSortCheckGates,List.forall_mem_append]
refine ⟨?_,hSuffix⟩
intro g hg
apply (g.holds_congr a₂ a₁ (fun i hi =>
hF₂ i (.inl (trieRowPair_names base B c l r hL hR g hg i hi)))).mpr
exact hPair g hg
end CNFEncComplexity.Robson
/- RobsonTrieRoutePass -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def trieRowWidth (B : ℕ) : ℕ := 1+3*B
def trieRowFromNat (B : ℕ) (src : ℕ → ℕ) : TrieRowPort :=
⟨src 0,fun i => src (1+i),fun i => src (1+B+i),fun i => src (1+2*B+i)⟩
def trieRouteName (base B h : ℕ) (v : RouteVar h (Fin (trieRowWidth B))) : ℕ :=
base+(routeLabel h (trieRowWidth B) v).val
def trieRouteEnd (base B h : ℕ) : ℕ :=
base+(2^h*trieRowWidth B+(2^h*trieRowWidth B+auxCount (trieRowWidth B) h))
def trieRouteOut (base B h q i : ℕ) : ℕ :=
base+2^h*trieRowWidth B+q*trieRowWidth B+i
def trieRouteIn (base B q i : ℕ) : ℕ := base+q*trieRowWidth B+i
theorem trieRouteName_in (base B h : ℕ) (q : Fin (2^h)) (i : Fin (trieRowWidth B)) :
trieRouteName base B h (.input ((wireLabel h).symm q) i) =
trieRouteIn base B q.val i.val := by
rw [trieRouteName,← nodeRouteName_root]
simp [nodeRouteName,rootRouteNode,routeNodeInput,routeNodeDepth,routeNodeStride,
trieRouteIn,Nat.add_assoc]
exact Or.inl (congrArg Fin.val ((wireLabel h).apply_symm_apply q))
theorem trieRouteName_out (base B h : ℕ) (q : Fin (2^h)) (i : Fin (trieRowWidth B)) :
trieRouteName base B h (.output ((wireLabel h).symm q) i) =
trieRouteOut base B h q.val i.val := by
rw [trieRouteName,← nodeRouteName_root]
simp [nodeRouteName,rootRouteNode,routeNodeOutput,routeNodeDepth,routeNodeStride,
trieRouteOut,Nat.add_assoc]
exact Or.inl (congrArg Fin.val ((wireLabel h).apply_symm_apply q))
theorem trieRouteName_range (base B h : ℕ) (i : RouteVar h (Fin (trieRowWidth B))) :
base ≤ trieRouteName base B h i ∧ trieRouteName base B h i < trieRouteEnd base B h :=
⟨Nat.le_add_right _ _, Nat.add_lt_add_left (routeLabel h (trieRowWidth B) i).isLt _⟩
def trieRouteCopy (base B h : ℕ) (src : ℕ → ℕ → ℕ) : List Gate :=
(List.range (2^h)).flatMap (fun q => wordCopy (trieRowWidth B) (trieRouteIn base B q) (src q))
def trieRouteRows (base B h : ℕ) : List TrieRowPort :=
List.ofFn (fun q : Fin (2^h) => trieRowFromNat B (trieRouteOut base B h q.val))
def trieSortPass (base B h : ℕ) (c : Bool) (src : ℕ → ℕ → ℕ) : List Gate :=
trieRouteCopy base B h src ++ routeNamedGates (trieRouteName base B h) ++
trieSortCheckGates B c (trieRouteEnd base B h) (trieRouteRows base B h)
def trieSortPassEnd (base B h : ℕ) : ℕ :=
trieRouteEnd base B h+2^h*triePairSpan B
def trieSourceRows (a : Assignment) (B h : ℕ) (src : ℕ → ℕ → ℕ) : List (Option WordEdge) :=
List.ofFn (fun q : Fin (2^h) => (trieRowFromNat B (src q.val)).decode a B)
private theorem trieNatRow_congr (a : Assignment) (B : ℕ) {x y : ℕ → ℕ}
(h : ∀ i < trieRowWidth B, a (x i) = a (y i)) :
(trieRowFromNat B x).decode a B = (trieRowFromNat B y).decode a B := by
have hOn : a (x 0) = a (y 0) := h 0 (by unfold trieRowWidth; omega)
have hP : wireValue a (fun i => x (1+i)) B = wireValue a (fun i => y (1+i)) B :=
(wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
have hD : wireValue a (fun i => x (1+B+i)) B = wireValue a (fun i => y (1+B+i)) B :=
(wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
have hC : wireValue a (fun i => x (1+2*B+i)) B = wireValue a (fun i => y (1+2*B+i)) B :=
(wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
simp [trieRowFromNat,TrieRowPort.decode,TrieRowPort.edge,hOn,hP,hD,hC] <;> rfl
private def trieReadBits (B : ℕ) (bs : Fin (trieRowWidth B) → Bool) : Option WordEdge :=
let a : Assignment := fun i => if h : i < trieRowWidth B then bs ⟨i,h⟩ else false
(trieRowFromNat B id).decode a B
private theorem trieReadBits_names (a : Assignment) (B : ℕ) (src : ℕ → ℕ) :
trieReadBits B (fun i => a (src i.val)) = (trieRowFromNat B src).decode a B := by
let a' : Assignment := fun i => if h : i < trieRowWidth B then a (src i) else false
have h (i : ℕ) (hi : i < trieRowWidth B) : a' i = a (src i) := by simp [a',hi]
have hOn : a' 0 = a (src 0) := h 0 (by unfold trieRowWidth; omega)
have hp (k : ℕ) (hk : k ≤ 1+2*B) :
wireValue a' (fun i => k+i) B = wireValue a (fun i => src (k+i)) B := by
apply Nat.eq_of_testBit_eq
intro i
by_cases hi : i < B
· rw [wireValue_testBit _ _ hi,wireValue_testBit _ _ hi]
exact h _ (by unfold trieRowWidth; omega)
· have hh : 2^B ≤ (2:ℕ)^i :=
Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi)
rw [Nat.testBit_lt_two_pow ((wireValue_lt _ _ _).trans_le hh),
Nat.testBit_lt_two_pow ((wireValue_lt _ _ _).trans_le hh)]
change (trieRowFromNat B id).decode a' B = _
simp [trieRowFromNat,TrieRowPort.decode,TrieRowPort.edge,hOn,
hp 1 (by omega),hp (1+B) (by omega),hp (1+2*B) le_rfl] <;> rfl
/-- Any satisfying pass permutes the exact optional records and certifies
adjacent order and functional consistency in its output. -/
theorem trieSortPass_sound (a : Assignment) (base B h : ℕ) (c : Bool) (src : ℕ → ℕ → ℕ)
(hSat : ∀ g ∈ trieSortPass base B h c src, g.Holds a) :
∃ rows : List (Option WordEdge), rows.Perm (trieSourceRows a B h src) ∧
rows.IsChain (trieOptOrdered (trieFunctional B c)) := by
simp only [trieSortPass,List.forall_mem_append] at hSat
obtain ⟨⟨hAtt,hRoute⟩,hSort⟩ := hSat
let rOut := trieRouteRows base B h
let D := trieRowWidth B
have hInput (q : Fin (2^h)) (i : Fin D) :
a (trieRouteName base B h (.input ((wireLabel h).symm q) i)) = a (src q.val i.val) := by
rw [trieRouteName_in]
exact hAtt (.copy (trieRouteIn base B q.val i.val) (src q.val i.val))
(List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,List.mem_map.mpr
⟨i.val,List.mem_range.mpr i.isLt,rfl⟩⟩)
have hp := routeNamedGates_perm (trieRouteName base B h) (trieReadBits B) a hRoute
refine ⟨rOut.map (TrieRowPort.decode a B),?_,trieSortCheckGates_sound a _ _ _ _ hSort⟩
have hl : (List.ofFn fun i : Fin (2^h) => trieReadBits B
(fun j => a (trieRouteName base B h (.output ((wireLabel h).symm i) j)))) =
rOut.map (TrieRowPort.decode a B) := by
unfold rOut trieRouteRows
rw [List.map_ofFn]
congr 1
funext q
simp only [trieRouteName_out,trieReadBits_names,Function.comp_def]
have hr : (List.ofFn fun i : Fin (2^h) => trieReadBits B
(fun j => a (trieRouteName base B h (.input ((wireLabel h).symm i) j)))) =
trieSourceRows a B h src := by
unfold trieSourceRows
congr 1
funext q
simp only [hInput,trieReadBits_names]
simpa only [hl,hr] using hp
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem trieOutputRow_below (base B h : ℕ) (q : Fin (2^h)) :
(trieRowFromNat B (trieRouteOut base B h q.val)).below B (trieRouteEnd base B h) := by
have hh (i : ℕ) (hi : i < trieRowWidth B) :
trieRouteOut base B h q.val i < trieRouteEnd base B h := by
have eq := trieRouteName_out base B h q ⟨i,hi⟩
rw [← eq]
exact (trieRouteName_range _ _ _ _).2
refine ⟨hh _ (by unfold trieRowWidth; omega),?_⟩
intro i hi
exact ⟨hh _ (by unfold trieRowWidth; omega),hh _ (by unfold trieRowWidth; omega),
hh _ (by unfold trieRowWidth; omega)⟩
private theorem trieRouteGateNames (base B h : ℕ) (g : Gate)
(hg : g ∈ routeNamedGates (trieRouteName base B h)) :
∀ i ∈ RobsonCNF.Gate.names g, i < trieRouteEnd base B h := by
obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hg
cases r with
| copy o s => simpa [RouteGate.named,RobsonCNF.Gate.names] using
⟨(trieRouteName_range base B h o).2,(trieRouteName_range base B h s).2⟩
| mux o s y n => simpa [RouteGate.named,RobsonCNF.Gate.names] using
⟨(trieRouteName_range base B h o).2,(trieRouteName_range base B h s).2,
(trieRouteName_range base B h y).2,(trieRouteName_range base B h n).2⟩
/-- A correct dictionary always extends to a satisfying sorted pass. -/
theorem trieSortPass_extend (a : Assignment) (base B h : ℕ)
(c : Bool) (src : ℕ → ℕ → ℕ)
(hSrc : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
(hDict : WordEdge.Interned ((trieSourceRows a B h src).filterMap id)) :
∃ a' : Assignment, (∀ i, i < base ∨ trieSortPassEnd base B h ≤ i → a' i = a i) ∧
∀ g ∈ trieSortPass base B h c src, g.Holds a' := by
let D := trieRowWidth B
let name := trieRouteName base B h
let rows := fun q : Fin (2^h) => (trieRowFromNat B (src q.val)).decode a B
have hD : ∀ e ∈ (trieSourceRows a B h src).filterMap id, e.digit < 2^B := by
intro e he
obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
change (if a (src q.val 0) then some _ else none) = some e at hEq
split at hEq
· obtain rfl := Option.some.inj hEq
exact wireValue_lt ..
· contradiction
obtain ⟨σ,hSorted⟩ := trieSort_exists_permutation B c rows hDict hD
have hInj : Function.Injective name := by
intro i j hh
apply (routeLabel h D).injective
exact Fin.ext (Nat.add_left_cancel hh)
obtain ⟨a₁,hFr₁,haRoute,hInputs,hOutputs⟩ :=
routeNamedGates_extend name hInj a (fun i j => a (src i.val j.val)) σ
have hCopy : ∀ g ∈ trieRouteCopy base B h src, g.Holds a₁ := by
intro g hg
obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hq' := List.mem_range.mp hq
have hi' := List.mem_range.mp hi
have hEq := hInputs ⟨q,hq'⟩ ⟨i,hi'⟩
change a₁ (trieRouteName base B h (.input ((wireLabel h).symm ⟨q,hq'⟩) ⟨i,hi'⟩)) = _ at hEq
rw [trieRouteName_in] at hEq
have hFrSrc : a₁ (src q i) = a (src q i) := by
apply hFr₁
intro v eq
apply (not_le_of_gt (hSrc q hq' i hi'))
rw [← eq]
exact (trieRouteName_range base B h v).1
change a₁ (trieRouteIn base B q i) = a₁ (src q i)
rw [hFrSrc]
exact hEq
have hDecoded (q : Fin (2^h)) :
(trieRowFromNat B (trieRouteOut base B h q.val)).decode a₁ B = rows (σ.symm q) := by
rw [← trieReadBits_names a₁,show rows (σ.symm q) =
trieReadBits B (fun i => a (src (σ.symm q).val i.val)) from (trieReadBits_names a B _).symm]
apply congrArg (trieReadBits B)
funext j
have hx := hOutputs (σ.symm q) j
rw [Equiv.apply_symm_apply] at hx
change a₁ (trieRouteName base B h (.output ((wireLabel h).symm q) j)) = _ at hx
rw [trieRouteName_out] at hx
exact hx
have hSort : ((trieRouteRows base B h).map (TrieRowPort.decode a₁ B)).IsChain
(trieOptOrdered (trieFunctional B c)) := by
unfold trieRouteRows
rw [List.map_ofFn]
simpa only [Function.comp_def,hDecoded] using hSorted
have hBelow (r : TrieRowPort) (hr : r ∈ trieRouteRows base B h) : r.below B (trieRouteEnd base B h) := by
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hr
exact trieOutputRow_below base B h q
obtain ⟨a₂,hFr₂,hCheck⟩ :=
trieSortCheckGates_extend a₁ B c (trieRouteEnd base B h) (trieRouteRows base B h) hBelow hSort
have hEnd : base ≤ trieRouteEnd base B h := Nat.le_add_right _ _
have hFrame (i : ℕ) (hi : i < base ∨ trieSortPassEnd base B h ≤ i) : a₂ i = a i := by
rcases hi with hi|hi
· exact (hFr₂ _ (.inl (hi.trans_le hEnd))).trans (hFr₁ _
(fun v hh => (not_le_of_gt hi) (hh ▸ (trieRouteName_range base B h v).1)))
· have hi' : trieRouteEnd base B h+(trieRouteRows base B h).length*triePairSpan B ≤ i := by
simpa [trieRouteRows,trieSortPassEnd] using hi
have he : trieRouteEnd base B h ≤ i := (Nat.le_add_right _ _).trans hi'
exact (hFr₂ _ (.inr hi')).trans (hFr₁ _ (fun v hh =>
(not_lt_of_ge he) (hh ▸ (trieRouteName_range base B h v).2)))
refine ⟨a₂,hFrame,?_⟩
simp only [trieSortPass,List.forall_mem_append]
refine ⟨⟨?_,?_⟩,hCheck⟩
· intro g hg
obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
have hq' := List.mem_range.mp hq
have hj' := List.mem_range.mp hj
have hn (q : Fin (2^h)) (j : Fin D) : trieRouteIn base B q.val j.val < trieRouteEnd base B h := by
rw [← trieRouteName_in base B h q j]
exact (trieRouteName_range base B h _).2
change a₂ (trieRouteIn base B q j) = a₂ (src q j)
rw [hFr₂ _ (.inl (hn ⟨q,hq'⟩ ⟨j,hj'⟩)),hFr₂ _ (.inl ((hSrc q hq' j hj').trans_le hEnd))]
exact hCopy _ (List.mem_flatMap.mpr ⟨q,hq,List.mem_map.mpr ⟨j,hj,rfl⟩⟩)
· intro g hg
exact (g.holds_congr a₂ a₁ (fun i hi =>
hFr₂ _ (.inl (trieRouteGateNames base B h g hg i hi)))).mpr (haRoute g hg)
end CNFEncComplexity.Robson
/- RobsonGatherLift -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
inductive GatherOutput (w count : ℕ) where
| active
| acc (i : Fin (count+1))
| bit (i : Fin w)
def gatherOutputName {w count : ℕ} (active : ℕ) (acc : ℕ → ℕ) (out : Fin w → ℕ) :
GatherOutput w count → ℕ
| .active => active
| .acc i => acc i.val
| .bit i => out i
/-- A deterministic witness for the local pooling circuit, conditional only
on the presence bits selecting at most one candidate. -/
theorem gatherGates_extends (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (cs : List (GatherCandidate w))
(hUnique : ∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j)
(hInjective : Function.Injective (gatherOutputName (count := cs.length) active acc out))
(hFreshOn : ∀ i : Fin cs.length, ¬∃ z : GatherOutput w cs.length,
gatherOutputName active acc out z = cs[i.val].1)
(hFreshBits : ∀ i : Fin cs.length, ∀ k : Fin w, ¬∃ z : GatherOutput w cs.length,
gatherOutputName active acc out z = cs[i.val].2 k) :
∃ b : Assignment,
(∀ i, (¬∃ z : GatherOutput w cs.length, gatherOutputName active acc out z = i) → b i = a i) ∧
(∀ g ∈ gatherGates active acc out cs, g.Holds b) := by
classical
let dest : GatherOutput w cs.length → ℕ := gatherOutputName active acc out
let on : Prop := ∃ i : Fin cs.length, a cs[i.val].1 = true
let val : GatherOutput w cs.length → Bool
| .active => decide on
| .acc i => decide (GatherSeen a cs i.val)
| .bit k => if hi : on then a (cs[hi.choose.val].2 k) else false
let b : Assignment := Function.extend dest val a
have hDest (v : GatherOutput w cs.length) : b (dest v) = val v := hInjective.extend_apply _ _ _
have hFr (i : ℕ) (hi : ¬∃ z, dest z=i) : b i = a i := Function.extend_apply' _ _ _ hi
have hOn (i : Fin cs.length) : b cs[i.val].1 = a cs[i.val].1 := hFr _ (hFreshOn i)
have hBit (i : Fin cs.length) (k : Fin w) : b (cs[i.val].2 k) = a (cs[i.val].2 k) :=
hFr _ (hFreshBits i k)
refine ⟨b,hFr,?_⟩
apply gatherGates_complete b active acc out cs
· change b (dest .active) = true ↔ _
rw [hDest]
change decide on = true ↔ _
simp only [decide_eq_true_eq,hOn,on]
· intro i j hi hj
exact hUnique i j ((hOn i).symm ▸ hi) ((hOn j).symm ▸ hj)
· intro i hi k
have hi' : a cs[i.val].1=true := (hOn i).symm ▸ hi
have hex : on := ⟨i,hi'⟩
have hl : i = hex.choose := hUnique _ _ hi' hex.choose_spec
change b (cs[i.val].2 k) = b (dest (.bit k))
rw [hBit,hDest]
dsimp [val]
rw [dif_pos hex]
exact congrArg (fun j : Fin cs.length => a (cs[j.val].2 k)) hl
· intro j hj
have he : b (acc j) = decide (GatherSeen a cs j) := hDest (.acc ⟨j,by omega⟩)
rw [he]
have he' : GatherSeen b cs j ↔ GatherSeen a cs j := by simp only [GatherSeen,hOn]
rw [he']
exact ⟨of_decide_eq_true,decide_eq_true⟩
/-- Non-dependent presentation of the same gather template for uniform gate
generation from unary arithmetic and index functions. -/
def gatherArray (w count active : ℕ) (acc out enable : ℕ → ℕ) (payload : ℕ → ℕ → ℕ) : List Gate :=
[.pin (acc 0) false,.copy active (acc count)] ++
(List.range count).flatMap (fun j =>
[.disj (acc (j+1)) (acc j) (enable j),.assert [.Neg (acc j),.Neg (enable j)]] ++
(List.range w).flatMap (fun i => guardEqual (enable j) (payload j i) (out i)))
private theorem finrange_flatmap_eq_range {α : Type} (n : ℕ) (F : ℕ → List α) :
(List.finRange n).flatMap (fun i => F i.val) = (List.range n).flatMap F := by
rw [← List.flatMap_map]
simp
private theorem gatherGates_range {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
(out : Fin w → ℕ) (cs : List (GatherCandidate w)) :
gatherGates active acc out cs = .pin (acc 0) false :: .copy active (acc cs.length) ::
(List.range cs.length).flatMap (fun j => gatherEntry acc out j (cs[j]?.getD (0,fun _ => 0))) := by
unfold gatherGates
rw [← finrange_flatmap_eq_range]
congr 2
apply List.flatMap_congr
intro j hj
rw [List.getElem?_eq_getElem j.isLt,Option.getD_some]
theorem gatherArray_exact (w count active : ℕ) (acc out enable : ℕ → ℕ) (payload : ℕ → ℕ → ℕ) :
gatherArray w count active acc out enable payload = gatherGates active acc
(fun i : Fin w => out i.val) (List.ofFn (fun i : Fin count => (enable i.val,fun k => payload i.val k.val))) := by
rw [gatherGates_range]
simp only [gatherArray,List.length_ofFn,List.cons_append,List.nil_append,List.cons.injEq,true_and]
apply List.flatMap_congr
intro j hj
have hj' : j < count := List.mem_range.mp hj
rw [List.getElem?_eq_getElem (by simpa using hj'),List.getElem_ofFn,Option.getD_some,gatherEntry]
have hh := finrange_flatmap_eq_range w (fun i => guardEqual (enable j) (payload j i) (out i))
simpa only [Prod.fst,Prod.snd,Fin.val_mk,List.cons.injEq,true_and] using hh.symm
section
variable {A : Type} {e : A ↪ List Bool}
private theorem negNeg_poly {r s : A → ℕ}
(hr : ComputableTidilyInPolyTime r e encUnary)
(hs : ComputableTidilyInPolyTime s e encUnary) :
ComputableTidilyInPolyTime
(fun x => Gate.assert [.Neg (r x),.Neg (s x)]) e gateEnc := by
exact gate_assert (cons' (unary_mul.comp ((const 2).prod hr))
(cons' (unary_mul.comp ((const 2).prod hs)) (const [])))
theorem guardEqual_poly {g s d : A → ℕ}
(hg : ComputableTidilyInPolyTime g e encUnary)
(hs : ComputableTidilyInPolyTime s e encUnary)
(hd : ComputableTidilyInPolyTime d e encUnary) :
ComputableTidilyInPolyTime (fun x => guardEqual (g x) (s x) (d x)) e (encList gateEnc) := by
have mul := fun {f : A → ℕ} (h : ComputableTidilyInPolyTime f e encUnary) =>
unary_mul.comp ((const 2).prod h)
have hg' := mul hg
have hs' := mul hs
have hd' := mul hd
have hS := unary_add.comp (hs'.prod (const 1))
have hD := unary_add.comp (hd'.prod (const 1))
exact cons' (gate_assert (cons' hg' (cons' hs' (cons' hD (const [])))))
(cons' (gate_assert (cons' hg' (cons' hS (cons' hd' (const []))))) (const []))
theorem gatherArray_poly {w m active : A → ℕ} {acc out enable : A → ℕ → ℕ} {payload : A → ℕ → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e encUnary)
(hm : ComputableTidilyInPolyTime m e encUnary)
(ha : ComputableTidilyInPolyTime active e encUnary)
(hac : ComputableTidilyInPolyTime (fun p : A×ℕ => acc p.1 p.2) (encPair e encUnary) encUnary)
(hOut : ComputableTidilyInPolyTime (fun p : A×ℕ => out p.1 p.2) (encPair e encUnary) encUnary)
(hen : ComputableTidilyInPolyTime (fun p : A×ℕ => enable p.1 p.2) (encPair e encUnary) encUnary)
(hP : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => payload p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => gatherArray (w x) (m x) (active x)
(acc x) (out x) (enable x) (payload x)) e (encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
have hX := fst e encUnary
have hI := snd e encUnary
have hY := fst e₁ encUnary
have hJ := snd e₁ encUnary
have hEnd := hac.comp ((id' (encIn := e)).prod hm)
have hZero := hac.comp ((id' (encIn := e)).prod (const 0))
have hHead := cons' (gate_pin false hZero) (cons' (gate_copy ha hEnd) (const []))
have hNext := hac.comp (hX.prod (unary_add.comp (hI.prod (const 1))))
have hLead := cons' (gate_disj hNext hac hen) (cons' (negNeg_poly hac hen) (const []))
have hOut' := hOut.comp ((hX.comp hY).prod hJ)
have hBody := flatMapWithInput (f := fun (p : A×ℕ) i =>
guardEqual (enable p.1 p.2) (payload p.1 p.2 i) (out p.1 i))
(range.comp (hw.comp hX)) (guardEqual_poly (hen.comp hY) hP hOut')
have hTail := flatMapWithInput (f := fun x j =>
[.disj (acc x (j+1)) (acc x j) (enable x j),.assert [.Neg (acc x j),.Neg (enable x j)]] ++
(List.range (w x)).flatMap (fun i => guardEqual (enable x j) (payload x j i) (out x i)))
(range.comp hm) (listAppend' hLead hBody)
exact listAppend' hHead hTail
end
end CNFEncComplexity.Robson
/- RobsonTriePool -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def triePoolWidth (b : ℕ) : ℕ := 3*2^b
def triePoolLanes (t b : ℕ) : ℕ := 2^(layoutHeight t-b)
def triePoolHeight (t b : ℕ) : ℕ := layoutHeight t-b+4
def triePoolLevels (t b : ℕ) : ℕ := layoutHeight t+1-b
def triePoolCount (t b q : ℕ) : ℕ :=
if q/triePoolLanes t b < 9 then triePoolLevels t b else 0
def triePoolStride (t b : ℕ) : ℕ := triePoolWidth b+triePoolLevels t b+2
def triePoolRowBase (pool t b q : ℕ) : ℕ := pool+q*triePoolStride t b
def triePoolBit (pool t b q i : ℕ) : ℕ := triePoolRowBase pool t b q+1+i
def triePoolAcc (pool t b q j : ℕ) : ℕ := triePoolRowBase pool t b q+1+triePoolWidth b+j
def triePoolAfter (pool t b : ℕ) : ℕ := pool+2^(triePoolHeight t b)*triePoolStride t b
def triePoolPort (pool t b q : ℕ) : TrieRowPort :=
⟨triePoolRowBase pool t b q, triePoolBit pool t b q,
fun i => triePoolBit pool t b q (2^b+i),fun i => triePoolBit pool t b q (2*2^b+i)⟩
def triePoolRowWords (a : Assignment) (pool t b : ℕ) : List (Option WordEdge) :=
List.ofFn (fun q : Fin (2^(triePoolHeight t b)) => (triePoolPort pool t b q.val).decode a (2^b))
def triePoolSource (t b q j : ℕ) : (ℕ × ℕ) × ℕ × ℕ × ℕ :=
let x := chunkLaneSource b (b+j) (q%triePoolLanes t b)
let f := q/triePoolLanes t b
(x.1,f/3,f%3,x.2)
def triePoolWire (base n t b q j : ℕ) : TrieWordWires :=
let x := triePoolSource t b q j
normalizeSlotWires base n t b x.1 x.2.1 x.2.2.1
def triePoolEnable (base n t b q j : ℕ) : ℕ :=
(triePoolWire base n t b q j).emit (triePoolSource t b q j).2.2.2
def triePoolPayload (base n t b q j i : ℕ) : ℕ :=
let w := triePoolWire base n t b q j
let k := (triePoolSource t b q j).2.2.2
let B := (2:ℕ)^b
if i < B then w.parent k i else
if i < 2*B then w.raw (k*B+(i-B)) else w.child k (i-2*B)
def triePoolLaneGates (base pool n t b q : ℕ) : List Gate :=
gatherArray (triePoolWidth b) (triePoolCount t b q)
(triePoolRowBase pool t b q) (triePoolAcc pool t b q) (triePoolBit pool t b q)
(triePoolEnable base n t b q) (triePoolPayload base n t b q)
def triePoolGateList (base pool n t b : ℕ) : List Gate :=
(List.range (2^(triePoolHeight t b))).flatMap (triePoolLaneGates base pool n t b)
theorem triePoolLanes_eq {t b : ℕ} (h : b ≤ layoutHeight t) :
triePoolLanes t b = layoutHorizon t/2^b := by
have he := normalizeChunkGeometry h
unfold layoutHorizon triePoolLanes
rw [← he,Nat.mul_div_cancel_left]
positivity
theorem triePoolSource_valid {t b q j : ℕ} (h : b ≤ layoutHeight t)
(hj : j < triePoolCount t b q) :
let d := triePoolSource t b q j
d.1 ∈ layoutSlots t ∧ d.2.1 < 3 ∧ d.2.2.1 < 3 ∧
b ≤ d.1.2 ∧ d.2.2.2 < 2^(d.1.2-b) := by
have hCases : q/triePoolLanes t b < 9 := by
by_contra he
simp [triePoolCount,he] at hj
have he : b+j ≤ layoutHeight t := by
simp only [triePoolCount,hCases,if_true,triePoolLevels] at hj
omega
have hPos : 0 < triePoolLanes t b := by unfold triePoolLanes; positivity
have hPool : q%triePoolLanes t b < layoutHorizon t/2^b := by
rw [← triePoolLanes_eq h]
exact Nat.mod_lt _ hPos
have hj' : b ≤ b+j := Nat.le_add_right _ _
have hs := chunkLaneSource_mem hj' he hPool
have hk := chunkLaneSource_chunk_lt b (b+j) (q%triePoolLanes t b)
refine ⟨hs,?_,Nat.mod_lt _ (by decide),hj',hk⟩
change q/triePoolLanes t b/3 < 3
exact (Nat.div_lt_iff_lt_mul (by decide)).mpr hCases
theorem triePoolSource_hits {t b : ℕ} (hb : b ≤ layoutHeight t) {s : ℕ × ℕ}
(hs : s ∈ layoutSlots t) (hbs : b ≤ s.2) {r f k : ℕ} (hr : r < 3) (hf : f < 3)
(hk : k < 2^(s.2-b)) :
∃ q < 2^(triePoolHeight t b), ∃ j < triePoolCount t b q,
triePoolSource t b q j = (s,r,f,k) := by
rcases s with ⟨a,d⟩
let N := triePoolLanes t b
let i := physicalChunkLane b a k
let q := (3*r+f)*N+i
have hp : 0 < N := by unfold N triePoolLanes; positivity
have hi : i < N := by
change i < triePoolLanes t b
rw [triePoolLanes_eq hb]
exact physicalChunkLane_lt hs hbs hk
have hdiv : q/N = 3*r+f := by
unfold q
rw [Nat.mul_comm (3*r+f) N,Nat.mul_add_div hp,Nat.div_eq_of_lt hi,Nat.add_zero]
have hmod : q%N = i := by
unfold q
rw [Nat.add_comm,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lt hi]
have hBnd : q < 2^(triePoolHeight t b) := by
have hmul : (3*r+f+1)*N ≤ 16*N := Nat.mul_le_mul_right N (by omega)
unfold q
have he : 2^(triePoolHeight t b) = 16*N := by
unfold triePoolHeight N triePoolLanes
rw [pow_add,Nat.mul_comm]
rfl
rw [he]
rw [Nat.add_mul,Nat.one_mul] at hmul
omega
have hslot := layout_mem.mp hs
refine ⟨q,hBnd,d-b,?_,?_⟩
· change d-b < if q/N < 9 then triePoolLevels t b else 0
rw [hdiv,if_pos (by omega)]
unfold triePoolLevels
change b ≤ d at hbs
have hd : d ≤ layoutHeight t := hslot.2.1
omega
· have hd : b+(d-b) = d := Nat.add_sub_of_le hbs
have hrw : (3*r+f)/3 = r := by rw [Nat.mul_add_div (by decide),
Nat.div_eq_of_lt hf,Nat.add_zero]
have hfw : (3*r+f)%3 = f := by rw [Nat.mul_comm,Nat.add_comm,Nat.add_mul_mod_self_right,
Nat.mod_eq_of_lt hf]
change ((chunkLaneSource b (b+(d-b)) (q%N)).1,(q/N)/3,(q/N)%3,
(chunkLaneSource b (b+(d-b)) (q%N)).2) = ((a,d),r,f,k)
rw [hd,hmod,hdiv,hrw,hfw,chunkLaneSource_inverse hbs hslot.2.2 hk]
end CNFEncComplexity.Robson
/- RobsonTriePoolSemantics -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem triePoolCands_eq (base pool n t b q : ℕ) :
triePoolLaneGates base pool n t b q =
gatherGates (triePoolRowBase pool t b q) (triePoolAcc pool t b q)
(fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val)
(List.ofFn (fun j : Fin (triePoolCount t b q) =>
(triePoolEnable base n t b q j.val,fun i => triePoolPayload base n t b q j.val i.val))) := by
exact gatherArray_exact ..
private theorem triePoolLane_local (a : Assignment) (base pool n t b q : ℕ)
(h : ∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a) :
(a (triePoolRowBase pool t b q) = true ↔ ∃ j : Fin (triePoolCount t b q),
a (triePoolEnable base n t b q j.val) = true) ∧
(∀ j : Fin (triePoolCount t b q), a (triePoolEnable base n t b q j.val) = true →
∀ i : Fin (triePoolWidth b),
a (triePoolPayload base n t b q j.val i.val) = a (triePoolBit pool t b q i.val)) := by
have hg := (triePoolCands_eq base pool n t b q) ▸ h
let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
(triePoolEnable base n t b q j.val,fun i : Fin (triePoolWidth b) =>
triePoolPayload base n t b q j.val i.val))
have hL : cs.length = triePoolCount t b q := by simp [cs]
have hs := gatherGates_sound a _ _ _ cs hg
refine ⟨?_,?_⟩
· rw [hs.1]
constructor
· rintro ⟨j,hj⟩
refine ⟨Fin.cast hL j,?_⟩
simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj
· rintro ⟨j,hj⟩
refine ⟨Fin.cast hL.symm j,?_⟩
simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj
· intro j hj i
have ho := hs.2.2 (Fin.cast hL.symm j) (by simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj) i
simpa only [cs,List.getElem_ofFn,Fin.val_cast] using ho
theorem triePoolLane_decode (a : Assignment) (base pool n t b q j : ℕ)
(h : ∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a)
(hj : j < triePoolCount t b q) (ha : a (triePoolEnable base n t b q j) = true) :
(triePoolPort pool t b q).decode a (2^b) = some
(trieEdge a (triePoolWire base n t b q j) (2^b) (triePoolSource t b q j).2.2.2) := by
let w := triePoolWire base n t b q j
let k := (triePoolSource t b q j).2.2.2
let B := (2:ℕ)^b
obtain ⟨hOn,hV⟩ := triePoolLane_local a base pool n t b q h
have hp := hOn.mpr ⟨⟨j,hj⟩,ha⟩
have hgParent (i : ℕ) (hi : i < B) :
a (w.parent k i) = a (triePoolBit pool t b q i) := by
have hh := hV ⟨j,hj⟩ ha ⟨i,by unfold triePoolWidth; change i < 3*B; omega⟩
change a (if i < B then w.parent k i else _) = _ at hh
simpa only [if_pos hi] using hh
have hgDigit (i : ℕ) (hi : i < B) :
a (w.raw (k*B+i)) = a (triePoolBit pool t b q (B+i)) := by
have hh := hV ⟨j,hj⟩ ha ⟨B+i,by unfold triePoolWidth; change B+i < 3*B; omega⟩
change a (if B+i < B then _ else if B+i < 2*B then w.raw (k*B+(B+i-B))
else _) = _ at hh
simpa [show ¬ B+i < B by omega,show B+i < 2*B by omega] using hh
have hgChild (i : ℕ) (hi : i < B) :
a (w.child k i) = a (triePoolBit pool t b q (2*B+i)) := by
have hh := hV ⟨j,hj⟩ ha ⟨2*B+i,by unfold triePoolWidth; change 2*B+i < 3*B; omega⟩
change a (if 2*B+i < B then _ else if 2*B+i < 2*B then _ else w.child k (2*B+i-2*B)) = _ at hh
simpa [show ¬ 2*B+i < B by omega,show ¬ (2*B+i < 2*B) by omega] using hh
have hd : (triePoolPort pool t b q).edge a B = trieEdge a w B k := by
unfold TrieRowPort.edge triePoolPort trieEdge
change WordEdge.mk _ _ _ = WordEdge.mk _ _ _
have hhP := (wireValue_eq_iff a (w.parent k) (triePoolBit pool t b q) B).2 hgParent
have hhD := (wireValue_eq_iff a (fun i => w.raw (k*B+i)) (fun i => triePoolBit pool t b q (B+i)) B).2 hgDigit
have hhC := (wireValue_eq_iff a (w.child k) (fun i => triePoolBit pool t b q (2*B+i)) B).2 hgChild
rw [hhP,hhD,hhC]
exact if_pos hp |>.trans (congrArg some hd)
theorem triePool_contains (a : Assignment) (base pool n t b : ℕ)
(hb : b ≤ layoutHeight t)
(h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a)
(s : ℕ × ℕ) (hs : s ∈ layoutSlots t) (r f : ℕ) (hr : r < 3) (hf : f < 3) :
∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ (triePoolRowWords a pool t b).filterMap id := by
by_cases hj : b ≤ s.2
· intro e he
simp only [normalizeWordRows,if_pos hj,trieWordRows] at he
obtain ⟨k,hk,rfl⟩ := List.mem_map.mp he
obtain ⟨hIn,hon⟩ := List.mem_filter.mp hk
obtain ⟨q,hq,i,hi,hSrc⟩ := triePoolSource_hits hb hs hj hr hf (List.mem_range.mp hIn)
have hEnable : a (triePoolEnable base n t b q i) = true := by
simpa [triePoolEnable,triePoolWire,hSrc] using hon
have hLane (g : Gate) (hg : g ∈ triePoolLaneGates base pool n t b q) : g.Holds a :=
h g (List.mem_flatMap.mpr ⟨q,List.mem_range.mpr hq,hg⟩)
have hDecode := triePoolLane_decode a base pool n t b q i hLane hi hEnable
apply List.mem_filterMap.mpr
refine ⟨(triePoolPort pool t b q).decode a (2^b),List.mem_ofFn.mpr ⟨⟨q,hq⟩,rfl⟩,?_⟩
simpa [triePoolWire,hSrc] using hDecode
· simp [normalizeWordRows,hj]
theorem triePool_sound_subset (a : Assignment) (base pool n t b : ℕ)
(hb : b ≤ layoutHeight t)
(h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a)
(dict : List WordEdge)
(hSub : ∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3,
∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
∀ e ∈ (triePoolRowWords a pool t b).filterMap id, e ∈ dict := by
intro e he
obtain ⟨y,hy,hEq⟩ := List.mem_filterMap.mp he
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hy
have hp : a (triePoolRowBase pool t b q.val) = true := by
change (if a (triePoolRowBase pool t b q.val) then some _ else none) = some e at hEq
split at hEq
· assumption
· contradiction
have hLane (g : Gate) (hg : g ∈ triePoolLaneGates base pool n t b q.val) : g.Holds a :=
h g (List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,hg⟩)
have ⟨j,hj⟩ := (triePoolLane_local a base pool n t b q.val hLane).1.mp hp
have hd := triePoolLane_decode a base pool n t b q.val j.val hLane j.isLt hj
have heq := Option.some.inj (hd.symm.trans hEq)
let d := triePoolSource t b q.val j.val
obtain ⟨hs,hr,hf,hb',hk⟩ := triePoolSource_valid hb j.isLt
rw [← heq]
apply hSub d.1 hs d.2.1 hr d.2.2.1 hf
have hd : b ≤ d.1.2 := hb'
rw [normalizeWordRows,if_pos hd,trieWordRows]
exact List.mem_map.mpr ⟨d.2.2.2,List.mem_filter.mpr ⟨List.mem_range.mpr hk,hj⟩,rfl⟩
end CNFEncComplexity.Robson
/- RobsonTriePoolWitness -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem triePoolInput_below {base pool n t b q j : ℕ}
(hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
(hb : b ≤ layoutHeight t) (hj : j < triePoolCount t b q) :
triePoolEnable base n t b q j < pool ∧
∀ i < triePoolWidth b, triePoolPayload base n t b q j i < pool := by
let d := triePoolSource t b q j
let k := d.2.2.2
let s := d.1
let r := d.2.1
let f := d.2.2.1
let B := (2:ℕ)^b
let K := (2:ℕ)^(s.2-b)
let W := (2:ℕ)^s.2
let u := normalizeWordBase base t s r f
let w := normalizeSlotWires base n t b s r f
obtain ⟨hs,hr,hf,hbs,hk⟩ := triePoolSource_valid hb hj
have he : B*K = W := normalizeChunkGeometry hbs
have hK : k < K := hk
have hKey := normalizeKeyBase_range base t (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
have hu : u+normalizeStride t ≤ normalizeAfter base t := hKey.2
have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
have hScratch (p : TrieRest B K) : w.restName p < pool := by
have h := trieWiresAt_rest_bounds u B K (port n t s (3+5*r) 0)
(port n t s (5+5*r+f)) (by unfold B; positivity) (by unfold K; positivity) p
rw [he] at h
change u+W+1 ≤ w.restName p ∧ w.restName p < u+6*W+4 at h
refine h.2.trans_le (?_ : u+6*W+4 ≤ pool)
unfold normalizeStride at hu
omega
refine ⟨hScratch (.emit ⟨k,hK⟩),?_⟩
intro i hi
change i < 3*B at hi
change (if i < B then w.parent k i else
if i < 2*B then w.raw (k*B+(i-B)) else w.child k (i-2*B)) < pool
by_cases hpa : i < B
· rw [if_pos hpa]
exact hScratch (.parent ⟨k,hK⟩ ⟨i,hpa⟩)
· rw [if_neg hpa]
by_cases hd : i < 2*B
· rw [if_pos hd]
have hAll : k*B+B ≤ W := by
have h := Nat.mul_le_mul_right B hK
simpa [Nat.succ_mul,Nat.mul_comm K B,he] using h
have hh : k*B+(i-B) < W := by omega
have hr' := (normalizeWordFrame_raw base n t b s r f hs hr hf).1 _ hh
exact hr'.trans_le (hL.trans (hKey.1.trans (by unfold normalizeStride at hu; omega)))
· rw [if_neg hd]
exact hScratch (.child ⟨k,hK⟩ ⟨i-2*B,by omega⟩)
private theorem triePoolEnabled_live (a : Assignment) {base n t b q j : ℕ}
(hShape : SlotsWellFormed a n t)
(hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a)
(hb : b ≤ layoutHeight t) (hj : j < triePoolCount t b q)
(hEn : a (triePoolEnable base n t b q j) = true) :
(triePoolSource t b q j).1 ∈ liveSlots a n t := by
let d := triePoolSource t b q j
let s := d.1
let w := triePoolWire base n t b q j
obtain ⟨hs,hr,hf,hbs,hk⟩ := triePoolSource_valid hb hj
have hLong : ∀ g ∈ longTrieGates w (2^b) (2^(s.2-b)), g.Holds a := by
intro g hg
apply hNorm
apply List.mem_flatMap.mpr
refine ⟨s,hs, List.mem_flatMap.mpr ⟨d.2.1,List.mem_range.mpr hr,
List.mem_flatMap.mpr ⟨d.2.2.1,List.mem_range.mpr hf,?_⟩⟩⟩
change b ≤ s.2 at hbs
simp only [normalizeWordGates,if_pos hbs]
exact hg
have h := (longTrieGates_emit a w (2^b) (2^(s.2-b))
(by positivity) (by positivity) hLong d.2.2.2 hk).mp hEn
have hOn : a (port n t s (3+5*d.2.1) 0) = true := h.1
apply List.mem_filter.mpr
refine ⟨hs,?_⟩
by_contra! hNot
have hOff : slotLive a n t s = false := by
change slotLive a n t s ≠ true at hNot
simpa using hNot
have hEmpty := (hShape.2 s hs hOff).2
have hMem : ∃ e, portMemory a n t s d.2.1 = some e := by
simp [portMemory,hOn]
obtain ⟨e,he⟩ := hMem
have hRow : e ∈ slotRows a n t s :=
List.mem_filterMap.mpr ⟨d.2.1,List.mem_range.mpr hr,he⟩
simp [hEmpty] at hRow
private theorem triePoolOutput_injective (pool t b q : ℕ) :
Function.Injective (gatherOutputName (count := triePoolCount t b q)
(triePoolRowBase pool t b q) (triePoolAcc pool t b q)
(fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val)) := by
intro p p' he
cases p <;> cases p' <;>
simp only [gatherOutputName,triePoolBit,triePoolAcc] at he
all_goals try rfl
all_goals try (exfalso; omega)
case acc.acc i j => exact congrArg GatherOutput.acc (Fin.ext (by omega))
case bit.bit i j => exact congrArg GatherOutput.bit (Fin.ext (by omega))
private theorem triePoolOutput_range (pool t b q : ℕ)
(i : GatherOutput (triePoolWidth b) (triePoolCount t b q)) :
let v := gatherOutputName (triePoolRowBase pool t b q) (triePoolAcc pool t b q)
(fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val) i
triePoolRowBase pool t b q ≤ v ∧ v < triePoolRowBase pool t b q+triePoolStride t b := by
have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
cases i with
| active => simp [gatherOutputName,triePoolStride] <;> omega
| acc i => have := i.isLt; simp [gatherOutputName,triePoolAcc,triePoolStride]; omega
| bit i => have := i.isLt; simp [gatherOutputName,triePoolBit,triePoolStride]; omega
theorem triePoolLane_extend (a : Assignment) (base pool n t b q : ℕ)
(hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
(hb : b ≤ layoutHeight t) (hShape : SlotsWellFormed a n t)
(hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a) :
∃ a' : Assignment,
(∀ i, i < triePoolRowBase pool t b q ∨ triePoolRowBase pool t b q+triePoolStride t b ≤ i →
a' i = a i) ∧
(∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a') := by
let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
(triePoolEnable base n t b q j.val,fun i : Fin (triePoolWidth b) =>
triePoolPayload base n t b q j.val i.val))
let out := fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val
let active := triePoolRowBase pool t b q
let acc := triePoolAcc pool t b q
have hc : cs.length = triePoolCount t b q := by simp [cs]
have hSome (i : Fin cs.length) : cs[i.val].1 = triePoolEnable base n t b q i.val := by
simp [cs]
have hPayload (i : Fin cs.length) (k : Fin (triePoolWidth b)) :
cs[i.val].2 k = triePoolPayload base n t b q i.val k.val := by simp [cs]
have hU (j k : Fin cs.length) (hj : a cs[j.val].1 = true) (hk : a cs[k.val].1 = true) :
j=k := by
have hpJ : j.val < triePoolCount t b q := hc ▸ j.isLt
have hpK : k.val < triePoolCount t b q := hc ▸ k.isLt
have hJ := triePoolEnabled_live a hShape hNorm hb hpJ ((hSome j) ▸ hj)
have hK := triePoolEnabled_live a hShape hNorm hb hpK ((hSome k) ▸ hk)
have eq := chunkLaneSource_unique hShape (Nat.le_add_right b j.val)
(Nat.le_add_right b k.val) hJ hK
exact Fin.ext (Nat.add_left_cancel eq)
have hN : Function.Injective (gatherOutputName (count := cs.length) active acc out) := by
rw [hc]
exact triePoolOutput_injective pool t b q
have hRange (p : GatherOutput (triePoolWidth b) cs.length) :
active ≤ gatherOutputName active acc out p ∧
gatherOutputName active acc out p < active+triePoolStride t b := by
have hCc : cs.length ≤ triePoolLevels t b := by
rw [hc]; unfold triePoolCount; split <;> omega
cases p with
| active => simp [gatherOutputName,triePoolStride,active] <;> omega
| acc j =>
have hj := j.isLt
simp [gatherOutputName,triePoolAcc,triePoolStride,active,acc]
omega
| bit j => have hj := j.isLt; simp [gatherOutputName,triePoolBit,triePoolStride,active,out]; omega
have hAP : pool ≤ active := Nat.le_add_right _ _
obtain ⟨a',hFr,hSat⟩ := gatherGates_extends a active acc out cs hU hN
(fun j => by
rintro ⟨p,he⟩
have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
have h := (triePoolInput_below hL hPool hb hj).1
have hp := (hRange p).1
rw [he,hSome] at hp
exact (not_lt_of_ge (hAP.trans hp)) h)
(fun j k => by
rintro ⟨p,he⟩
have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
have h := (triePoolInput_below hL hPool hb hj).2 _ k.isLt
have hp := (hRange p).1
rw [he,hPayload] at hp
exact (not_lt_of_ge (hAP.trans hp)) h)
refine ⟨a',?_,?_⟩
· intro i hi
apply hFr
rintro ⟨p,he⟩
obtain ⟨hl,hh⟩ := hRange p
rw [he] at hl hh
change i < active ∨ active+triePoolStride t b ≤ i at hi
omega
· simpa only [triePoolCands_eq] using hSat
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- All enumerated physical pool lanes are independently writable. Active
candidate bits and payload bits below the pool are preserved. -/
theorem triePool_complete (a : Assignment) (base pool n t b : ℕ)
(hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
(hb : b ≤ layoutHeight t) (hShape : SlotsWellFormed a n t)
(hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a) :
∃ a' : Assignment,
(∀ i, i < pool ∨ triePoolAfter pool t b ≤ i → a' i = a i) ∧
(∀ g ∈ triePoolGateList base pool n t b, g.Holds a') := by
classical
choose pick hFrame hGate using fun q =>
triePoolLane_extend a base pool n t b q hL hPool hb hShape hNorm
let step := triePoolStride t b
have hStep : 0 < step := by unfold step triePoolStride; omega
let top := triePoolAfter pool t b
let a' : Assignment := fun i => if pool ≤ i ∧ i < top then pick ((i-pool)/step) i else a i
have hFix (i : ℕ) (hi : i < pool ∨ top ≤ i) : a' i = a i := by
unfold a'
rw [if_neg]
omega
have hLocal (q i : ℕ) (hq : q < 2^(triePoolHeight t b))
(h : triePoolRowBase pool t b q ≤ i ∧ i < triePoolRowBase pool t b q+step) :
a' i = pick q i := by
have hq' : q+1 ≤ 2^(triePoolHeight t b) := hq
have hp := Nat.mul_le_mul_right step hq'
rw [Nat.add_mul,Nat.one_mul] at hp
change pool+q*step ≤ i ∧ i < pool+q*step+step at h
have htop : top = pool+2^(triePoolHeight t b)*step := rfl
have hd : pool ≤ i ∧ i < top := by omega
have hDecomp : i-pool = (i-(pool+q*step))+q*step := by omega
have hh : i-(pool+q*step) < step := by omega
unfold a'
rw [if_pos hd,hDecomp,Nat.add_mul_div_right _ _ hStep,Nat.div_eq_of_lt hh,Nat.zero_add]
refine ⟨a',hFix,?_⟩
intro g hg
obtain ⟨q,hq,hqg⟩ := List.mem_flatMap.mp hg
have hq' := List.mem_range.mp hq
let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
(triePoolEnable base n t b q j.val,
fun i : Fin (triePoolWidth b) => triePoolPayload base n t b q j.val i.val))
let active := triePoolRowBase pool t b q
let out := fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val
let acc := triePoolAcc pool t b q
have hc : cs.length = triePoolCount t b q := by simp [cs]
have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
have hQA : pool ≤ active := Nat.le_add_right _ _
have hActive : a' active = pick q active := by apply hLocal q _ hq'; exact ⟨le_rfl,by omega⟩
have hAcc (i : ℕ) (hi : i ≤ cs.length) : a' (acc i) = pick q (acc i) := by
apply hLocal q _ hq'
change active ≤ active+1+triePoolWidth b+i ∧ active+1+triePoolWidth b+i < active+step
unfold step triePoolStride
omega
have hOut (i : Fin (triePoolWidth b)) : a' (out i) = pick q (out i) := by
apply hLocal q _ hq'
change active ≤ active+1+i.val ∧ active+1+i.val < active+step
have := i.isLt
unfold step triePoolStride
omega
have hEnabled (i : Fin cs.length) : a' cs[i.val].1 = pick q cs[i.val].1 := by
have hi : i.val < triePoolCount t b q := hc ▸ i.isLt
have hp := (triePoolInput_below hL hPool hb hi).1
have he : cs[i.val].1 = triePoolEnable base n t b q i.val := by simp [cs]
rw [he,hFix _ (.inl hp),hFrame q _ (.inl (hp.trans_le hQA))]
have hPayload (j : Fin cs.length) (i : Fin (triePoolWidth b)) :
a' (cs[j.val].2 i) = pick q (cs[j.val].2 i) := by
have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
have hp := (triePoolInput_below hL hPool hb hj).2 _ i.isLt
have he : cs[j.val].2 i = triePoolPayload base n t b q j.val i.val := by simp [cs]
rw [he,hFix _ (.inl hp),hFrame q _ (.inl (hp.trans_le hQA))]
have hqSat : ∀ g ∈ gatherGates active acc out cs, g.Holds (pick q) := by
simpa only [triePoolCands_eq] using hGate q
obtain ⟨h0,hL,hLoc⟩ := (gatherGates_local (pick q) active acc out cs).mp hqSat
apply (gatherGates_local a' active acc out cs).mpr ?_ g
· exact (triePoolCands_eq base pool n t b q) ▸ hqg
· refine ⟨?_,?_,?_⟩
· rwa [hAcc _ (Nat.zero_le _)]
· rwa [hActive,hAcc _ le_rfl]
· intro i
rw [hAcc _ i.isLt,hAcc _ i.isLt.le,hEnabled i]
refine ⟨(hLoc i).1,(hLoc i).2.1,?_⟩
intro hOn k
rw [hPayload i k,hOut k]
exact (hLoc i).2.2 hOn k
theorem triePoolGateList_length (base pool n t b : ℕ) (hb : b ≤ layoutHeight t) :
(triePoolGateList base pool n t b).length ≤ 160*(layoutHorizon t*(layoutHeight t+1)) := by
let B := (2:ℕ)^b
let N := triePoolLanes t b
let C := layoutHeight t+1
have hp : 0 < B := by unfold B; positivity
have he : B*N = layoutHorizon t := normalizeChunkGeometry hb
have hN : N ≤ layoutHorizon t := by
rw [← he,Nat.mul_comm]
simpa using Nat.mul_le_mul_left N hp
have hC : 0 < C := by unfold C; omega
have hNpool : 2^(triePoolHeight t b) = 16*N := by
unfold triePoolHeight N triePoolLanes
rw [pow_add,Nat.mul_comm]
rfl
have hSingle (q : ℕ) : (triePoolLaneGates base pool n t b q).length ≤ 2+(8*B)*C := by
have hq : triePoolCount t b q ≤ C := by unfold triePoolCount triePoolLevels C; split <;> omega
rw [triePoolCands_eq,gatherGates_length,List.length_ofFn]
apply Nat.add_le_add_left
exact Nat.mul_le_mul (by unfold triePoolWidth; change 2+2*(3*B) ≤ 8*B; omega) hq
have hSum (xs : List ℕ) :
(xs.flatMap (triePoolLaneGates base pool n t b)).length ≤ xs.length*(2+(8*B)*C) := by
induction xs with
| nil => simp
| cons x xs ih =>
rw [List.flatMap_cons,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul,Nat.add_comm]
exact Nat.add_le_add ih (hSingle x)
unfold triePoolGateList
refine (hSum _).trans ?_
rw [List.length_range,hNpool]
have hExpand : (16*N)*(2+(8*B)*C) = 32*N+128*((B*N)*C) := by ring
rw [hExpand,he]
have hSmall : 32*N ≤ 32*(layoutHorizon t*C) := by
exact Nat.mul_le_mul_left _ (hN.trans (by simpa using Nat.mul_le_mul_left (layoutHorizon t) hC))
change 32*N+128*(layoutHorizon t*C) ≤ 160*(layoutHorizon t*C)
omega
end CNFEncComplexity.Robson
/- RobsonTrieDictionary -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem trieSortCheckNames (base B : ℕ) (c : Bool) (rows : List TrieRowPort)
(hN : ∀ r ∈ rows, r.below B base)
(g : Gate) (hg : g ∈ trieSortCheckGates B c base rows) (i : ℕ) (hi : i ∈ RobsonCNF.Gate.names g) :
i < base+rows.length*triePairSpan B := by
induction rows generalizing base with
| nil => simp [trieSortCheckGates] at hg
| cons l rows ih =>
cases rows with
| nil => simp [trieSortCheckGates] at hg
| cons r rs =>
simp only [trieSortCheckGates,List.mem_append] at hg
cases hg with
| inl hl =>
have hlt := trieRowPair_names base B c l r (hN l List.mem_cons_self)
(hN r (List.mem_cons_of_mem _ List.mem_cons_self)) g hl i hi
exact hlt.trans_le (by
rw [List.length_cons,Nat.add_mul,Nat.one_mul]
omega)
| inr hr =>
have hN' (r' : TrieRowPort) (hh : r' ∈ r::rs) : r'.below B (base+triePairSpan B) :=
TrieRowPort.below_mono (hN _ (List.mem_cons_of_mem _ hh)) (Nat.le_add_right _ _)
have hh := ih _ hN' hr
rw [List.length_cons,Nat.add_mul,Nat.one_mul]
omega
private theorem trieDataBelow (base B h : ℕ) (src : ℕ→ℕ→ℕ)
(hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base) (q : Fin (2^h)) :
(trieRowFromNat B (src q.val)).below B base := by
refine ⟨hS _ q.isLt _ (by unfold trieRowWidth; omega), ?_⟩
intro i hi
exact ⟨hS _ q.isLt _ (by unfold trieRowWidth; omega),
hS _ q.isLt _ (by unfold trieRowWidth; omega),
hS _ q.isLt _ (by unfold trieRowWidth; omega)⟩
private theorem trieSourceRows_frame (a a' : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
(hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base) (hFrame : ∀ i < base, a i = a' i) :
trieSourceRows a B h src = trieSourceRows a' B h src := by
unfold trieSourceRows
congr 1
funext q
exact TrieRowPort.decode_frame (trieDataBelow base B h src hS q) hFrame
private theorem trieRouteOut_below' (base B h : ℕ) (q : Fin (2^h)) :
(trieRowFromNat B (trieRouteOut base B h q.val)).below B (trieRouteEnd base B h) := by
have hh (i : ℕ) (hi : i < trieRowWidth B) :
trieRouteOut base B h q.val i < trieRouteEnd base B h := by
rw [← trieRouteName_out base B h q ⟨i,hi⟩]
exact (trieRouteName_range _ _ _ _).2
refine ⟨hh _ (by unfold trieRowWidth; omega),?_⟩
intro i hi
exact ⟨hh _ (by unfold trieRowWidth; omega),hh _ (by unfold trieRowWidth; omega),
hh _ (by unfold trieRowWidth; omega)⟩
private theorem trieSortPass_names_lt (base B h : ℕ) (c : Bool) (src : ℕ→ℕ→ℕ)
(hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
(g : Gate) (hg : g ∈ trieSortPass base B h c src) (i : ℕ)
(hi : i ∈ RobsonCNF.Gate.names g) : i < trieSortPassEnd base B h := by
have hR : trieRouteEnd base B h ≤ trieSortPassEnd base B h := Nat.le_add_right _ _
have hBase : base ≤ trieRouteEnd base B h := Nat.le_add_right _ _
simp only [trieSortPass,List.mem_append] at hg
rcases hg with (hg|hg)|hg
· obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
have hv : trieRouteIn base B q j < trieRouteEnd base B h := by
rw [← trieRouteName_in base B h ⟨q,List.mem_range.mp hq⟩ ⟨j,List.mem_range.mp hj⟩]
exact (trieRouteName_range _ _ _ _).2
simp only [RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
rcases hi with rfl|rfl
· exact hv.trans_le hR
· exact (hS _ (List.mem_range.mp hq) _ (List.mem_range.mp hj)).trans_le (hBase.trans hR)
· obtain ⟨g,hg,rfl⟩ := List.mem_map.mp hg
have hv (r : RouteVar h (Fin (trieRowWidth B))) :
trieRouteName base B h r < trieSortPassEnd base B h :=
((trieRouteName_range _ _ _ _).2).trans_le hR
cases g with
| copy _ _ =>
simp only [RouteGate.named,RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
rcases hi with rfl|rfl <;> exact hv _
| mux _ _ _ _ =>
simp only [RouteGate.named,RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
rcases hi with rfl|rfl|rfl|rfl <;> exact hv _
· have hBound (r : TrieRowPort) (hr : r ∈ trieRouteRows base B h) :
r.below B (trieRouteEnd base B h) := by
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hr
exact trieRouteOut_below' base B h q
have hf := trieSortCheckNames _ _ c _ hBound g hg i hi
simpa [trieSortPassEnd,trieRouteRows] using hf
def trieNonzeroList (B h : ℕ) (src : ℕ→ℕ→ℕ) : List Gate :=
(List.range (2^h)).flatMap (fun q => trieNonzeroGates B (trieRowFromNat B (src q)))
def trieDictionaryGates (base B h : ℕ) (src : ℕ→ℕ→ℕ) : List Gate :=
trieNonzeroList B h src ++ trieSortPass base B h false src ++
trieSortPass (trieSortPassEnd base B h) B h true src
def trieDictionaryEnd (base B h : ℕ) : ℕ := trieSortPassEnd (trieSortPassEnd base B h) B h
theorem trieDictionaryGates_sound (a : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
(hG : ∀ g ∈ trieDictionaryGates base B h src, g.Holds a) :
WordEdge.Interned ((trieSourceRows a B h src).filterMap id) := by
simp only [trieDictionaryGates,List.forall_mem_append] at hG
obtain ⟨⟨hZ,hK⟩,hC⟩ := hG
obtain ⟨key,hKey,hKeyC⟩ := trieSortPass_sound a base B h false src hK
obtain ⟨child,hChild,hChildC⟩ := trieSortPass_sound a _ B h true src hC
refine trieDictionary_sound B _ key child ?_ ?_ hKey hChild hKeyC hChildC
· intro e he
obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
change (if a (src q.val 0) then some _ else none) = some e at hEq
split at hEq
· obtain rfl := Option.some.inj hEq
exact wireValue_lt ..
· contradiction
· intro e he
obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
exact (trieNonzero_exact a B (trieRowFromNat B (src q.val))).mp
(fun g hg => hZ g (List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,hg⟩)) _ hEq
theorem trieDictionaryGates_extend (a : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
(hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
(hW : WordEdge.Interned ((trieSourceRows a B h src).filterMap id)) :
∃ a' : Assignment,
(∀ i, i < base ∨ trieDictionaryEnd base B h ≤ i → a' i = a i) ∧
(∀ g ∈ trieDictionaryGates base B h src, g.Holds a') := by
let next := trieSortPassEnd base B h
have hNext : base ≤ next := (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
obtain ⟨a₁,hF₁,hFirst⟩ := trieSortPass_extend a base B h false src hS hW
have hW₁ : WordEdge.Interned ((trieSourceRows a₁ B h src).filterMap id) := by
rw [trieSourceRows_frame a₁ a base B h src hS (fun i hi => hF₁ _ (.inl hi))]
exact hW
have hS' (q : ℕ) (hq : q < 2^h) (i : ℕ) (hi : i < trieRowWidth B) : src q i < next :=
(hS q hq i hi).trans_le hNext
obtain ⟨a₂,hF₂,hSecond⟩ := trieSortPass_extend a₁ next B h true src hS' hW₁
have hB : next ≤ trieSortPassEnd next B h := (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
have hF (i : ℕ) (hi : i < base ∨ trieDictionaryEnd base B h ≤ i) : a₂ i = a i := by
rcases hi with hi | hi
· exact (hF₂ _ (.inl (hi.trans_le hNext))).trans (hF₁ _ (.inl hi))
· exact (hF₂ _ (.inr hi)).trans (hF₁ _ (.inr (hB.trans hi)))
refine ⟨a₂,hF,?_⟩
simp only [trieDictionaryGates,List.forall_mem_append]
refine ⟨⟨?_,?_⟩,hSecond⟩
· intro g hg
obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
apply (trieNonzero_exact a₂ B (trieRowFromNat B (src q))).2 ?_ _ hg
intro e he
let q' : Fin (2^h) := ⟨q,List.mem_range.mp hq⟩
have hD := TrieRowPort.decode_frame (trieDataBelow base B h src hS q') (a := a₂) (b := a)
(fun i hi => hF _ (.inl hi))
have hh := hD ▸ he
exact hW.nonzero _ (List.mem_filterMap.mpr ⟨_,List.mem_ofFn.mpr ⟨q',rfl⟩,hh⟩)
· intro g hg
exact (g.holds_congr a₂ a₁ (fun i hi =>
hF₂ _ (.inl (trieSortPass_names_lt base B h false src hS g hg i hi)))).mpr (hFirst g hg)
/-- The dictionary check reads its source and two consecutive private sorting areas. -/
theorem trieDictionaryGates_names_lt (base B h : ℕ) (src : ℕ → ℕ → ℕ)
(hSource : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
(g : Gate) (hg : g ∈ trieDictionaryGates base B h src)
(i : ℕ) (hi : i ∈ RobsonCNF.Gate.names g) : i < trieDictionaryEnd base B h := by
have hPass (n : ℕ) : n ≤ trieSortPassEnd n B h :=
(Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
have hEnd : trieSortPassEnd base B h ≤ trieDictionaryEnd base B h := hPass _
simp only [trieDictionaryGates,List.mem_append] at hg
rcases hg with (hg|hg)|hg
· obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
simp only [trieNonzeroGates,List.mem_singleton] at hg
subst g
simp only [RobsonCNF.Gate.names,List.map_cons,List.mem_cons] at hi
rcases hi with hi | hi
· subst i
exact (hSource q (List.mem_range.mp hq) 0 (by simp [trieRowWidth])).trans_le
((hPass _).trans hEnd)
· obtain ⟨lit,hlit,rfl⟩ := List.mem_map.mp hi
obtain ⟨bit,hbit,rfl⟩ := List.mem_map.mp hlit
change src q (1+2*B+bit) < trieDictionaryEnd base B h
have hbit := List.mem_range.mp hbit
have hRange : 1+2*B+bit < trieRowWidth B := by unfold trieRowWidth; omega
exact (hSource q (List.mem_range.mp hq) _ hRange).trans_le ((hPass _).trans hEnd)
· exact (trieSortPass_names_lt base B h false src hSource g hg i hi).trans_le hEnd
· exact trieSortPass_names_lt _ B h true src
(fun q hq k hk => (hSource q hq k hk).trans_le (hPass _)) g hg i hi
end CNFEncComplexity.Robson
/- RobsonTrieComponent -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- Finite packed shape shared by the pool and the two sorted permutations. -/
def triePoolSourceWire (pool t b q i : ℕ) : ℕ :=
triePoolRowBase pool t b q+i
theorem triePoolSourceWire_below (pool t b : ℕ) (q : ℕ) (hq : q < 2^(triePoolHeight t b))
(i : ℕ) (hi : i < trieRowWidth (2^b)) :
triePoolSourceWire pool t b q i < triePoolAfter pool t b := by
have hMq := Nat.mul_le_mul_right (triePoolStride t b) hq
change ((q+1)*triePoolStride t b) ≤ 2^(triePoolHeight t b)*triePoolStride t b at hMq
rw [Nat.add_mul,Nat.one_mul] at hMq
unfold triePoolSourceWire triePoolAfter triePoolRowBase at *
unfold triePoolStride trieRowWidth triePoolWidth at *
omega
private theorem triePoolSourceWire_row (pool t b q : ℕ) :
trieRowFromNat (2^b) (triePoolSourceWire pool t b q) = triePoolPort pool t b q := by
simp [trieRowFromNat,triePoolPort,triePoolSourceWire,triePoolBit,Nat.add_assoc]
funext i
simp [triePoolBit,Nat.add_assoc]
theorem triePoolSourceWords (a : Assignment) (pool t b : ℕ) :
trieSourceRows a (2^b) (triePoolHeight t b) (triePoolSourceWire pool t b) =
triePoolRowWords a pool t b := by
unfold trieSourceRows triePoolRowWords
apply congrArg List.ofFn
funext q
rw [triePoolSourceWire_row]
def normalizeMemoryGates (base n t b : ℕ) : List Gate :=
let pool := normalizeAfter base t
normalizeLayoutGates base n t b ++ triePoolGateList base pool n t b ++
trieDictionaryGates (triePoolAfter pool t b) (2^b) (triePoolHeight t b) (triePoolSourceWire pool t b)
def normalizeMemoryEnd (base t b : ℕ) : ℕ :=
trieDictionaryEnd (triePoolAfter (normalizeAfter base t) t b) (2^b) (triePoolHeight t b)
theorem normalizeMemoryGates_sound (a : Assignment) (base n t b : ℕ)
(hb : b ≤ layoutHeight t) (h : ∀ g ∈ normalizeMemoryGates base n t b, g.Holds a) :
∃ dict : List WordEdge, WordEdge.Interned dict ∧
PackedSlots a n t (2^b) dict (slotCompactRows a base n t b) := by
simp only [normalizeMemoryGates,List.forall_mem_append] at h
obtain ⟨⟨hNorm,hPool⟩,hDict⟩ := h
let pool := normalizeAfter base t
let dict := (triePoolRowWords a pool t b).filterMap id
have hD := trieDictionaryGates_sound a (triePoolAfter pool t b) (2^b) (triePoolHeight t b)
(triePoolSourceWire pool t b) hDict
rw [triePoolSourceWords] at hD
refine ⟨dict,hD,⟨?_,?_⟩⟩
· intro s hs
exact normalizedSlot_sound a base n t b s
(fun g hg => hNorm g (List.mem_flatMap.mpr ⟨s,hs,hg⟩)) dict
(fun r hr f hf => triePool_contains a base pool n t b hb hPool s hs r f hr hf)
· intro s hs r hr
obtain ⟨i,_,hi⟩ := List.mem_filterMap.mp hr
unfold slotCompactMemory at hi
split at hi
· obtain rfl := Option.some.inj hi
exact ⟨Nat.size_le.mpr (wireValue_lt ..),Nat.size_le.mpr (wireValue_lt ..),Nat.size_le.mpr (wireValue_lt ..)⟩
· contradiction
theorem normalizePoolGates_frame (a α : Assignment) (base pool n t b : ℕ)
(hBase : sharedLimit n t ≤ base) (hP : normalizeAfter base t ≤ pool) (hb : b ≤ layoutHeight t)
(hFr : ∀ i < triePoolAfter pool t b, α i = a i)
(h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a) :
∀ g ∈ triePoolGateList base pool n t b, g.Holds α := by
intro g hg
obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
have hq' := List.mem_range.mp hq
have hM := Nat.mul_le_mul_right (triePoolStride t b) hq'
change (q+1)*triePoolStride t b ≤ 2^(triePoolHeight t b)*triePoolStride t b at hM
rw [Nat.add_mul,Nat.one_mul] at hM
let acc := triePoolAcc pool t b q
let on := triePoolRowBase pool t b q
let out := fun j : Fin (triePoolWidth b) => triePoolBit pool t b q j.val
let cs := List.ofFn (fun i : Fin (triePoolCount t b q) =>
(triePoolEnable base n t b q i.val,fun j : Fin (triePoolWidth b) =>
triePoolPayload base n t b q i.val j.val))
have hCL : cs.length = triePoolCount t b q := by simp [cs]
have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
have hOn : α on = a on := by
apply hFr
change pool+q*triePoolStride t b < _
unfold triePoolAfter
have hp : 0 < triePoolStride t b := by unfold triePoolStride; omega
omega
have hAcc (i : ℕ) (hi : i ≤ cs.length) : α (acc i) = a (acc i) := by
apply hFr
change pool+q*triePoolStride t b+1+triePoolWidth b+i < _
unfold triePoolAfter triePoolStride at *
omega
have hOut (i : Fin (triePoolWidth b)) : α (out i) = a (out i) := by
apply hFr
change pool+q*triePoolStride t b+1+i.val < _
have := i.isLt
unfold triePoolAfter triePoolStride at *
omega
have hLow : pool ≤ triePoolAfter pool t b := Nat.le_add_right _ _
have hEn (i : Fin cs.length) : α cs[i.val].1 = a cs[i.val].1 := by
apply hFr
have hi : i.val < triePoolCount t b q := hCL ▸ i.isLt
simpa [cs] using (triePoolInput_below hBase hP hb hi).1.trans_le hLow
have hData (i : Fin cs.length) (j : Fin (triePoolWidth b)) :
α (cs[i.val].2 j) = a (cs[i.val].2 j) := by
apply hFr
have hi : i.val < triePoolCount t b q := hCL ▸ i.isLt
simpa [cs] using ((triePoolInput_below hBase hP hb hi).2 _ j.isLt).trans_le hLow
have hSat : ∀ g ∈ gatherGates on acc out cs, g.Holds a := by
intro g hg
apply h g (List.mem_flatMap.mpr ⟨q,hq,?_⟩)
rwa [triePoolCands_eq]
obtain ⟨h0,hLast,hStep⟩ := (gatherGates_local a on acc out cs).mp hSat
apply (gatherGates_local α on acc out cs).mpr ?_ g
· exact (triePoolCands_eq base pool n t b q) ▸ hg
· refine ⟨?_,?_,?_⟩
· rwa [hAcc _ (Nat.zero_le _)]
· rwa [hOn,hAcc _ le_rfl]
· intro k
rw [hAcc _ k.isLt,hAcc _ k.isLt.le,hEn k]
refine ⟨(hStep k).1,(hStep k).2.1,?_⟩
intro hp i
rw [hOut i,hData k i]
exact (hStep k).2.2 hp i
end CNFEncComplexity.Robson
/- RobsonTrieComponentComplete -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem trieSlots_frame (a β : Assignment) (n t : ℕ)
(hFr : ∀ i < sharedLimit n t, β i = a i) (h : SlotsWellFormed a n t) :
SlotsWellFormed β n t := by
apply (slotShapeGates_exact β n t).mp
intro g hg
exact (gate_congr g (fun i hi => hFr i (slotShapeGates_shared hg hi))).mpr
((slotShapeGates_exact a n t).mpr h g hg)
theorem normalizeMemoryGates_complete (a : Assignment) (base n t b : ℕ)
(hBase : sharedLimit n t ≤ base) (hb : b ≤ layoutHeight t)
(hShape : SlotsWellFormed a n t) (dict : List WordEdge) (lab : ℕ → ℕ)
(hGood : WordEdge.Interned dict) (hDict : ∀ e ∈ dict, e.child < 2^(2^b))
(hLab : ∀ x ∈ observationWords (memoryStream a n t), WordLabel (2^b) dict x (lab x)) :
∃ α : Assignment,
(∀ i, i < base ∨ normalizeMemoryEnd base t b ≤ i → α i = a i) ∧
(∀ g ∈ normalizeMemoryGates base n t b, g.Holds α) ∧
∀ s ∈ layoutSlots t, ∀ r < 3,
slotCompactMemory α base n t b s r = (portMemory a n t s r).map (compactRow lab) := by
let pool := normalizeAfter base t
let top := triePoolAfter pool t b
have hbP : base ≤ pool := Nat.le_add_right _ _
have hpT : pool ≤ top := Nat.le_add_right _ _
have hPass (start : ℕ) : start ≤ trieSortPassEnd start (2^b) (triePoolHeight t b) :=
(Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
have htD : top ≤ normalizeMemoryEnd base t b :=
(hPass top).trans (hPass (trieSortPassEnd top (2^b) (triePoolHeight t b)))
obtain ⟨β,hFβ,hGβ,hLβ,hRβ⟩ := normalizeLayout_complete a base n t b hBase dict lab hDict
(fun s hs r hr f hf hOn => hLab _ (normalizedWord_mem_input a n t s hs r f hr hf hOn))
have hSβ := trieSlots_frame a β n t
(fun i hi => hFβ i (.inl (hi.trans_le hBase))) hShape
obtain ⟨γ,hFγ,hGγ⟩ := triePool_complete β base pool n t b hBase le_rfl hb hSβ hGβ
have hRγ (s : ℕ×ℕ) (hs : s ∈ layoutSlots t) (r : ℕ) (hr : r < 3) (f : ℕ) (hf : f < 3)
(e : WordEdge) (he : e ∈ normalizeWordRows γ base n t b s r f) : e ∈ dict := by
have heq := normalizeWordRows_congr γ β base n t b s r f hs hr hf
(fun i hi => hFγ _ (.inl (normalizeWord_name_below hBase hs hr hf hi)))
exact hRβ s hs r hr f hf e (heq ▸ he)
have hDγ : WordEdge.Interned ((trieSourceRows γ (2^b) (triePoolHeight t b)
(triePoolSourceWire pool t b)).filterMap id) := by
rw [triePoolSourceWords]
exact hGood.of_subset (triePool_sound_subset γ base pool n t b hb hGγ dict hRγ)
obtain ⟨α,hFα,hGα⟩ := trieDictionaryGates_extend γ top (2^b) (triePoolHeight t b)
(triePoolSourceWire pool t b) (triePoolSourceWire_below pool t b) hDγ
have hF (i : ℕ) (hi : i < base ∨ normalizeMemoryEnd base t b ≤ i) : α i = a i := by
rcases hi with hi|hi
· exact (hFα _ (.inl (hi.trans_le (hbP.trans hpT)))).trans
((hFγ _ (.inl (hi.trans_le hbP))).trans (hFβ _ (.inl hi)))
· exact (hFα _ (.inr hi)).trans
((hFγ _ (.inr (htD.trans hi))).trans (hFβ _ (.inr ((hpT.trans htD).trans hi))))
have hLow (i : ℕ) (hi : i < pool) : α i = β i :=
(hFα _ (.inl (hi.trans_le hpT))).trans (hFγ _ (.inl hi))
refine ⟨α,hF,?_,?_⟩
· simp only [normalizeMemoryGates,List.forall_mem_append]
refine ⟨⟨?_,normalizePoolGates_frame γ α base pool n t b hBase le_rfl hb
(fun i hi => hFα _ (.inl hi)) hGγ⟩,hGα⟩
intro g hg
obtain ⟨s,hs,hm⟩ := List.mem_flatMap.mp hg
obtain ⟨r,hr,hm⟩ := List.mem_flatMap.mp hm
obtain ⟨f,hf,hm⟩ := List.mem_flatMap.mp hm
apply (gate_congr g (fun i hi => hLow _ (normalizeWord_name_below hBase hs
(List.mem_range.mp hr) (List.mem_range.mp hf)
(normalizeWordGates_frame base n t b s r f hs (List.mem_range.mp hr)
(List.mem_range.mp hf) g hm i hi)))).mpr
exact hGβ g hg
· intro s hs r hr
apply slotCompactMemory_witness a α base n t b s hs r hr lab
(fun i hi => hF _ (.inl (hi.trans_le hBase)))
intro f hf hOn
exact (normalizeSlotLabel_frame α β base n t b hBase s hs r f hr hf hLow).trans
(hLβ s hs r hr f hf hOn)
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).