Uniform generation of the RAM trie dictionary
DefinitionCNFEncComplexity_RobsonMemoryTrieDictionarycomplexity-theorysatisfiability
Polynomial-time generation of the routing, pooled trie, word-label dictionary, and normalization gate lists.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieDictionarySoundness
import Definitions.Def_CNFEncComplexity_RobsonMemoryParameters
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonTrieDictNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
private theorem posNegLit_poly (positive : Bool) {name : A → ℕ}
(h : ComputableTidilyInPolyTime name e encUnary) :
ComputableTidilyInPolyTime (fun x => literalN (if positive then .Pos (name x) else .Neg (name x)))
e encUnary := by
cases positive
· exact unary_mul.comp ((const 2).prod h)
· exact unary_add.comp ((unary_mul.comp ((const 2).prod h)).prod (const 1))
private theorem pairAssert₂ (s₁ s₂ : Bool) {x y : A → ℕ}
(hx : ComputableTidilyInPolyTime x e encUnary) (hy : ComputableTidilyInPolyTime y e encUnary) :
ComputableTidilyInPolyTime (fun p => .assert [if s₁ then .Pos (x p) else .Neg (x p),
if s₂ then .Pos (y p) else .Neg (y p)] : A → Gate) e gateEnc := by
exact gate_assert (cons' (posNegLit_poly s₁ hx) (cons' (posNegLit_poly s₂ hy) (const [])))
private theorem pairAssert₃ (s₁ s₂ s₃ : Bool) {x y z : A → ℕ}
(hx : ComputableTidilyInPolyTime x e encUnary) (hy : ComputableTidilyInPolyTime y e encUnary)
(hz : ComputableTidilyInPolyTime z e encUnary) :
ComputableTidilyInPolyTime (fun p => .assert [if s₁ then .Pos (x p) else .Neg (x p),
if s₂ then .Pos (y p) else .Neg (y p),if s₃ then .Pos (z p) else .Neg (z p)] : A → Gate) e gateEnc :=
gate_assert (cons' (posNegLit_poly s₁ hx) (cons' (posNegLit_poly s₂ hy)
(cons' (posNegLit_poly s₃ hz) (const []))))
private theorem trieSortWidth_poly (c : Bool) {B : A → ℕ}
(hB : ComputableTidilyInPolyTime B e encUnary) :
ComputableTidilyInPolyTime (fun x => trieSortWidth (B x) c) e encUnary := by
cases c
· exact unary_add.comp (hB.prod hB)
· exact hB
private theorem trieSortWire_poly (c : Bool) {B : A → ℕ} {src : A → ℕ → ℕ}
(hB : ComputableTidilyInPolyTime B e encUnary)
(hSrc : ComputableTidilyInPolyTime (fun p : A×ℕ => src p.1 p.2) (encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime
(fun p : A×ℕ => trieSortWire (B p.1) c (trieRowFromNat (B p.1) (src p.1)) p.2)
(encPair e encUnary) encUnary := by
let X := fst e encUnary
let I := snd e encUnary
have hBB := hB.comp X
have hsP : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+(p.2-B p.1))
(encPair e encUnary) encUnary := by fun_prop
have hsD : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+B p.1+p.2)
(encPair e encUnary) encUnary := by fun_prop
have hsC : ComputableTidilyInPolyTime (fun p : A×ℕ => 1+2*B p.1+p.2)
(encPair e encUnary) encUnary := by fun_prop
cases c
· have hp := hSrc.comp (X.prod hsP)
have hd := hSrc.comp (X.prod hsD)
have ht := (unary_lt' I hBB).ite' hd hp
simpa only [trieSortWire,trieRowFromNat,joinKey,Function.comp_def,decide_eq_true_eq,
Bool.false_eq_true,if_false] using ht
· exact hSrc.comp (X.prod hsC)
private theorem trieRowPair_poly (c : Bool) {base B : A → ℕ} {l r : A → ℕ → ℕ}
(hq : ComputableTidilyInPolyTime base e encUnary)
(hB : ComputableTidilyInPolyTime B e encUnary)
(hL : ComputableTidilyInPolyTime (fun p : A×ℕ => l p.1 p.2) (encPair e encUnary) encUnary)
(hR : ComputableTidilyInPolyTime (fun p : A×ℕ => r p.1 p.2) (encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => trieRowPair (base a) (B a) c
(trieRowFromNat (B a) (l a)) (trieRowFromNat (B a) (r a))) e (encList gateEnc) := by
let n := fun x => trieSortWidth (B x) c
let m := fun x => trieSortWidth (B x) (!c)
let next := fun x => base x+4*(n x+1)
let PL := fun x => trieSortWire (B x) c (trieRowFromNat (B x) (l x))
let PR := fun x => trieSortWire (B x) c (trieRowFromNat (B x) (r x))
let QL := fun x => trieSortWire (B x) (!c) (trieRowFromNat (B x) (l x))
let QR := fun x => trieSortWire (B x) (!c) (trieRowFromNat (B x) (r x))
have hn : ComputableTidilyInPolyTime n e encUnary := trieSortWidth_poly c hB
have hm : ComputableTidilyInPolyTime m e encUnary := trieSortWidth_poly (!c) hB
have hnxt : ComputableTidilyInPolyTime next e encUnary := by unfold next; fun_prop
have hP := compareCircuit_polytime (lhs := PL) (rhs := PR) hq hn
(trieSortWire_poly c hB hL) (trieSortWire_poly c hB hR)
have hQ := compareCircuit_polytime (lhs := QL) (rhs := QR) hnxt hm
(trieSortWire_poly (!c) hB hL) (trieSortWire_poly (!c) hB hR)
have hl := hL.comp ((id' (encIn := e)).prod (const 0))
have hr := hR.comp ((id' (encIn := e)).prod (const 0))
have ht : ComputableTidilyInPolyTime (fun x => ltWire (base x) (n x)) e encUnary := by
unfold ltWire; fun_prop
have he : ComputableTidilyInPolyTime (fun x => eqWire (base x) (n x)) e encUnary := by
unfold eqWire; fun_prop
have he₂ : ComputableTidilyInPolyTime (fun x => eqWire (next x) (m x)) e encUnary := by
unfold eqWire; fun_prop
exact listAppend' (listAppend' hP hQ)
(cons' (pairAssert₂ true false hl hr) (cons' (pairAssert₃ false true true hr ht he)
(cons' (pairAssert₃ false false true hr he he₂) (const []))))
end
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
private theorem trieSortCheckOfFn (base B : ℕ) (c : Bool) (n : ℕ) (row : ℕ → TrieRowPort) :
trieSortCheckGates B c base (List.ofFn fun i : Fin n => row i.val) =
(List.range (n-1)).flatMap fun i => trieRowPair (base+i*triePairSpan B) B c (row i) (row (i+1)) := by
induction n generalizing base row with
| zero => simp [trieSortCheckGates]
| succ m ih =>
cases m with
| zero => simp [List.ofFn_succ,trieSortCheckGates]
| succ k =>
rw [List.ofFn_succ]
have hh : List.ofFn (fun i : Fin (k+1) => row (i.val+1)) =
row 1 :: List.ofFn (fun i : Fin k => row (i.val+1+1)) := by
rw [List.ofFn_succ]
rfl
change trieSortCheckGates B c base (row 0::List.ofFn (fun i : Fin (k+1) => row (i.val+1))) = _
rw [hh,trieSortCheckGates]
have ih' := ih (base+triePairSpan B) (fun j => row (j+1))
simp only [List.ofFn_succ,Fin.val_zero,Fin.val_succ,Nat.zero_add] at ih'
rw [ih']
simp only [Nat.add_sub_cancel, List.range_succ_eq_map,List.flatMap_cons,List.flatMap_map,
Function.comp_def,Nat.zero_mul,Nat.add_zero]
congr 1
apply List.flatMap_congr
intro j hj
have eq : base+triePairSpan B+j*triePairSpan B = base+(j+1)*triePairSpan B := by ring
rw [eq]
section
variable {A : Type} {e : A ↪ List Bool}
private theorem trieRouteEnd_poly {base B h : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hB : ComputableTidilyInPolyTime B e encUnary)
(hH : ComputableTidilyInPolyTime h e encUnary)
(hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary) :
ComputableTidilyInPolyTime (fun x => trieRouteEnd (base x) (B x) (h x)) e encUnary := by
unfold trieRouteEnd trieRowWidth
simp only [auxCount_exact]
fun_prop
theorem trieSortPassEnd_poly {base B h : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hB : ComputableTidilyInPolyTime B e encUnary)
(hH : ComputableTidilyInPolyTime h e encUnary)
(hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary) :
ComputableTidilyInPolyTime (fun x => trieSortPassEnd (base x) (B x) (h x)) e encUnary := by
have hE := trieRouteEnd_poly hBase hB hH hN
unfold trieSortPassEnd triePairSpan
fun_prop
set_option maxHeartbeats 1000000 in
theorem trieSortPass_polytime (c : Bool) {base B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hB : ComputableTidilyInPolyTime B e encUnary)
(hH : ComputableTidilyInPolyTime h e encUnary)
(hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
(hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => trieSortPass (base x) (B x) (h x) c (src x))
e (encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
let X := fst e encUnary
let Q := snd e encUnary
let Y := fst e₁ encUnary
let I := snd e₁ encUnary
let D := fun x => trieRowWidth (B x)
have hD : ComputableTidilyInPolyTime D e encUnary := by unfold D trieRowWidth; fun_prop
have hX2 := X.comp Y
have hQ2 := Q.comp Y
have hStart := unary_add.comp (((hBase.comp hX2)).prod
(unary_mul.comp (hQ2.prod (hD.comp hX2))))
have hIn : ComputableTidilyInPolyTime
(fun p : (A×ℕ)×ℕ => trieRouteIn (base p.1.1) (B p.1.1) p.1.2 p.2) e₂ encUnary :=
unary_add.comp (hStart.prod I)
have hLines := mapWithInput (f := fun (p : A×ℕ) i =>
Gate.copy (trieRouteIn (base p.1) (B p.1) p.2 i) (src p.1 p.2 i))
(range.comp (hD.comp X)) (gate_copy hIn hSrc)
have hAttach := flatMapWithInput (f := fun x q => wordCopy (D x) (trieRouteIn (base x) (B x) q) (src x q))
(range.comp hN) hLines
have hRoute' := boundedRouteGates_poly.comp (hD.prod (hH.prod (hBase.prod hN)))
have hRoute : ComputableTidilyInPolyTime (fun x => routeNamedGates (trieRouteName (base x) (B x) (h x)))
e (encList gateEnc) := by
convert hRoute' using 1
funext x
change routeNamedGates (fun v => base x+(routeLabel (h x) (D x) v).val) = _
exact (boundedRouteGates_eq (D x) (h x) (base x) (2^h x) le_rfl).symm
have hEnd := trieRouteEnd_poly hBase hB hH hN
have hSpan : ComputableTidilyInPolyTime (fun x => triePairSpan (B x)) e encUnary := by unfold triePairSpan; fun_prop
have hScratch : ComputableTidilyInPolyTime
(fun p : A×ℕ => trieRouteEnd (base p.1) (B p.1) (h p.1)+p.2*triePairSpan (B p.1)) e₁ encUnary :=
unary_add.comp ((hEnd.comp X).prod (unary_mul.comp (Q.prod (hSpan.comp X))))
have hOutBase := unary_add.comp ((hBase.comp hX2).prod ((unary_mul.comp (hN.prod hD)).comp hX2))
have hL : ComputableTidilyInPolyTime
(fun p : (A×ℕ)×ℕ => trieRouteOut (base p.1.1) (B p.1.1) (h p.1.1) p.1.2 p.2) e₂ encUnary :=
unary_add.comp ((unary_add.comp (hOutBase.prod
(unary_mul.comp (hQ2.prod (hD.comp hX2))))).prod I)
have hQsucc := unary_add.comp (hQ2.prod (const 1))
have hR : ComputableTidilyInPolyTime
(fun p : (A×ℕ)×ℕ => trieRouteOut (base p.1.1) (B p.1.1) (h p.1.1) (p.1.2+1) p.2) e₂ encUnary :=
unary_add.comp ((unary_add.comp (hOutBase.prod
(unary_mul.comp (hQsucc.prod (hD.comp hX2))))).prod I)
have hPairs := trieRowPair_poly c
(l := fun p i => trieRouteOut (base p.1) (B p.1) (h p.1) p.2 i)
(r := fun p i => trieRouteOut (base p.1) (B p.1) (h p.1) (p.2+1) i)
hScratch (hB.comp X) hL hR
have hN1 := unary_sub.comp (hN.prod (const 1))
have hCheck := flatMapWithInput (f := fun x i => trieRowPair
(trieRouteEnd (base x) (B x) (h x)+i*triePairSpan (B x)) (B x) c
(trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) i))
(trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) (i+1))))
(range.comp hN1) hPairs
have hAll := listAppend' (listAppend' hAttach hRoute) hCheck
convert hAll using 1
funext x
simp only [trieSortPass,trieRouteCopy,trieRouteRows,Function.comp_def,D]
rw [trieSortCheckOfFn (trieRouteEnd (base x) (B x) (h x)) (B x) c (2^h x)
(fun q => trieRowFromNat (B x) (trieRouteOut (base x) (B x) (h x) q))]
set_option maxHeartbeats 1000000 in
private theorem trieNonzeroList_poly {B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hB : ComputableTidilyInPolyTime B e encUnary)
(hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
(hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => trieNonzeroList (B x) (h x) (src x))
e (encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
let X := fst e encUnary
let Y := fst e₁ encUnary
have hOn := hSrc.comp ((id' (encIn := e₁)).prod (const 0))
have hi : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => 1+2*B p.1.1+p.2) e₂ encUnary := by
unfold e₂ e₁
fun_prop
have hChild := hSrc.comp (Y.prod hi)
have hNeg := posNegLit_poly false hOn
have hPos := posNegLit_poly true hChild
have hBits := mapWithInput
(f := fun (p : A×ℕ) i => literalN (.Pos (src p.1 p.2 (1+2*B p.1+i))))
(range.comp (hB.comp X)) hPos
have hGate := gate_assert (c := fun p : A×ℕ => .Neg (src p.1 p.2 0) ::
(List.range (B p.1)).map (fun i => .Pos (src p.1 p.2 (1+2*B p.1+i)))) (by
simpa [clauseN,List.map_map,Function.comp_def] using cons' hNeg hBits)
have hClause := cons' hGate (const [])
exact flatMapWithInput (f := fun x q => trieNonzeroGates (B x) (trieRowFromNat (B x) (src x q)))
(range.comp hN) hClause
theorem trieDictionaryGates_polytime {base B h : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hB : ComputableTidilyInPolyTime B e encUnary)
(hH : ComputableTidilyInPolyTime h e encUnary)
(hN : ComputableTidilyInPolyTime (fun x => 2^h x) e encUnary)
(hSrc : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => trieDictionaryGates (base x) (B x) (h x) (src x))
e (encList gateEnc) := by
have hBase' := trieSortPassEnd_poly hBase hB hH hN
exact listAppend' (listAppend' (trieNonzeroList_poly (src := src) hB hN hSrc)
(trieSortPass_polytime (src := src) false hBase hB hH hN hSrc))
(trieSortPass_polytime (src := src) true hBase' hB hH hN hSrc)
end
end CNFEncComplexity.Robson
/- RobsonTriePoolNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
theorem triePoolLanes_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary) :
ComputableTidilyInPolyTime (fun x => triePoolLanes (t x) (b x)) e encUnary :=
unary_pow2_of_bound (unary_sub.comp ((layoutHeight_poly.comp hT).prod hB))
(layoutHorizon_poly.comp hT) (fun _ => Nat.pow_le_pow_right (by decide) (Nat.sub_le ..))
theorem triePoolHeight_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary) :
ComputableTidilyInPolyTime (fun x => triePoolHeight (t x) (b x)) e encUnary :=
unary_add.comp ((unary_sub.comp ((layoutHeight_poly.comp hT).prod hB)).prod (const 4))
theorem triePoolRows_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary) :
ComputableTidilyInPolyTime (fun x => 2^triePoolHeight (t x) (b x)) e encUnary := by
convert unary_mul.comp ((triePoolLanes_poly hT hB).prod (const 16)) using 1
funext x
exact pow_add (2:ℕ) _ _
theorem triePoolLevels_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary) :
ComputableTidilyInPolyTime (fun x => triePoolLevels (t x) (b x)) e encUnary :=
unary_sub.comp ((unary_add.comp ((layoutHeight_poly.comp hT).prod (const 1))).prod hB)
theorem triePoolCount_poly {t b q : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hQ : ComputableTidilyInPolyTime q e encUnary) :
ComputableTidilyInPolyTime (fun x => triePoolCount (t x) (b x) (q x)) e encUnary := by
have hp := unary_div_poly.comp (hQ.prod (triePoolLanes_poly hT hB))
have ht := (unary_lt' hp (const 9)).ite' (triePoolLevels_poly hT hB) (const 0)
simpa only [triePoolCount,decide_eq_true_eq,Function.comp_def] using ht
private theorem triePoolPower_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => 2^b x) e encUnary :=
unary_pow2_of_bound hB (layoutHorizon_poly.comp hT) (fun x => Nat.pow_le_pow_right (by decide) (hBnd x))
theorem triePoolWidth_poly {t b : A → ℕ}
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolWidth (b x)) e encUnary :=
unary_mul.comp ((const 3).prod (triePoolPower_poly hT hB hBnd))
theorem triePoolAfter_poly {pool t b : A → ℕ}
(hP : ComputableTidilyInPolyTime pool e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolAfter (pool x) (t x) (b x)) e encUnary := by
have hW := triePoolWidth_poly hT hB hBnd
have hL := triePoolLevels_poly hT hB
have hN := triePoolRows_poly hT hB
unfold triePoolAfter triePoolStride
fun_prop
private def trieCapLevel (t b j : ℕ) : ℕ := min j (layoutHeight t-b)
private theorem trieCapLevel_eq {t b q j : ℕ} (hb : b ≤ layoutHeight t)
(hj : j < triePoolCount t b q) : trieCapLevel t b j = j := by
have hN : triePoolCount t b q ≤ triePoolLevels t b := by
unfold triePoolCount
split <;> omega
unfold trieCapLevel triePoolLevels at *
apply min_eq_left
omega
set_option maxHeartbeats 2000000 in
private theorem triePoolWordScalars_poly {base n t b q j : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hQ : ComputableTidilyInPolyTime q e encUnary)
(hJ : ComputableTidilyInPolyTime j e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x))
(hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
let src : A → (ℕ×ℕ) × ℕ × ℕ × ℕ := fun x => triePoolSource (t x) (b x) (q x) (j x)
∃ hS : ComputableTidilyInPolyTime (fun x => (src x).1.1) e encUnary,
∃ hD : ComputableTidilyInPolyTime (fun x => (src x).1.2) e encUnary,
∃ hR : ComputableTidilyInPolyTime (fun x => (src x).2.1) e encUnary,
∃ hF : ComputableTidilyInPolyTime (fun x => (src x).2.2.1) e encUnary,
∃ hI : ComputableTidilyInPolyTime (fun x => (src x).2.2.2) e encUnary,
ComputableTidilyInPolyTime (fun x => normalizeWordBase (base x) (t x)
(src x).1 (src x).2.1 (src x).2.2.1) e encUnary := by
dsimp only
let N := fun x => triePoolLanes (t x) (b x)
let K := fun x => (2:ℕ)^j x
let W := fun x => (2:ℕ)^(b x+j x)
have hp := triePoolLanes_poly hT hB
have hH := layoutHeight_poly.comp hT
have hW' := layoutHorizon_poly.comp hT
have hK : ComputableTidilyInPolyTime K e encUnary :=
unary_pow2_of_bound hJ hW' (fun x => Nat.pow_le_pow_right (by decide)
((Nat.le_add_left _ _).trans (hJnd x)))
have hW : ComputableTidilyInPolyTime W e encUnary :=
unary_pow2_of_bound (unary_add.comp (hB.prod hJ)) hW' (fun x =>
Nat.pow_le_pow_right (by decide) (hJnd x))
have hDiv := unary_div_poly.comp (hQ.prod hp)
have hMod := unary_mod_poly.comp (hQ.prod hp)
have hR := unary_div_poly.comp (hDiv.prod (const 3))
have hF := unary_mod_poly.comp (hDiv.prod (const 3))
have hS := unary_mul.comp ((unary_div_poly.comp (hMod.prod hK)).prod hW)
have hD := unary_add.comp (hB.prod hJ)
have hI := unary_mod_poly.comp (hMod.prod hK)
have hS' : ComputableTidilyInPolyTime (fun x => (triePoolSource (t x) (b x) (q x) (j x)).1.1) e encUnary := by
apply hS.of_enc_eq
intro x
apply congrArg encUnary
simp only [triePoolSource,chunkLaneSource,Nat.add_sub_cancel_left,Function.comp_def,W,K]
have hI' : ComputableTidilyInPolyTime (fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.2) e encUnary := by
apply hI.of_enc_eq
intro x
apply congrArg encUnary
simp only [triePoolSource,chunkLaneSource,Nat.add_sub_cancel_left,Function.comp_def,K]
refine ⟨hS',hD,hR,hF,hI',?_⟩
have hStride : ComputableTidilyInPolyTime (fun x => normalizeStride (t x)) e encUnary :=
unary_add.comp ((unary_mul.comp ((const 6).prod hW')).prod (const 4))
have hHeight1 := unary_add.comp (hH.prod (const 1))
have hSlot := unary_add.comp ((unary_mul.comp (hS'.prod hHeight1)).prod hD)
have hRow := unary_add.comp ((unary_mul.comp (hSlot.prod (const 3))).prod hR)
have hField := unary_add.comp ((unary_mul.comp (hRow.prod (const 3))).prod hF)
exact unary_add.comp (hBase.prod (unary_mul.comp (hField.prod hStride)))
private theorem triePoolEnable_poly {base n t b q j : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hQ : ComputableTidilyInPolyTime q e encUnary)
(hJ : ComputableTidilyInPolyTime j e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x))
(hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolEnable (base x) (n x) (t x) (b x) (q x) (j x))
e encUnary := by
obtain ⟨hs,hd,hr,hf,hi,hL⟩ :=
triePoolWordScalars_poly hBase hN hT hB hQ hJ hBnd hJnd
have hW := unary_pow2_of_bound hd (layoutHorizon_poly.comp hT)
(fun x => Nat.pow_le_pow_right (by decide) (hJnd x))
exact unary_add.comp ((unary_add.comp ((unary_add.comp (hL.prod hW)).prod (const 2))).prod hi)
private theorem triePoolPayload_poly {base n t b q j i : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hQ : ComputableTidilyInPolyTime q e encUnary)
(hJ : ComputableTidilyInPolyTime j e encUnary)
(hI : ComputableTidilyInPolyTime i e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x))
(hJnd : ∀ x, b x+j x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolPayload (base x) (n x) (t x) (b x) (q x) (j x) (i x))
e encUnary := by
let s := fun x => (triePoolSource (t x) (b x) (q x) (j x)).1
let r := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.1
let f := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.1
let k := fun x => (triePoolSource (t x) (b x) (q x) (j x)).2.2.2
let L := fun x => normalizeWordBase (base x) (t x) (s x) (r x) (f x)
let W := fun x => (2:ℕ)^(s x).2
let K := fun x => (2:ℕ)^((s x).2-b x)
let B := fun x => (2:ℕ)^b x
obtain ⟨hs,hd,hr,hf,hk,hL⟩ :=
triePoolWordScalars_poly hBase hN hT hB hQ hJ hBnd hJnd
have hL' : ComputableTidilyInPolyTime L e encUnary := hL
have hK : ComputableTidilyInPolyTime K e encUnary :=
unary_pow2_of_bound (unary_sub.comp (hd.prod hB)) (layoutHorizon_poly.comp hT)
(fun x => Nat.pow_le_pow_right (by decide) ((Nat.sub_le ..).trans (hJnd x)))
have hW : ComputableTidilyInPolyTime W e encUnary :=
unary_pow2_of_bound hd (layoutHorizon_poly.comp hT)
(fun x => Nat.pow_le_pow_right (by decide) (hJnd x))
have hBP : ComputableTidilyInPolyTime B e encUnary := triePoolPower_poly hT hB hBnd
have hk' : ComputableTidilyInPolyTime k e encUnary := hk
have hr' : ComputableTidilyInPolyTime r e encUnary := hr
have hf' : ComputableTidilyInPolyTime f e encUnary := hf
have hTwoW := unary_mul.comp ((const 2).prod hW)
have hTwoB := unary_mul.comp ((const 2).prod hBP)
have hKB := unary_mul.comp (hk'.prod hBP)
have hField := unary_add.comp ((unary_add.comp ((const 5).prod
(unary_mul.comp ((const 5).prod hr')))).prod hf')
have hParent : ComputableTidilyInPolyTime (fun x => L x+W x+2+K x+k x*B x+i x) e encUnary :=
unary_add.comp ((unary_add.comp ((unary_add.comp ((unary_add.comp
((unary_add.comp (hL'.prod hW)).prod (const 2))).prod hK)).prod hKB)).prod hI)
have hChild : ComputableTidilyInPolyTime
(fun x => L x+2*W x+2+K x+k x*B x+(i x-2*B x)) e encUnary :=
unary_add.comp ((unary_add.comp ((unary_add.comp ((unary_add.comp
((unary_add.comp (hL'.prod hTwoW)).prod (const 2))).prod hK)).prod hKB)).prod
(unary_sub.comp (hI.prod hTwoB)))
have hRaw : ComputableTidilyInPolyTime (fun x => port (n x) (t x)
((s x).1,(s x).2) (5+5*r x+f x) (k x*B x+(i x-B x))) e encUnary :=
slotPort_poly hN hT hs hd hField (unary_add.comp (hKB.prod (unary_sub.comp (hI.prod hBP))))
have hTest := unary_lt' hI hBP
have hTest' := unary_lt' hI (unary_mul.comp ((const 2).prod hBP))
have h := hTest.ite' hParent (hTest'.ite' hRaw hChild)
simpa only [triePoolPayload,triePoolWire,normalizeSlotWires,trieWiresAt,s,r,f,k,L,W,K,B,
Function.comp_def,decide_eq_true_eq] using h
end
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
set_option maxHeartbeats 2000000 in
private theorem triePoolLaneGates_poly {base pool n t b q : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hPool : ComputableTidilyInPolyTime pool e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hQ : ComputableTidilyInPolyTime q e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolLaneGates (base x) (pool x) (n x) (t x) (b x) (q x))
e (encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
let jCap := fun x j => trieCapLevel (t x) (b x) j
let enable := fun x j => triePoolEnable (base x) (n x) (t x) (b x) (q x) (jCap x j)
let payload := fun x j i => triePoolPayload (base x) (n x) (t x) (b x) (q x) (jCap x j) i
have hX := fst e encUnary
have hJ := snd e encUnary
have hY := fst e₁ encUnary
have hI := snd e₁ encUnary
have hW := triePoolWidth_poly hT hB hBnd
have hM := triePoolCount_poly hT hB hQ
have hLev := triePoolLevels_poly hT hB
have hStride := unary_add.comp ((unary_add.comp (hW.prod hLev)).prod (const 2))
have hAcc0 : ComputableTidilyInPolyTime (fun x => triePoolRowBase (pool x) (t x) (b x) (q x))
e encUnary := unary_add.comp (hPool.prod (unary_mul.comp (hQ.prod hStride)))
have hArr := unary_add.comp ((hAcc0.comp hX).prod (const 1))
have hAcc : ComputableTidilyInPolyTime (fun x : A×ℕ => triePoolAcc (pool x.1) (t x.1) (b x.1) (q x.1) x.2)
e₁ encUnary := unary_add.comp ((unary_add.comp (hArr.prod (hW.comp hX))).prod hJ)
have hOut : ComputableTidilyInPolyTime (fun x : A×ℕ => triePoolBit (pool x.1) (t x.1) (b x.1) (q x.1) x.2)
e₁ encUnary := unary_add.comp (hArr.prod hJ)
have hCap : ComputableTidilyInPolyTime (fun x : A×ℕ => jCap x.1 x.2) e₁ encUnary :=
unary_min.comp (hJ.prod (unary_sub.comp ((layoutHeight_poly.comp (hT.comp hX)).prod (hB.comp hX))))
have hCapBnd (x : A) (j : ℕ) : b x+jCap x j ≤ layoutHeight (t x) := by
have hh : jCap x j ≤ layoutHeight (t x)-b x := min_le_right ..
have hb := hBnd x
omega
have hEnable : ComputableTidilyInPolyTime (fun x : A×ℕ => enable x.1 x.2) e₁ encUnary :=
triePoolEnable_poly (hBase.comp hX) (hN.comp hX) (hT.comp hX) (hB.comp hX)
(hQ.comp hX) hCap (fun x => hBnd x.1) (fun x => hCapBnd x.1 x.2)
have hX' := hX.comp hY
have hPayload : ComputableTidilyInPolyTime (fun x : (A×ℕ)×ℕ => payload x.1.1 x.1.2 x.2) e₂ encUnary :=
triePoolPayload_poly (hBase.comp hX') (hN.comp hX') (hT.comp hX') (hB.comp hX')
(hQ.comp hX') (hCap.comp hY) hI (fun x => hBnd x.1.1) (fun x => hCapBnd x.1.1 x.1.2)
have hAll := gatherArray_poly
(acc := fun x i => triePoolAcc (pool x) (t x) (b x) (q x) i)
(out := fun x i => triePoolBit (pool x) (t x) (b x) (q x) i)
(enable := enable) (payload := payload) hW hM hAcc0 hAcc hOut hEnable hPayload
convert hAll using 1
funext x
unfold triePoolLaneGates gatherArray
congr 1
apply List.flatMap_congr
intro j hj
have hex := trieCapLevel_eq (hBnd x) (List.mem_range.mp hj)
simp [enable,payload,jCap,hex]
theorem triePoolGateList_polytime {base pool n t b : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hPool : ComputableTidilyInPolyTime pool e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hBnd : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => triePoolGateList (base x) (pool x) (n x) (t x) (b x))
e (encList gateEnc) := by
let hX := fst e encUnary
exact flatMapWithInput (f := fun x q => triePoolLaneGates (base x) (pool x) (n x) (t x) (b x) q)
(range.comp (triePoolRows_poly hT hB))
(triePoolLaneGates_poly (hBase.comp hX) (hPool.comp hX) (hN.comp hX) (hT.comp hX)
(hB.comp hX) (snd e encUnary) (fun x => hBnd x.1))
end
end CNFEncComplexity.Robson
/- RobsonMemPackedLocal -/
namespace CNFEncComplexity.Robson
open CookLevin
def rawOptions (α : Assignment) (n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
(List.range 3).map (portMemory α n t s)
theorem rawOptions_filter (α : Assignment) (n t : ℕ) (s : ℕ×ℕ) :
(rawOptions α n t s).filterMap id = slotRows α n t s := by
simp [rawOptions,slotRows,List.filterMap_map,Function.comp_def]
def relabelOptions (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
List (Option ObservedAccess) := (rawOptions α n t s).map (Option.map (compactRow label))
private theorem map_opt_filter {A B : Type} (f : A → B) (l : List (Option A)) :
((l.map (Option.map f)).filterMap id) = (l.filterMap id).map f := by
induction l with
| nil => rfl
| cons x xs ih =>
cases x
· exact ih
· rename_i x
exact congrArg (List.cons (f x)) ih
theorem relabelOptions_filter (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
(relabelOptions α n t label s).filterMap id = (slotRows α n t s).map (compactRow label) := by
rw [relabelOptions,map_opt_filter,rawOptions_filter]
theorem relabelOptions_length (α : Assignment) (n t : ℕ) (label : ℕ → ℕ) (s : ℕ×ℕ) :
(relabelOptions α n t label s).length = 3 := by simp [relabelOptions,rawOptions]
private theorem observationWords_in {α : Assignment} {n t : ℕ} {s : ℕ×ℕ}
(hs : s ∈ layoutSlots t) {x : ℕ} (hx : x ∈ observationWords (slotRows α n t s)) :
x ∈ observationWords (memoryStream α n t) := by
obtain ⟨r,hr,hval⟩ := List.mem_flatMap.mp hx
exact List.mem_flatMap.mpr ⟨r,List.mem_flatMap.mpr ⟨s,hs,hr⟩,hval⟩
private theorem memoryWord_fits {α : Assignment} {n t : ℕ} {x : ℕ}
(hx : x ∈ observationWords (memoryStream α n t)) : x.size ≤ layoutHorizon t := by
obtain ⟨e,he,hword⟩ := List.mem_flatMap.mp hx
obtain ⟨s,hs,he'⟩ := List.mem_flatMap.mp he
obtain ⟨i,_,he'⟩ := List.mem_filterMap.mp he'
obtain ⟨ha,hv,ho⟩ := portMemory_sizes he'
rcases s with ⟨start,k⟩
obtain ⟨_,hk,_⟩ := layout_mem.mp hs
have hW : 2^k ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hk
simp only [List.mem_cons,List.mem_nil_iff,or_false] at hword
rcases hword with rfl|rfl|rfl
· exact ha.trans hW
· exact hv.trans hW
· exact ho.trans hW
theorem memoryPacking_exists {α : Assignment} {n t b : ℕ} (h : SlotsWellFormed α n t)
(hb : 0 < b) (hAllow : layoutHorizon t ≤ b ∨ 18*layoutHorizon t < 2^b) :
∃ (dict : List WordEdge) (label : ℕ → ℕ),
WordEdge.Interned dict ∧ label 0=0 ∧
(∀ e ∈ dict, max e.parent e.child < 2^b) ∧
b*dict.length ≤ 18*layoutHorizon t ∧
(∀ x ∈ observationWords (memoryStream α n t), WordLabel b dict x (label x)) ∧
PackedSlots α n t b dict (fun s => (relabelOptions α n t label s).filterMap id) := by
have hCore : ∃ (dict : List WordEdge) (label : ℕ → ℕ),
WordEdge.Interned dict ∧ label 0=0 ∧
(∀ e ∈ dict, max e.parent e.child < 2^b) ∧
b*dict.length ≤ 18*layoutHorizon t ∧
(∀ x ∈ observationWords (memoryStream α n t), WordLabel b dict x (label x)) := by
rcases hAllow with hAll|hIds
· refine ⟨[],fun x => 2*x,?_,by simp,by simp,by simp,?_⟩
· exact ⟨by simp,by simp,by simp⟩
· intro x hx
exact .small ((memoryWord_fits hx).trans hAll)
· have hw := memoryStream_word_budget h
have h2 : 2*(9*layoutHorizon t) < 2^b := by omega
obtain ⟨d,l,hG,hZero,hNum,hBound,hWords⟩ := wordLabels_exist_bounded _ hw b hb h2
have hSize := (Nat.mul_le_mul_left b hNum).trans ((labelEntries_budget hb _).trans
(Nat.mul_le_mul_left 2 hw))
exact ⟨d,l,hG,hZero,hBound,by omega,fun x hx => (hWords x hx).1⟩
obtain ⟨d,l,hG,hZero,hId,hCount,hWord⟩ := hCore
refine ⟨d,l,hG,hZero,hId,hCount,hWord,⟨?_,?_⟩⟩
· intro s hs
rw [relabelOptions_filter]
exact compactRows_labels (fun x hx => hWord x (observationWords_in hs hx))
· intro s hs row hr
rw [relabelOptions_filter] at hr
obtain ⟨raw,hRaw,rfl⟩ := List.mem_map.mp hr
obtain ⟨i,_,hm⟩ := List.mem_filterMap.mp hRaw
obtain ⟨ha,hv,ho⟩ := portMemory_sizes hm
have hx (x : ℕ) (hx : x ∈ [raw.action.address,raw.action.value,raw.old]) :
(l x).size ≤ b+1 ∧ (l x).size ≤ x.size+1 :=
(hWord x (observationWords_in hs (List.mem_flatMap.mpr ⟨raw,hRaw,hx⟩))).size_le
(fun e he => (le_max_right ..).trans_lt (hId e he))
have hl (x : ℕ) (hx' : x ∈ [raw.action.address,raw.action.value,raw.old]) (hw : x.size ≤ 2^s.2) :
(l x).size ≤ min (2^s.2) b+1 := by
obtain ⟨hb,hc⟩ := hx x hx'
calc
_ ≤ min (2^s.2+1) (b+1) :=
le_min ((hc.trans (Nat.add_le_add_right hw _))) hb
_ = _ := by rw [Nat.add_min_add_right]
exact ⟨hl _ (by simp) ha,hl _ (by simp) hv,hl _ (by simp) ho⟩
end CNFEncComplexity.Robson
/- RobsonTrieComponentNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
theorem normalizeAfter_polytime {base t : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary) :
ComputableTidilyInPolyTime (fun x => normalizeAfter (base x) (t x)) e encUnary := by
have hH := layoutHorizon_poly.comp hT
have hJ := unary_add.comp ((layoutHeight_poly.comp hT).prod (const 1))
have hSlots := unary_mul.comp ((unary_mul.comp (hH.prod hJ)).prod (const 9))
have hStride := unary_add.comp ((unary_mul.comp ((const 6).prod hH)).prod (const 4))
exact unary_add.comp (hBase.prod (unary_mul.comp (hSlots.prod hStride)))
theorem triePoolSourceWire_polytime {pool t b : A → ℕ}
(hP : ComputableTidilyInPolyTime pool e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hCap : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun p : (A × ℕ) × ℕ =>
triePoolSourceWire (pool p.1.1) (t p.1.1) (b p.1.1) p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary := by
let ep := encPair e encUnary
have hA := fst e encUnary
have hQ := snd e encUnary
have hP' := hP.comp hA
have hW := triePoolWidth_poly (hT.comp hA) (hB.comp hA) (fun p => hCap p.1)
have hL := triePoolLevels_poly (hT.comp hA) (hB.comp hA)
have hStride := unary_add.comp ((unary_add.comp (hW.prod hL)).prod (const 2))
have hRow : ComputableTidilyInPolyTime (fun p : A × ℕ =>
triePoolRowBase (pool p.1) (t p.1) (b p.1) p.2) ep encUnary :=
unary_add.comp (hP'.prod (unary_mul.comp (hQ.prod hStride)))
exact unary_add.comp ((hRow.comp (fst ep encUnary)).prod (snd ep encUnary))
set_option maxHeartbeats 2000000 in
theorem normalizeMemoryGates_polytime {base n t b : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hN : ComputableTidilyInPolyTime n e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hCap : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => normalizeMemoryGates (base x) (n x) (t x) (b x))
e (encList gateEnc) := by
have hP := normalizeAfter_polytime hBase hT
have hLayout := normalizeLayoutGates_polytime hBase hN hT hB hCap
have hPool := triePoolGateList_polytime hBase hP hN hT hB hCap
have hDictionaryBase := triePoolAfter_poly hP hT hB hCap
have hWidth := unary_pow2_of_bound hB (layoutHorizon_poly.comp hT)
(fun x => Nat.pow_le_pow_right (by decide) (hCap x))
let src := fun x => triePoolSourceWire (normalizeAfter (base x) (t x)) (t x) (b x)
have hDictionary := trieDictionaryGates_polytime (src := src) hDictionaryBase hWidth
(triePoolHeight_poly hT hB) (triePoolRows_poly hT hB)
(triePoolSourceWire_polytime hP hT hB hCap)
exact listAppend' (listAppend' hLayout hPool) hDictionary
theorem normalizeMemoryEnd_polytime {base t b : A → ℕ}
(hBase : ComputableTidilyInPolyTime base e encUnary)
(hT : ComputableTidilyInPolyTime t e encUnary)
(hB : ComputableTidilyInPolyTime b e encUnary)
(hCap : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => normalizeMemoryEnd (base x) (t x) (b x))
e encUnary := by
have hP := normalizeAfter_polytime hBase hT
have hDictionaryBase := triePoolAfter_poly hP hT hB hCap
have hWidth := unary_pow2_of_bound hB (layoutHorizon_poly.comp hT)
(fun x => Nat.pow_le_pow_right (by decide) (hCap x))
have hHeight := triePoolHeight_poly hT hB
have hCount := triePoolRows_poly hT hB
exact trieSortPassEnd_poly (trieSortPassEnd_poly hDictionaryBase hWidth hHeight hCount) hWidth hHeight hCount
end
theorem normalizeMemoryGates_extend_layout (a : Assignment) (base n t : ℕ)
(hBase : sharedLimit n t ≤ base) (hShape : SlotsWellFormed a n t) :
∃ α : Assignment,
(∀ i, i < base ∨ normalizeMemoryEnd base t (trieLevel t) ≤ i → α i = a i) ∧
∀ g ∈ normalizeMemoryGates base n t (trieLevel t), g.Holds α := by
have hWidth : 0 < trieWidth t := Nat.two_pow_pos _
obtain ⟨dict,lab,hGood,_,hIds,_,hLab,_⟩ :=
memoryPacking_exists hShape hWidth (trieWidth_allow t)
obtain ⟨α,hFr,hG,_⟩ := normalizeMemoryGates_complete a base n t (trieLevel t)
hBase (trieLevel_cap t) hShape dict lab hGood
(fun x hx => (le_max_right _ _).trans_lt (hIds x hx)) hLab
exact ⟨α,hFr,hG⟩
end CNFEncComplexity.Robson
/- RobsonTrieComponentGeometry -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem trieRouteCopy_length (base B h : ℕ) (src : ℕ → ℕ → ℕ) :
(trieRouteCopy base B h src).length = 2^h*trieRowWidth B := by
have hL (qs : List ℕ) : (qs.flatMap (fun q =>
wordCopy (trieRowWidth B) (trieRouteIn base B q) (src q))).length = qs.length*trieRowWidth B := by
induction qs with
| nil => simp
| cons q qs ih =>
rw [List.flatMap_cons,List.length_append,ih]
simp only [wordCopy,List.length_map,List.length_range,List.length_cons,Nat.add_mul,Nat.one_mul] <;> omega
exact (hL _).trans (congrArg (fun q => q*trieRowWidth B) List.length_range)
private theorem trieSortPass_length (base B h : ℕ) (hB : 0 < B)
(byChild : Bool) (src : ℕ → ℕ → ℕ) :
(trieSortPass base B h byChild src).length ≤ 27*(h+1)*(2^h*B) := by
have hRows : (trieRouteRows base B h).length = 2^h := by simp [trieRouteRows]
have hCheck := trieSortCheckGates_length B byChild (trieRouteEnd base B h) (trieRouteRows base B h)
rw [hRows] at hCheck
have hWidth : trieRowWidth B ≤ 4*B := by unfold trieRowWidth; omega
have hPair : 12*B+7 ≤ 19*B := by omega
simp only [trieSortPass,List.length_append,trieRouteCopy_length,routeNamedGates_length]
calc
_ ≤ 2^h*trieRowWidth B+(2*h+1)*2^h*trieRowWidth B+2^h*(12*B+7) := Nat.add_le_add_left hCheck _
_ = 2^h*((2*h+2)*trieRowWidth B+(12*B+7)) := by ring
_ ≤ 2^h*((2*h+2)*(4*B)+19*B) := Nat.mul_le_mul_left _
(Nat.add_le_add (Nat.mul_le_mul_left _ hWidth) hPair)
_ = (2^h*B)*(8*(h+1)+19) := by ring
_ ≤ (2^h*B)*(27*(h+1)) := Nat.mul_le_mul_left _ (by omega)
_ = 27*(h+1)*(2^h*B) := by ring
private theorem trieNonzeroList_length (B h : ℕ) (src : ℕ → ℕ → ℕ) :
(trieNonzeroList B h src).length = 2^h := by
have hL (qs : List ℕ) : (qs.flatMap fun q => trieNonzeroGates B (trieRowFromNat B (src q))).length =
qs.length := by
induction qs with
| nil => rfl
| cons q qs ih => simp [List.flatMap_cons,trieNonzeroGates,ih,Nat.add_comm]
exact (hL _).trans List.length_range
private theorem trieDictionaryGates_length (base B h : ℕ) (hB : 0 < B) (src : ℕ → ℕ → ℕ) :
(trieDictionaryGates base B h src).length ≤ 55*(h+1)*(2^h*B) := by
have first := trieSortPass_length base B h hB false src
have second := trieSortPass_length (trieSortPassEnd base B h) B h hB true src
have hNonzero : 2^h ≤ (h+1)*(2^h*B) := by
have hB' : 2^h ≤ 2^h*B := by simpa using Nat.mul_le_mul_left (2^h) hB
apply hB'.trans
simpa using Nat.mul_le_mul_right (2^h*B) (Nat.succ_pos h)
simp only [trieDictionaryGates,List.length_append,trieNonzeroList_length]
calc
_ ≤ (h+1)*(2^h*B) + 27*(h+1)*(2^h*B) + 27*(h+1)*(2^h*B) :=
Nat.add_le_add (Nat.add_le_add hNonzero first) second
_ = 55*(h+1)*(2^h*B) := by ring
/-- Word normalization, gathering, and the two dictionary passes fit the layout budget. -/
theorem normalizeMemoryGates_length (base n t b : ℕ) (hb : b ≤ layoutHeight t) :
(normalizeMemoryGates base n t b).length ≤ 5000*(layoutHorizon t*(layoutHeight t+1)) := by
let Q := triePoolHeight t b
have hGeometry : 2^Q * 2^b = 16*layoutHorizon t := by
have he : Q+b = layoutHeight t+4 := by dsimp [Q,triePoolHeight]; omega
rw [← pow_add,he,pow_add]
exact Nat.mul_comm _ _
have hHeight : Q+1 ≤ 5*(layoutHeight t+1) := by dsimp [Q,triePoolHeight]; omega
have hLayout := normalizeLayoutGates_length base n t b
have hPool := triePoolGateList_length base (normalizeAfter base t) n t b hb
have hDictionary := trieDictionaryGates_length
(triePoolAfter (normalizeAfter base t) t b) (2^b) Q (Nat.two_pow_pos b)
(triePoolSourceWire (normalizeAfter base t) t b)
change (trieDictionaryGates _ (2^b) Q _).length ≤ 55*(Q+1)*(2^Q*2^b) at hDictionary
rw [hGeometry] at hDictionary
have hD : (trieDictionaryGates (triePoolAfter (normalizeAfter base t) t b) (2^b) Q
(triePoolSourceWire (normalizeAfter base t) t b)).length ≤
4400*(layoutHorizon t*(layoutHeight t+1)) := by
calc
_ ≤ 55*(Q+1)*(16*layoutHorizon t) := hDictionary
_ ≤ 55*(5*(layoutHeight t+1))*(16*layoutHorizon t) :=
Nat.mul_le_mul_right _ (Nat.mul_le_mul_left _ hHeight)
_ = _ := by ring
simp only [normalizeMemoryGates,List.length_append]
change _ + _ + (trieDictionaryGates _ _ Q _).length ≤ _
apply (Nat.add_le_add (Nat.add_le_add hLayout hPool) hD).trans
omega
private theorem triePoolAfter_le_normalizeMemoryEnd (base t b : ℕ) :
triePoolAfter (normalizeAfter base t) t b ≤ normalizeMemoryEnd base t b := by
unfold normalizeMemoryEnd trieDictionaryEnd trieSortPassEnd trieRouteEnd
omega
theorem normalizeAfter_le_end (base t b : ℕ) : normalizeAfter base t ≤ normalizeMemoryEnd base t b :=
(Nat.le_add_right _ _).trans (triePoolAfter_le_normalizeMemoryEnd base t b)
/-- Changes above the end of the reserved region preserve all normalization checks. -/
theorem normalizeMemoryGates_frame (a α : Assignment) (base n t b : ℕ)
(hBase : sharedLimit n t ≤ base) (hb : b ≤ layoutHeight t)
(hFr : ∀ i < normalizeMemoryEnd base t b, α i = a i)
(h : ∀ g ∈ normalizeMemoryGates base n t b, g.Holds a) :
∀ g ∈ normalizeMemoryGates base n t b, g.Holds α := by
let pool := normalizeAfter base t
let top := triePoolAfter pool t b
have hTop : top ≤ normalizeMemoryEnd base t b := triePoolAfter_le_normalizeMemoryEnd base t b
simp only [normalizeMemoryGates,List.forall_mem_append] at h ⊢
obtain ⟨⟨hLayout,hPool⟩,hDict⟩ := h
refine ⟨⟨?_,normalizePoolGates_frame a α base pool n t b hBase le_rfl hb
(fun i hi => hFr _ (hi.trans_le hTop)) hPool⟩,?_⟩
· 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 => hFr _ ((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)).trans_le (normalizeAfter_le_end base t b)))).mpr
exact hLayout g hg
· intro g hg
apply (gate_congr g (fun i hi => hFr i (trieDictionaryGates_names_lt top (2^b) (triePoolHeight t b)
(triePoolSourceWire pool t b) (triePoolSourceWire_below pool t b) g hg i hi))).mpr
exact hDict g hg
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).