Trie constraints for bounded RAM word slots
DefinitionCNFEncComplexity_RobsonMemoryTrieSlotscomplexity-theorysatisfiability
Local Boolean constraints for normalizing bounded RAM words, with witness construction and shared-port framing.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryWindowGates
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonTrieChunk -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- The bits of a decoded word agree with the source wires throughout its width. -/
theorem wireValue_testBit (a : Assignment) (src : ℕ → ℕ) {w i : ℕ} (hi : i < w) :
(wireValue a src w).testBit i = a (src i) := by
let e := Cslib.BitString.equivFin w
let f : Fin w → Bool := fun j => a (src j.val)
have he := Cslib.BitString.equivFin_symm_apply (e f) ⟨i,hi⟩
change e.symm (e f) ⟨i,hi⟩ = (e f).val.testBit i at he
rw [Equiv.symm_apply_apply] at he
rw [wireValue_eq_bitString]
exact he.symm
/-- An aligned B-bit slice has exactly the expected digit in base 2^B. -/
theorem wireValue_chunk (a : Assignment) (src : ℕ → ℕ) {w B k : ℕ} (h : k*B+B ≤ w) :
wireValue a (fun i => src (k*B+i)) B = (wireValue a src w / (2^B)^k) % 2^B := by
apply Nat.eq_of_testBit_eq
intro i
rw [Nat.testBit_mod_two_pow]
by_cases hi : i < B
· have hi' : k*B+i < w := by omega
simp only [hi,decide_true,Bool.true_and]
rw [wireValue_testBit _ _ hi,← Nat.pow_mul,Nat.testBit_div_two_pow,
Nat.mul_comm B k,Nat.add_comm i (k*B),wireValue_testBit _ _ hi']
· have eq : (wireValue a (fun i => src (k*B+i)) B).testBit i = false :=
Nat.testBit_lt_two_pow ((wireValue_lt a _ B).trans_le
(Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi)))
simp [hi,eq]
/-- A significant digit exists at k exactly when a bit at offset k*B or greater is set. -/
theorem chunk_index_lt_iff {x k B : ℕ} (hB : 0 < B) :
k < (Nat.digits (2^B) x).length ↔ k*B < x.size := by
have hbase : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
rw [Nat.lt_digits_length_iff hbase,← Nat.pow_mul,Nat.mul_comm B k]
exact (Nat.lt_size).symm
/-- The digit list implementation and binary slices use the same least significant order. -/
theorem chunk_getElem {x k B : ℕ} (hB : 0 < B)
(hk : k < (Nat.digits (2^B) x).length) :
(Nat.digits (2^B) x)[k] = (x / (2^B)^k) % 2^B := by
have hbase : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
induction k generalizing x with
| zero =>
have h0 : x ≠ 0 := by intro he; subst x; simp at hk
apply Option.some.inj
rw [← List.getElem?_eq_getElem hk, Nat.digits_eq_cons_digits_div hbase h0]
simp
| succ k ih =>
have h0 : x ≠ 0 := by intro he; subst x; simp at hk
have hd := Nat.digits_eq_cons_digits_div hbase h0
have hk' : k < (Nat.digits (2^B) (x / 2^B)).length := by simpa [hd] using hk
apply Option.some.inj
rw [← List.getElem?_eq_getElem hk,hd,List.getElem?_cons_succ,List.getElem?_eq_getElem hk',
ih hk',Nat.div_div_eq_div_mul,pow_succ,Nat.mul_comm (2^B) ((2^B)^k)]
/-- The false padding bits after the encoded word is truncated do not change its value. -/
theorem wireValue_prefix_eq (a : Assignment) (src : ℕ → ℕ) {n B : ℕ}
(hBn : B ≤ n) (h : (wireValue a src n).size ≤ B) :
wireValue a src B = wireValue a src n := by
apply Nat.eq_of_testBit_eq
intro i
by_cases hi : i < B
· rw [wireValue_testBit _ _ hi,wireValue_testBit _ _ (hi.trans_le hBn)]
· have hp : 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 a _ B).trans_le hp),
Nat.testBit_lt_two_pow ((Nat.size_le.mp h).trans_le hp)]
/-- One low tag bit precedes the little-endian payload. -/
theorem wireValue_tag (a : Assignment) (src : ℕ → ℕ) (n : ℕ) :
wireValue a src (n+1) = 2*wireValue a (fun i => src (i+1)) n + (a (src 0)).toNat := by
induction n with
| zero => cases h : a (src 0) <;> simp [wireValue,h]
| succ n ih =>
simp only [wireValue] at ih ⊢
rw [pow_succ]
cases h : a (src (n+1)) <;> simp only [h, if_true,if_false,Bool.false_eq_true] <;> omega
end CNFEncComplexity.Robson
/- RobsonTrieLocal -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- A word-level multiplexer introduces one local gate per bit. -/
def trieMux (w sel : ℕ) (out yes no : ℕ → ℕ) : List Gate :=
(List.range w).map (fun i => .mux (out i) sel (yes i) (no i))
@[simp] theorem length_trieMux (w sel : ℕ) (out yes no : ℕ → ℕ) :
(trieMux w sel out yes no).length = w := by simp [trieMux]
theorem trieMux_exact (a : Assignment) (w sel : ℕ) (out yes no : ℕ → ℕ) :
(∀ g ∈ trieMux w sel out yes no, g.Holds a) ↔
wireValue a out w = if a sel then wireValue a yes w else wireValue a no w := by
cases h : a sel <;>
simp only [trieMux,List.forall_mem_map,List.mem_range,Gate.Holds,h,Bool.false_eq_true,
if_false,if_true,wireValue_eq_iff]
theorem wireValue_const_false (a : Assignment) (f w : ℕ) (h : a f = false) :
wireValue a (fun _ => f) w = 0 := by
induction w with
| zero => rfl
| succ w ih => simp [wireValue,ih,h]
/-- The scratch wire names for one word. Width flags are stored consecutively.
All other names are supplied by the surrounding layout. -/
structure TrieWordWires where
raw : ℕ → ℕ
present : ℕ
flags : ℕ
usesTrie : ℕ
emit : ℕ → ℕ
parent : ℕ → ℕ → ℕ
child : ℕ → ℕ → ℕ
label : ℕ → ℕ
def TrieWordWires.mark (w : TrieWordWires) (i : ℕ) : ℕ := widthFlagWire w.flags i
/-- At the end of the allocated chunk range the successor is the constant zero. -/
def TrieWordWires.nextChild (w : TrieWordWires) (B K k i : ℕ) : ℕ :=
if k+1 < K then w.child (k+1) i else w.mark (B*K)
def trieStepGates (w : TrieWordWires) (B K k : ℕ) : List Gate :=
.conj (w.emit k) w.usesTrie (w.mark (k*B)) ::
trieMux B (w.mark ((k+1)*B)) (w.parent k) (w.nextChild B K k) (fun _ => w.mark (B*K))
def longTrieGates (w : TrieWordWires) (B K : ℕ) : List Gate :=
widthCircuit w.flags (B*K) w.raw ++
[.conj w.usesTrie w.present (w.mark B), .copy (w.label 0) (w.mark B)] ++
trieMux B (w.mark B) (fun i => w.label (i+1)) (w.child 0) w.raw ++
(List.range K).flatMap (trieStepGates w B K)
def shortTrieGates (w : TrieWordWires) (n : ℕ) : List Gate :=
.pin (w.label 0) false :: wordCopy n (fun i => w.label (i+1)) w.raw
/-- An edge's digit uses the existing raw input wires, so no copy gates are needed. -/
def trieEdge (a : Assignment) (w : TrieWordWires) (B k : ℕ) : WordEdge :=
⟨wireValue a (w.parent k) B,wireValue a (fun i => w.raw (k*B+i)) B,
wireValue a (w.child k) B⟩
def trieWordRows (a : Assignment) (w : TrieWordWires) (B K : ℕ) : List WordEdge :=
((List.range K).filter fun k => a (w.emit k)).map (trieEdge a w B)
theorem shortTrieGates_sound (a : Assignment) (w : TrieWordWires) (n B : ℕ)
(hn : n ≤ B)
(h : ∀ g ∈ shortTrieGates w n, g.Holds a) (dict : List WordEdge) :
WordLabel B dict (wireValue a w.raw n) (wireValue a w.label (n+1)) := by
have tag : a (w.label 0) = false := h _ (List.mem_cons_self)
have hcopy : wireValue a (fun i => w.label (i+1)) n = wireValue a w.raw n :=
(wordCopy_exact _ _ _ _).mp (fun g hg => h g (List.mem_cons_of_mem _ hg))
have hsize := (Nat.size_le.mpr (wireValue_lt a w.raw n)).trans hn
rw [wireValue_tag,hcopy,tag]
simpa using (WordLabel.small (dict := dict) hsize)
theorem length_shortTrieGates (w : TrieWordWires) (n : ℕ) :
(shortTrieGates w n).length = n+1 := by simp [shortTrieGates]
theorem length_longTrieGates (w : TrieWordWires) (B K : ℕ) (hK : 0 < K) (hB : 0 < B) :
(longTrieGates w B K).length ≤ 8*(B*K) := by
have stepLength (ks : List ℕ) :
(ks.flatMap (trieStepGates w B K)).length = ks.length*(B+1) := by
induction ks with
| nil => simp
| cons k ks ih =>
simp [List.flatMap_cons,trieStepGates,ih,Nat.add_mul,Nat.add_comm] <;> omega
have hKB : K ≤ B*K := by simpa using Nat.mul_le_mul_right K hB
have hBK : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
simp only [longTrieGates,List.length_append,length_widthCircuit,List.length_cons,
List.length_nil,length_trieMux,stepLength,List.length_range]
rw [Nat.mul_add,Nat.mul_one,Nat.mul_comm K B]
omega
/-- The semantic obligations are also sufficient for satisfying the exact gate list. -/
theorem longTrieGates_realize (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hwidth : ∀ g ∈ widthCircuit w.flags (B*K) w.raw, g.Holds a)
(hUses : a w.usesTrie = (a w.present && a (w.mark B)))
(hTag : a (w.label 0) = a (w.mark B))
(hLabel : ∀ i < B, a (w.label (i+1)) = if a (w.mark B) then a (w.child 0 i) else a (w.raw i))
(hEmit : ∀ k < K, a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))))
(hParent : ∀ k < K, ∀ i < B, a (w.parent k i) =
if a (w.mark ((k+1)*B)) then a (w.nextChild B K k i) else a (w.mark (B*K))) :
∀ g ∈ longTrieGates w B K, g.Holds a := by
simp only [longTrieGates,List.forall_mem_append]
refine ⟨⟨⟨hwidth,?_⟩,?_⟩,?_⟩
· simpa [Gate.Holds] using And.intro hUses hTag
· intro g hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
exact hLabel _ (List.mem_range.mp hi)
· intro g hg
obtain ⟨k,hk,hg⟩ := List.mem_flatMap.mp hg
rcases List.mem_cons.mp hg with rfl | hg
· exact hEmit _ (List.mem_range.mp hk)
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
exact hParent _ (List.mem_range.mp hk) _ (List.mem_range.mp hi)
end CNFEncComplexity.Robson
/- RobsonTrieChain -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem chainOfArray {dict : List WordEdge} (ds : List ℕ) (ids : ℕ → ℕ)
(he : ∀ k (hk : k < ds.length),
(⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict) :
WordEdge.Represents dict ds (if ds.isEmpty then 0 else ids 0) := by
induction ds generalizing ids with
| nil => exact .nil
| cons d ds ih =>
have atHead := he 0 (by simp)
have hRest : WordEdge.Represents dict ds (if ds.isEmpty then 0 else ids (0+1)) := by
apply ih (fun k => ids (k+1))
intro k hk
have hh := he (k+1) (by simp; omega)
have hr : k+1 < ds.length ↔ k+1+1 < (d::ds).length := by simp
simpa [List.getElem_cons_succ,hr,Nat.add_assoc] using hh
change WordEdge.Represents dict (d::ds) (ids 0)
apply WordEdge.Represents.cons hRest
cases ds <;> simpa using atHead
/-- Convert an existing canonical trie path to exactly the child-ID array used
by the local gates. This also supplies bounds for every relevant ID. -/
theorem WordEdge.Represents.childArray {dict : List WordEdge} {ds : List ℕ} {id : ℕ}
(h : WordEdge.Represents dict ds id) {B : ℕ}
(hBound : ∀ e ∈ dict, e.child < 2^B) :
∃ ids : ℕ → ℕ, (if ds.isEmpty then 0 else ids 0) = id ∧
(∀ k (hk : k < ds.length),
(⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict) ∧
∀ k, ids k < 2^B := by
induction h with
| nil =>
refine ⟨fun _ => 0,rfl,?_,fun _ => by positivity⟩
simp
| @cons d ds par id hp he ih =>
obtain ⟨ids,hFirst,hMem,hb⟩ := ih
let out : ℕ → ℕ
| 0 => id
| k+1 => ids k
refine ⟨out,rfl,?_,?_⟩
· intro k hk
cases k with
| zero =>
have htop : (if 0+1 < (d::ds).length then out (0+1) else 0) = par := by
cases ds <;> simpa [out] using hFirst
change (⟨if 0+1 < (d::ds).length then out (0+1) else 0,d,id⟩ : WordEdge) ∈ dict
rw [htop]
exact he
| succ k =>
have hk' : k < ds.length := by simpa using hk
have hif : (k+1+1 < (d::ds).length) = (k+1 < ds.length) := by simp
simpa [out,hif] using hMem k hk'
· intro k
cases k with
| zero => exact hBound _ he
| succ k => exact hb k
private theorem trieWordDigit_fits (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hB : 0 < B) :
(Nat.digits (2^B) (wireValue a w.raw (B*K))).length ≤ K := by
have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
apply (Nat.digits_length_le_iff hb _).mpr
rw [← Nat.pow_mul]
exact wireValue_lt ..
theorem longTrieGates_sound (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hB : 0 < B) (hK : 0 < K)
(h : ∀ g ∈ longTrieGates w B K, g.Holds a) (hLive : a w.present = true)
(dict : List WordEdge) (hSub : ∀ e ∈ trieWordRows a w B K, e ∈ dict) :
WordLabel B dict (wireValue a w.raw (B*K)) (wireValue a w.label (B+1)) := by
let val := wireValue a w.raw (B*K)
let ds := Nat.digits (2^B) val
let ids := fun k => wireValue a (w.child k) B
have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
simp only [longTrieGates,List.forall_mem_append] at h
obtain ⟨⟨⟨hW,hInit⟩,hLabels⟩,hRows⟩ := h
have hf (i : ℕ) (hi : i ≤ B*K) : a (w.mark i) = decide (i < val.size) :=
widthCircuit_exact _ _ _ _ hW hi
have hUse : a w.usesTrie = a (w.mark B) := by
have he : a w.usesTrie = (a w.present && a (w.mark B)) :=
hInit (.conj w.usesTrie w.present (w.mark B)) (by simp)
simp [he,hLive]
have hTag : a (w.label 0) = a (w.mark B) :=
hInit (.copy (w.label 0) (w.mark B)) (by simp)
have hLabelPayload := (trieMux_exact _ _ _ _ _ _).mp hLabels
have hTotal := trieWordDigit_fits a w B K hB
rw [wireValue_tag,hTag,hLabelPayload]
by_cases hx : B < val.size
· simp only [hf B hb,hx,decide_true,if_true]
have hNonempty : ds ≠ [] := by
intro he
have h1 := (chunk_index_lt_iff (x := val) (k := 1) hB).2 (by simpa using hx)
simp [ds,he] at h1
have hRowsIn (k : ℕ) (hk : k < ds.length) :
(⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict := by
have hkK : k < K := hk.trans_le hTotal
have hkW : k*B ≤ B*K := by
rw [Nat.mul_comm B K]
exact Nat.mul_le_mul_right B hkK.le
have hnW : (k+1)*B ≤ B*K := by
rw [Nat.mul_comm B K]
exact Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr hkK)
have hkOn := (chunk_index_lt_iff hB).mp hk
have hStep : ∀ g ∈ trieStepGates w B K k, g.Holds a :=
fun g hg => hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hkK,hg⟩)
have hemit : a (w.emit k) = true := by
change a (w.emit k) = _
have hg : a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))) := hStep _ (List.mem_cons_self)
rw [hg,hUse,hf _ hb,hf _ hkW]
simp [hx,hkOn]
apply hSub
have hMem : trieEdge a w B k ∈ trieWordRows a w B K := by
apply List.mem_map.mpr
exact ⟨k,List.mem_filter.mpr ⟨List.mem_range.mpr hkK,hemit⟩,rfl⟩
have hEqDigit : wireValue a (fun i => w.raw (k*B+i)) B = ds[k] := by
have hw : k*B+B ≤ B*K := by simpa [Nat.succ_mul] using hnW
exact (wireValue_chunk a w.raw hw).trans (chunk_getElem hB hk).symm
have hEqParent : wireValue a (w.parent k) B =
if k+1 < ds.length then ids (k+1) else 0 := by
have hMux := (trieMux_exact a B (w.mark ((k+1)*B)) (w.parent k)
(w.nextChild B K k) (fun _ => w.mark (B*K))).mp
(fun g hg => hStep _ (List.mem_cons_of_mem _ hg))
refine hMux.trans ?_
rw [hf _ hnW]
by_cases hn : k+1 < ds.length
· have hn' : k+1 < K := hn.trans_le hTotal
have htest := (chunk_index_lt_iff hB).mp hn
simp only [htest,hn,decide_true,if_true]
apply wireValue_key_congr
intro i hi
exact if_pos hn'
· have htest := (chunk_index_lt_iff (x := val) (k := k+1) hB).not.mp hn
have hz : a (w.mark (B*K)) = false := by
have hxw : val.size ≤ B*K := Nat.size_le.mpr (wireValue_lt a w.raw (B*K))
rw [hf _ le_rfl]
simp [not_lt.mpr hxw]
simp [hn,htest,wireValue_const_false a _ _ hz]
simpa [trieEdge,hEqDigit,hEqParent,ids] using hMem
have hRep := chainOfArray ds ids hRowsIn
have hempty : ds.isEmpty = false := by simpa using hNonempty
have hRep' : WordEdge.Represents dict ds (ids 0) := by simpa [hempty] using hRep
exact WordLabel.wide hx hRep'
· simp only [hf B hb,hx,decide_false,Bool.false_eq_true,if_false]
have hs : val.size ≤ B := Nat.le_of_not_gt hx
rw [wireValue_prefix_eq a w.raw hb hs]
simpa using (WordLabel.small (dict := dict) hs)
end CNFEncComplexity.Robson
/- RobsonTrieRows -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem longTrieGates_emit (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hB : 0 < B) (hK : 0 < K)
(h : ∀ g ∈ longTrieGates w B K, g.Holds a)
(k : ℕ) (hk : k < K) :
a (w.emit k) = true ↔ a w.present = true ∧ B < (wireValue a w.raw (B*K)).size ∧
k < (Nat.digits (2^B) (wireValue a w.raw (B*K))).length := by
have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
have hwk : k*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk.le
simp only [longTrieGates,List.forall_mem_append] at h
obtain ⟨⟨⟨hWidth,hInit⟩,_⟩,hRows⟩ := h
have hf (i : ℕ) (hi : i ≤ B*K) :
a (w.mark i) = decide (i < (wireValue a w.raw (B*K)).size) :=
widthCircuit_exact _ _ _ _ hWidth hi
have hUse : a w.usesTrie = (a w.present && a (w.mark B)) :=
hInit (.conj w.usesTrie w.present (w.mark B)) (by simp)
have hStep : ∀ g ∈ trieStepGates w B K k, g.Holds a :=
fun g hg => hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hk,hg⟩)
have hemit : a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))) := hStep _ List.mem_cons_self
rw [hemit,hUse,hf _ hb,hf _ hwk,chunk_index_lt_iff hB]
simp [and_assoc]
theorem longTrieGates_edge (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hB : 0 < B) (h : ∀ g ∈ longTrieGates w B K, g.Holds a)
{k : ℕ} (hk : k < K)
(hd : k < (Nat.digits (2^B) (wireValue a w.raw (B*K))).length) :
let ds := Nat.digits (2^B) (wireValue a w.raw (B*K))
trieEdge a w B k = ⟨
if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0,
ds[k], wireValue a (w.child k) B⟩ := by
let val := wireValue a w.raw (B*K)
let ds := Nat.digits (2^B) val
have hn : (k+1)*B ≤ B*K := by
rw [Nat.mul_comm B K]
exact Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr hk)
have hw : k*B+B ≤ B*K := by simpa [Nat.succ_mul] using hn
simp only [longTrieGates,List.forall_mem_append] at h
obtain ⟨⟨⟨hWidth,_⟩,_⟩,hRows⟩ := h
have hs : ∀ g ∈ trieStepGates w B K k, g.Holds a := fun g hg =>
hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hk,hg⟩)
have hf (i : ℕ) (hi : i ≤ B*K) : a (w.mark i) = decide (i < val.size) :=
widthCircuit_exact _ _ _ _ hWidth hi
have hDigit : wireValue a (fun i => w.raw (k*B+i)) B = ds[k] :=
(wireValue_chunk a w.raw hw).trans (chunk_getElem hB hd).symm
have hMux := (trieMux_exact a B (w.mark ((k+1)*B)) (w.parent k) (w.nextChild B K k)
(fun _ => w.mark (B*K))).mp (fun g hg => hs _ (List.mem_cons_of_mem _ hg))
have hFit : ds.length ≤ K := by
have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
apply (Nat.digits_length_le_iff hb _).mpr
rw [← Nat.pow_mul]
exact wireValue_lt ..
have hParent : wireValue a (w.parent k) B =
if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0 := by
rw [hMux,hf _ hn]
by_cases hD : k+1 < ds.length
· have hp := (chunk_index_lt_iff (x := val) (k := k+1) hB).mp hD
simp only [hp,hD,decide_true,if_true]
apply wireValue_key_congr
intro i hi
exact if_pos (hD.trans_le hFit)
· have hp := (chunk_index_lt_iff (x := val) (k := k+1) hB).not.mp hD
have hv : val.size ≤ B*K := Nat.size_le.mpr (wireValue_lt a w.raw (B*K))
have hz : a (w.mark (B*K)) = false := by rw [hf _ le_rfl]; simp [not_lt.mpr hv]
simp [hp,hD,wireValue_const_false a _ _ hz]
change trieEdge a w B k = ⟨if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0,
ds[k],wireValue a (w.child k) B⟩
simp only [trieEdge,hDigit,hParent]
theorem longTrieGates_payload (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hK : 0 < K) (h : ∀ g ∈ longTrieGates w B K, g.Holds a) :
wireValue a w.label (B+1) =
if B < (wireValue a w.raw (B*K)).size then 2*wireValue a (w.child 0) B+1
else 2*wireValue a w.raw (B*K) := by
have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
simp only [longTrieGates,List.forall_mem_append] at h
obtain ⟨⟨⟨hWidth,hInit⟩,hLabels⟩,_⟩ := h
have hTag : a (w.label 0) = a (w.mark B) :=
hInit (.copy (w.label 0) (w.mark B)) (by simp)
have hf : a (w.mark B) = decide (B < (wireValue a w.raw (B*K)).size) :=
widthCircuit_exact _ _ _ _ hWidth hb
rw [wireValue_tag,hTag,(trieMux_exact _ _ _ _ _ _).mp hLabels,hf]
by_cases hu : B < (wireValue a w.raw (B*K)).size
· simp [hu]
· have hs := Nat.le_of_not_gt hu
simp [hu,wireValue_prefix_eq a w.raw hb hs]
end CNFEncComplexity.Robson
/- RobsonTrieWitness -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
inductive TrieRest (B K : ℕ) where
| used
| emit (k : Fin K)
| parent (k : Fin K) (i : Fin B)
| child (k : Fin K) (i : Fin B)
| label (i : Fin (B+1))
def TrieWordWires.restName (w : TrieWordWires) {B K : ℕ} : TrieRest B K → ℕ
| .used => w.usesTrie
| .emit k => w.emit k.val
| .parent k i => w.parent k.val i.val
| .child k i => w.child k.val i.val
| .label i => w.label i.val
private def trieRestValue (a : Assignment) (w : TrieWordWires) (B K : ℕ) (ids : ℕ → ℕ) :
TrieRest B K → Bool
| .used => a w.present && a (w.mark B)
| .emit k => (a w.present && a (w.mark B)) && a (w.mark (k.val*B))
| .parent k i =>
if a (w.mark ((k.val+1)*B)) then
if k.val+1 < K then (ids (k.val+1)).testBit i.val else a (w.mark (B*K))
else a (w.mark (B*K))
| .child k i => (ids k.val).testBit i.val
| .label i =>
match i.val with
| 0 => a (w.mark B)
| j+1 => if a (w.mark B) then (ids 0).testBit j else a (w.raw j)
/-- Given fitted identifiers, the local verifier has a satisfying extension
which modifies only the interval for flags and the explicitly reserved names. -/
theorem longTrieGates_witnessIds (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hK : 0 < K) (ids : ℕ → ℕ) (hIds : ∀ k < K, ids k < 2^B)
(hRaw : ∀ i < B*K, w.raw i < w.flags) (hPresent : w.present < w.flags)
(hName : Function.Injective (w.restName (B := B) (K := K)))
(hAlloc : ∀ p : TrieRest B K, w.flags+B*K+1 ≤ w.restName p) :
∃ a' : Assignment,
(∀ i, (i < w.flags ∨ w.flags+B*K+1 ≤ i) →
(¬∃ p : TrieRest B K, w.restName p = i) → a' i = a i) ∧
(∀ i < w.flags, a' i = a i) ∧
(∀ g ∈ longTrieGates w B K, g.Holds a') ∧
(∀ k < K, wireValue a' (w.child k) B = ids k) := by
obtain ⟨a0,ha0,hw0⟩ := widthCircuit_extends_interval w.flags (B*K) w.raw a hRaw
let a' : Assignment := Function.extend (w.restName (B := B) (K := K))
(trieRestValue a0 w B K ids) a0
have he (p : TrieRest B K) : a' (w.restName p) = trieRestValue a0 w B K ids p :=
hName.extend_apply _ _ _
have horig (i : ℕ) (hi : i < w.flags+B*K+1) : a' i = a0 i := by
apply Function.extend_apply'
rintro ⟨p,hp⟩
have := hAlloc p
omega
have hbelow (i : ℕ) (hi : i < w.flags) : a' i = a i :=
(horig i (by omega)).trans (ha0 i (.inl hi))
have hFlag (i : ℕ) (hi : i ≤ B*K) : a' (w.mark i) = a0 (w.mark i) :=
horig _ (by unfold TrieWordWires.mark widthFlagWire; omega)
have hW : ∀ g ∈ widthCircuit w.flags (B*K) w.raw, g.Holds a' := by
intro g hg
have hs := hw0 g hg
rcases List.mem_cons.mp hg with rfl | hg
· change a' (w.mark (B*K)) = false
exact (hFlag _ le_rfl).trans hs
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hi' := List.mem_range.mp hi
change a' (w.mark i) = (a' (w.raw i) || a' (w.mark (i+1)))
rw [hFlag _ hi'.le,hFlag _ hi',horig _ (by have := hRaw i hi'; omega)]
exact hs
have hBK : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
have hUse : a' w.usesTrie = (a' w.present && a' (w.mark B)) := by
rw [hFlag _ hBK,horig w.present (by omega)]
exact he .used
have hTag : a' (w.label 0) = a' (w.mark B) := by
rw [hFlag _ hBK]
exact he (.label ⟨0,by omega⟩)
have hChild (k : ℕ) (hk : k < K) (i : ℕ) (hi : i < B) :
a' (w.child k i) = (ids k).testBit i :=
he (.child ⟨k,hk⟩ ⟨i,hi⟩)
have hSat : ∀ g ∈ longTrieGates w B K, g.Holds a' := by
apply longTrieGates_realize a' w B K hW hUse hTag
· intro i hi
rw [hFlag _ hBK,hChild _ hK _ hi,horig (w.raw i) (by have := hRaw i (hi.trans_le hBK); omega)]
exact he (.label ⟨i+1,by omega⟩)
· intro k hk
have hmul : k*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk.le
rw [hUse,hFlag _ hBK,hFlag _ hmul,horig w.present (by omega)]
exact he (.emit ⟨k,hk⟩)
· intro k hk i hi
have hmul : (k+1)*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk
rw [hFlag _ hmul,hFlag _ le_rfl]
have he' : a' (w.parent k i) =
(if a0 (w.mark ((k+1)*B)) then
if k+1 < K then (ids (k+1)).testBit i else a0 (w.mark (B*K))
else a0 (w.mark (B*K))) := he (.parent ⟨k,hk⟩ ⟨i,hi⟩)
rw [he']
by_cases hNext : k+1 < K
· simp only [TrieWordWires.nextChild,hNext,if_true,hChild _ hNext _ hi]
· simp only [TrieWordWires.nextChild,hNext,if_false,hFlag _ le_rfl]
refine ⟨a',?_,hbelow,hSat,?_⟩
· intro i hi hi'
exact (Function.extend_apply' _ _ _ hi').trans (ha0 i hi)
· intro k hk
apply Nat.eq_of_testBit_eq
intro i
by_cases hi : i < B
· rw [wireValue_testBit _ _ hi,hChild _ hk _ hi]
· have hp : 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 hp),
Nat.testBit_lt_two_pow ((hIds k hk).trans_le hp)]
end CNFEncComplexity.Robson
/- RobsonTrieBlock -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
private theorem wordLabel_short {B : ℕ} {dict : List WordEdge} {x y : ℕ}
(h : WordLabel B dict x y) (hb : x.size ≤ B) : y = 2*x := by
cases h with
| small _ => rfl
| wide he _ => omega
private theorem wordLabel_long {B : ℕ} {dict : List WordEdge} {x y : ℕ}
(h : WordLabel B dict x y) (hb : B < x.size) :
∃ id, y = 2*id+1 ∧ WordEdge.Represents dict (Nat.digits (2^B) x) id := by
cases h with
| small he => omega
| wide _ h => exact ⟨_,rfl,h⟩
/-- Construct the full local witness from fitted canonical dictionary labels.
The result's emitted rows are a subset of the very same dictionary. -/
theorem longTrieGates_complete (a : Assignment) (w : TrieWordWires) (B K : ℕ)
(hB : 0 < B) (hK : 0 < K)
(dict : List WordEdge) (label : ℕ)
(hDict : ∀ e ∈ dict, e.child < 2^B)
(hLabel : a w.present = true → WordLabel B dict (wireValue a w.raw (B*K)) label)
(hRaw : ∀ i < B*K, w.raw i < w.flags) (hPresent : w.present < w.flags)
(hName : Function.Injective (w.restName (B := B) (K := K)))
(hAlloc : ∀ p : TrieRest B K, w.flags+B*K+1 ≤ w.restName p) :
∃ a' : Assignment,
(∀ i, (i < w.flags ∨ w.flags+B*K+1 ≤ i) →
(¬∃ p : TrieRest B K, w.restName p = i) → a' i = a i) ∧
(∀ i < w.flags, a' i = a i) ∧
(∀ g ∈ longTrieGates w B K, g.Holds a') ∧
(a w.present = true → wireValue a' w.label (B+1) = label) ∧
∀ e ∈ trieWordRows a' w B K, e ∈ dict := by
classical
let x := wireValue a w.raw (B*K)
let digits := Nat.digits (2^B) x
have hArray : ∃ ids : ℕ → ℕ, (∀ k, ids k < 2^B) ∧
(a w.present = true → B < x.size →
label = 2*ids 0+1 ∧
∀ k (hk : k < digits.length),
(⟨if k+1 < digits.length then ids (k+1) else 0,digits[k],ids k⟩ : WordEdge) ∈ dict) := by
by_cases hwide : a w.present = true ∧ B < x.size
· obtain ⟨id,he,hRep⟩ := wordLabel_long (hLabel hwide.1) hwide.2
obtain ⟨ids,hf,hr,hfit⟩ := hRep.childArray hDict
have hn : digits.isEmpty = false := by
apply List.isEmpty_eq_false_iff.mpr
intro hh
have hh' : 1 < digits.length :=
(chunk_index_lt_iff (x := x) (k := 1) hB).2 (by simpa using hwide.2)
simp [hh] at hh'
have hz : ids 0 = id := by
change (if digits.isEmpty then 0 else ids 0) = id at hf
simpa only [hn,Bool.false_eq_true,if_false] using hf
exact ⟨ids,hfit,fun _ _ => ⟨by rw [hz]; exact he,hr⟩⟩
· exact ⟨fun _ => 0,fun _ => by positivity, fun hp hw => False.elim (hwide ⟨hp,hw⟩)⟩
obtain ⟨ids,hFit,hCertified⟩ := hArray
obtain ⟨a',hFrame,hLow,hSat,hChild⟩ :=
longTrieGates_witnessIds a w B K hK ids (fun k _ => hFit k) hRaw hPresent hName hAlloc
have hVal : wireValue a' w.raw (B*K) = x :=
wireValue_congr (fun i hi => hLow _ (hRaw i hi))
have hOn : a' w.present = a w.present := hLow _ hPresent
refine ⟨a',hFrame,hLow,hSat,?_,?_⟩
· intro ha
rw [longTrieGates_payload a' w B K hK hSat,hVal,hChild 0 hK]
by_cases hw : B < x.size
· simp [hw,(hCertified ha hw).1]
· simpa [hw,wordLabel_short (hLabel ha) (Nat.le_of_not_gt hw),x]
· intro e he
obtain ⟨k,hk,rfl⟩ := List.mem_map.mp he
obtain ⟨hm,hen⟩ := List.mem_filter.mp hk
have hv : k < K := List.mem_range.mp hm
have hc := (longTrieGates_emit a' w B K hB hK hSat k hv).mp hen
rw [hOn,hVal] at hc
obtain ⟨ha,hw,hd⟩ := hc
have hEdge := longTrieGates_edge a' w B K hB hSat hv
have hk' : k < (Nat.digits (2^B) (wireValue a' w.raw (B*K))).length := by simpa [hVal] using hd
have hRewrite : trieEdge a' w B k =
(⟨if k+1 < digits.length then wireValue a' (w.child (k+1)) B else 0,
digits[k], wireValue a' (w.child k) B⟩ : WordEdge) := by
have hs := hEdge hk'
have hDigit (q : ℕ) :
(Nat.digits (2^B) (wireValue a' w.raw (B*K)))[q]? = digits[q]? := by rw [hVal]
have hqd := hDigit k
rw [List.getElem?_eq_getElem hk',List.getElem?_eq_getElem hd] at hqd
have hsz : (Nat.digits (2^B) (wireValue a' w.raw (B*K))).length = digits.length := by rw [hVal]
dsimp only at hs
rw [hs]
simp only [hsz,Option.some.inj hqd] <;> rfl
rw [hRewrite,hChild k hv]
have hh := (hCertified ha hw).2 k hd
by_cases hNext : k+1 < digits.length
· have hMax : digits.length ≤ K := by
have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
apply (Nat.digits_length_le_iff hb _).2
rw [← Nat.pow_mul]
exact wireValue_lt ..
simpa [hNext,hChild _ (hNext.trans_le hMax)] using hh
· simpa [hNext] using hh
/-- Short literals also have a fresh-wire extension. No trie payload is emitted. -/
theorem shortTrieGates_witness (a : Assignment) (w : TrieWordWires) (n : ℕ)
(hName : Function.Injective (fun i : Fin (n+1) => w.label i.val))
(hFresh : ∀ i < n, ¬∃ k : Fin (n+1), w.label k.val = w.raw i) :
∃ a' : Assignment,
(∀ v, (¬∃ k : Fin (n+1), w.label k.val = v) → a' v = a v) ∧
(∀ g ∈ shortTrieGates w n, g.Holds a') ∧
wireValue a' w.label (n+1) = 2*wireValue a w.raw n := by
classical
let f : Fin (n+1) → Bool := fun i =>
match i.val with
| 0 => false
| k+1 => a (w.raw k)
let a' : Assignment := Function.extend (fun i : Fin (n+1) => w.label i.val) f a
have he (i : Fin (n+1)) : a' (w.label i.val) = f i := hName.extend_apply f a i
have hFrame (v : ℕ) (hv : ¬∃ k : Fin (n+1), w.label k.val = v) : a' v = a v :=
Function.extend_apply' f a v hv
have hTag : a' (w.label 0) = false := he ⟨0,by omega⟩
have hCopy : wireValue a' (fun i => w.label (i+1)) n = wireValue a w.raw n := by
rw [show wireValue a w.raw n = wireValue a' w.raw n from
(wireValue_congr (fun i hi => hFrame _ (hFresh i hi))).symm]
exact (wireValue_eq_iff _ _ _ _).2 (fun i hi =>
(he ⟨i+1,by omega⟩).trans (hFrame _ (hFresh i hi)).symm)
refine ⟨a',hFrame,?_,?_⟩
· intro g hg
rcases List.mem_cons.mp hg with rfl | hg
· exact hTag
· have hh := (wordCopy_exact n (fun i => w.label (i+1)) w.raw a').2
(hCopy.trans (wireValue_congr (fun i hi => hFrame _ (hFresh i hi))).symm)
exact hh _ hg
· simp [wireValue_tag,hTag,hCopy]
end CNFEncComplexity.Robson
/- RobsonTrieAlloc -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- Static consecutive blocks within a word's reserved interval. -/
def trieWiresAt (base width K : ℕ) (B : ℕ) (raw : ℕ → ℕ) (on : ℕ) : TrieWordWires :=
{ raw := raw, present := on, flags := base, usesTrie := base+width+1
emit := fun k => base+width+2+k
parent := fun k j => base+width+2+K+k*B+j
child := fun k j => base+2*width+2+K+k*B+j
label := fun i => base+3*width+2+K+i }
theorem trieWiresAt_labels {D base W K B on : ℕ} {raw : ℕ → ℕ} :
Function.Injective (fun i : Fin D => (trieWiresAt base W K B raw on).label i.val) := by
intro i j he
apply Fin.ext
simpa [trieWiresAt,Nat.add_left_cancel_iff] using he
private theorem flattenFin_lt {B K : ℕ} (k : Fin K) (i : Fin B) :
k.val*B+i.val < B*K := by
have h := Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr k.isLt)
rw [Nat.succ_mul,Nat.mul_comm K B] at h
have := i.isLt
omega
private theorem flattenFin_inj {B K : ℕ} {k k' : Fin K} {i i' : Fin B}
(h : k.val*B+i.val = k'.val*B+i'.val) :
k = k' ∧ i = i' := by
have hp : 0 < B := Nat.zero_lt_of_lt i.isLt
have hk := congrArg (fun n => n / B) h
have hi := congrArg (fun n => n % B) h
have hk0 : k.val*B+i.val = i.val+k.val*B := Nat.add_comm ..
have hk1 : k'.val*B+i'.val = i'.val+k'.val*B := Nat.add_comm ..
rw [hk0,hk1,Nat.add_mul_div_right _ _ hp,Nat.add_mul_div_right _ _ hp,
Nat.div_eq_of_lt i.isLt,Nat.div_eq_of_lt i'.isLt,Nat.zero_add,Nat.zero_add] at hk
rw [hk0,hk1,Nat.add_mul_mod_self_right,Nat.add_mul_mod_self_right,
Nat.mod_eq_of_lt i.isLt,Nat.mod_eq_of_lt i'.isLt] at hi
exact ⟨Fin.ext hk,Fin.ext hi⟩
theorem trieWiresAt_rest_injective (base B K on : ℕ) (raw : ℕ → ℕ) :
Function.Injective ((trieWiresAt base (B*K) K B raw on).restName (B := B) (K := K)) := by
intro x y he
cases x <;> cases y <;> simp only [TrieWordWires.restName,trieWiresAt] at he
all_goals try rfl
all_goals try (exfalso; omega)
case emit.emit i j => exact congrArg TrieRest.emit (Fin.ext (by omega))
case parent.parent k i k' i' =>
obtain ⟨rfl,rfl⟩ := flattenFin_inj (k := k) (k' := k') (i := i) (i' := i') (by omega)
rfl
case parent.child k i k' i' =>
have := flattenFin_lt k i
have := flattenFin_lt k' i'
exfalso; omega
case parent.label k i j =>
have := flattenFin_lt k i
exfalso; omega
case child.parent k i k' i' =>
have := flattenFin_lt k i
have := flattenFin_lt k' i'
exfalso; omega
case child.child k i k' i' =>
obtain ⟨rfl,rfl⟩ := flattenFin_inj (k := k) (k' := k') (i := i) (i' := i') (by omega)
rfl
case child.label k i j =>
have := flattenFin_lt k i
exfalso; omega
case label.parent j k i =>
have := flattenFin_lt k i
exfalso; omega
case label.child j k i =>
have := flattenFin_lt k i
exfalso; omega
case label.label i j => exact congrArg TrieRest.label (Fin.ext (by omega))
theorem trieWiresAt_rest_bounds (base B K on : ℕ) (raw : ℕ → ℕ)
(hB : 0 < B) (hK : 0 < K) (r : TrieRest B K) :
let w := trieWiresAt base (B*K) K B raw on
base+B*K+1 ≤ w.restName r ∧ w.restName r < base+6*(B*K)+4 := by
have h₁ : K ≤ B*K := by simpa using Nat.mul_le_mul_right K hB
have h₂ : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
dsimp only
cases r with
| used => simp [TrieWordWires.restName,trieWiresAt]; omega
| emit k => have := k.isLt; simp [TrieWordWires.restName,trieWiresAt]; omega
| parent k i => have := flattenFin_lt k i; simp [TrieWordWires.restName,trieWiresAt]; omega
| child k i => have := flattenFin_lt k i; simp [TrieWordWires.restName,trieWiresAt]; omega
| label i => have := i.isLt; simp [TrieWordWires.restName,trieWiresAt]; omega
theorem wireValue_portWord (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (field : ℕ) :
wireValue a (port n t s field) (2^s.2) = portWord a n t s field := by
rw [wireValue_eq_sum]
unfold portWord
congr 1
end CNFEncComplexity.Robson
/- RobsonTrieSlot -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def normalizeWidth (b : ℕ) (s : ℕ × ℕ) : ℕ := min (2^s.2) (2^b)+1
def normalizeStride (t : ℕ) : ℕ := 6*layoutHorizon t+4
def normalizeWordBase (base t : ℕ) (s : ℕ × ℕ) (r f : ℕ) : ℕ :=
base+(((s.1*(layoutHeight t+1)+s.2)*3+r)*3+f)*normalizeStride t
def normalizeSlotWires (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : TrieWordWires :=
trieWiresAt (normalizeWordBase base t s r f) (2^s.2) (2^(s.2-b)) (2^b)
(port n t s (5+5*r+f)) (port n t s (3+5*r) 0)
def normalizeWordGates (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : List Gate :=
let w := normalizeSlotWires base n t b s r f
if b ≤ s.2 then longTrieGates w (2^b) (2^(s.2-b))
else shortTrieGates w (2^s.2)
def normalizeSlotGates (base n t b : ℕ) (s : ℕ × ℕ) : List Gate :=
(List.range 3).flatMap fun r =>
(List.range 3).flatMap fun f => normalizeWordGates base n t b s r f
def normalizeSlotLabel (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : ℕ :=
wireValue a (normalizeSlotWires base n t b s r f).label (normalizeWidth b s)
def normalizeWordRows (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
List WordEdge :=
if b ≤ s.2 then trieWordRows a (normalizeSlotWires base n t b s r f) (2^b) (2^(s.2-b))
else []
def slotCompactMemory (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (i : ℕ) :
Option ObservedAccess :=
if a (port n t s (3+5*i) 0) then some
⟨⟨normalizeSlotLabel a base n t b s i 0, normalizeSlotLabel a base n t b s i 1,
a (port n t s (3+5*i+1) 0)⟩,normalizeSlotLabel a base n t b s i 2⟩
else none
def slotCompactRows (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) : List ObservedAccess :=
(List.range 3).filterMap (slotCompactMemory a base n t b s)
theorem normalizeChunkGeometry {b j : ℕ} (h : b ≤ j) : 2^b*2^(j-b) = (2:ℕ)^j := by
rw [← pow_add,Nat.add_sub_of_le h]
theorem normalizeWordGates_length (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
(normalizeWordGates base n t b s r f).length ≤ 8*2^s.2 := by
unfold normalizeWordGates
split
· rename_i h
rw [← normalizeChunkGeometry h]
exact length_longTrieGates _ _ _ (by positivity) (by positivity)
· rw [length_shortTrieGates]
have h : 0 < (2:ℕ)^s.2 := by positivity
omega
theorem normalizeSlotGates_length (base n t b : ℕ) (s : ℕ × ℕ) :
(normalizeSlotGates base n t b s).length ≤ 72*2^s.2 := by
have hs (rows : List ℕ) (F : ℕ → List Gate) (m : ℕ)
(h : ∀ i ∈ rows, (F i).length ≤ m) : (rows.flatMap F).length ≤ rows.length*m := by
induction rows with
| nil => simp
| cons i r ih =>
have hr := ih (fun j hj => h j (List.mem_cons_of_mem _ hj))
have hi := h i List.mem_cons_self
rw [List.flatMap_cons,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
unfold normalizeSlotGates
have h := hs (List.range 3) _ (24*2^s.2) (fun r _ => by
have hh := hs (List.range 3) (normalizeWordGates base n t b s r) (8*2^s.2)
(fun f _ => normalizeWordGates_length base n t b s r f)
simpa only [List.length_range,← Nat.mul_assoc] using hh)
simpa only [List.length_range,← Nat.mul_assoc] using h
/-- Decode one compact word from the actual gate list and the verified
dictionary containing that word's emitted rows. -/
theorem normalizedWord_sound (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(ha : a (port n t s (3+5*r) 0) = true)
(h : ∀ g ∈ normalizeWordGates base n t b s r f, g.Holds a)
(dict : List WordEdge) (hSub : ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (normalizeSlotLabel a base n t b s r f) := by
let w := normalizeSlotWires base n t b s r f
by_cases hb : b ≤ s.2
· have hLong : ∀ g ∈ longTrieGates w (2^b) (2^(s.2-b)), g.Holds a := by
simpa only [normalizeWordGates,if_pos hb] using h
have hS : ∀ e ∈ trieWordRows a w (2^b) (2^(s.2-b)), e ∈ dict := by
simpa only [normalizeWordRows,if_pos hb] using hSub
have hw := longTrieGates_sound a w _ _ (by positivity) (by positivity) hLong ha dict hS
rw [normalizeChunkGeometry hb] at hw
change WordLabel _ _ (wireValue a (port n t s _) _) (wireValue a w.label _) at hw
rw [wireValue_portWord] at hw
have hOrder := Nat.pow_le_pow_right (n := 2) (by decide : 0 < 2) hb
simpa only [normalizeSlotLabel,normalizeWidth,min_eq_right hOrder] using hw
· have hShort : ∀ g ∈ shortTrieGates w (2^s.2), g.Holds a := by
simpa only [normalizeWordGates,if_neg hb] using h
have hOrder := Nat.pow_le_pow_right (n := 2) (by decide : 0 < 2) (by omega : s.2 ≤ b)
have hw := shortTrieGates_sound a w _ _ hOrder hShort dict
change WordLabel _ _ (wireValue a (port n t s _) _) (wireValue a w.label _) at hw
rw [wireValue_portWord] at hw
simpa only [normalizeSlotLabel,normalizeWidth,min_eq_left hOrder] using hw
/-- All selected compact rows have the same order and the same flags as the
original slot. The three values are decoded from the local labeled words. -/
theorem normalizedSlot_sound (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ)
(h : ∀ g ∈ normalizeSlotGates base n t b s, g.Holds a)
(dict : List WordEdge)
(hSub : ∀ r < 3, ∀ f < 3, ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
List.Forall₂ (ObservedLabels (2^b) dict) (slotRows a n t s) (slotCompactRows a base n t b s) := by
have hWord (r f : ℕ) (hr : r < 3) (hf : f < 3) (hv : a (port n t s (3+5*r) 0) = true) :
WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (normalizeSlotLabel a base n t b s r f) :=
normalizedWord_sound a base n t b s r f hv
(fun g hg => h g (List.mem_flatMap.mpr ⟨r,List.mem_range.mpr hr,
List.mem_flatMap.mpr ⟨f,List.mem_range.mpr hf,hg⟩⟩)) dict (hSub r hr f hf)
have aux (rows : List ℕ) (hR : ∀ i ∈ rows, i < 3) :
List.Forall₂ (ObservedLabels (2^b) dict) (rows.filterMap (portMemory a n t s))
(rows.filterMap (slotCompactMemory a base n t b s)) := by
induction rows with
| nil => exact List.Forall₂.nil
| cons r rows ih =>
have hr := hR r List.mem_cons_self
have ht := ih (fun k hk => hR _ (List.mem_cons_of_mem _ hk))
by_cases hv : a (port n t s (3+5*r) 0) = true
· rw [List.filterMap_cons, List.filterMap_cons]
have h0 := hWord r 0 hr (by decide) hv
have h1 := hWord r 1 hr (by decide) hv
have h2 := hWord r 2 hr (by decide) hv
have he0 : 5+5*r+0 = 3+5*r+2 := by omega
have he1 : 5+5*r+1 = 3+5*r+3 := by omega
have he2 : 5+5*r+2 = 3+5*r+4 := by omega
rw [he0] at h0
rw [he1] at h1
rw [he2] at h2
simp only [portMemory,slotCompactMemory,hv,if_true]
exact .cons ⟨⟨h0,h1,rfl⟩,fun _ => h2⟩ ht
· simpa only [List.filterMap_cons,portMemory,slotCompactMemory,hv,Bool.false_eq_true,if_false] using ht
exact aux (List.range 3) (fun _ hi => List.mem_range.mp hi)
end CNFEncComplexity.Robson
/- RobsonTrieSlotWitness -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem normalizeWordBase_ge (base t : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
base ≤ normalizeWordBase base t s r f := Nat.le_add_right _ _
theorem normalizeWord_complete (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hBase : sharedLimit n t ≤ base) (hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
(dict : List WordEdge) (label : ℕ) (hDict : ∀ e ∈ dict, e.child < 2^(2^b))
(hLabel : a (port n t s (3+5*r) 0) = true →
WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) label) :
let l := normalizeWordBase base t s r f
∃ a' : Assignment,
(∀ i, (i < l ∨ l+normalizeStride t ≤ i) → a' i = a i) ∧
(∀ g ∈ normalizeWordGates base n t b s r f, g.Holds a') ∧
(a (port n t s (3+5*r) 0) = true → normalizeSlotLabel a' base n t b s r f = label) ∧
∀ e ∈ normalizeWordRows a' base n t b s r f, e ∈ dict := by
let W := (2:ℕ)^s.2
let B := (2:ℕ)^b
let K := (2:ℕ)^(s.2-b)
let l := normalizeWordBase base t s r f
let w := normalizeSlotWires base n t b s r f
have hWpos : 0 < W := by unfold W; positivity
have hsGeom := layout_mem.mp hs
have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hsGeom.2.1
have hLb : sharedLimit n t ≤ l := hBase.trans (normalizeWordBase_ge _ _ _ _ _)
have hRaw (i : ℕ) (hi : i < W) : w.raw i < l := by
change port n t s (5+5*r+f) i < l
rcases s with ⟨u,j⟩
exact (port_lt_shared hsGeom.1 hsGeom.2.1 (by omega) (hi.trans_le hW)).trans_le hLb
have hOn : w.present < l := by
change port n t s (3+5*r) 0 < l
rcases s with ⟨u,j⟩
exact (port_lt_shared hsGeom.1 hsGeom.2.1 (by omega) (hWpos.trans_le hW)).trans_le hLb
by_cases hLong : b ≤ s.2
· have he : B*K = W := normalizeChunkGeometry hLong
have hw : w = trieWiresAt l (B*K) K B (port n t s (5+5*r+f)) (port n t s (3+5*r) 0) := by
rw [he]
rfl
have hUniq : Function.Injective (w.restName (B := B) (K := K)) :=
hw.symm ▸ trieWiresAt_rest_injective l B K _ _
have hAlloc (p : TrieRest B K) :
l+B*K+1 ≤ w.restName p ∧ w.restName p < l+6*(B*K)+4 := by
rw [hw]
exact trieWiresAt_rest_bounds _ _ _ _ _ (by unfold B; positivity) (by unfold K; positivity) p
obtain ⟨a',hFrame,_,hSat,hExact,hRows⟩ :=
longTrieGates_complete a w B K (by unfold B; positivity) (by unfold K; positivity)
dict label hDict
(fun h => by rw [he]; exact wireValue_portWord a n t s _ ▸ hLabel h)
(fun i hi => hRaw i (he ▸ hi)) hOn hUniq (fun p => (hAlloc p).1)
refine ⟨a',?_,?_,?_,?_⟩
· intro i hi
have hTop : B*K ≤ layoutHorizon t := he ▸ hW
have hFrame' : (i < w.flags ∨ w.flags+B*K+1 ≤ i) := by
change i < l ∨ l+B*K+1 ≤ i
unfold normalizeStride at hi
rcases hi with hl | hh
· exact .inl hl
· exact .inr (by omega)
exact hFrame i hFrame' (by
rintro ⟨p,he⟩
obtain ⟨hl,hu⟩ := hAlloc p
unfold normalizeStride at hi
change i < l ∨ l+6*layoutHorizon t+4 ≤ i at hi
omega)
· simpa only [normalizeWordGates,if_pos hLong] using hSat
· have hBW : B ≤ W := Nat.pow_le_pow_right (by decide) hLong
have hWidth : normalizeWidth b s = B+1 := by
unfold normalizeWidth
change min W B+1 = B+1
rw [min_eq_right hBW]
intro h
rw [normalizeSlotLabel,hWidth]
exact hExact h
· simpa only [normalizeWordRows,if_pos hLong] using hRows
· have hWidth : W ≤ B := Nat.pow_le_pow_right (by decide) (by omega)
have hK : K=1 := by unfold K; rw [Nat.sub_eq_zero_of_le (by omega),pow_zero]
have hAlloc (i : Fin (W+1)) : l ≤ w.label i.val ∧ w.label i.val < l+normalizeStride t := by
have hi := i.isLt
change l ≤ l+3*W+2+K+i.val ∧ l+3*W+2+K+i.val < l+6*layoutHorizon t+4
omega
obtain ⟨a',hFrame,hSat,hExact⟩ := shortTrieGates_witness a w W trieWiresAt_labels
(fun i hi => by
rintro ⟨k,hEq⟩
have hL := (hAlloc k).1
have hR := hRaw i hi
omega)
refine ⟨a',?_,?_,?_,?_⟩
· intro i hi
apply hFrame
rintro ⟨p,he⟩
obtain ⟨hl,hu⟩ := hAlloc p
omega
· simpa only [normalizeWordGates,if_neg hLong] using hSat
· intro he
have hLab : label = 2*portWord a n t s (5+5*r+f) := by
have hs := (portWord_size a n t s (5+5*r+f)).trans hWidth
have h := hLabel he
cases h with
| small _ => rfl
| wide hu _ => omega
have hw' : normalizeWidth b s = W+1 := by
unfold normalizeWidth
change min W B+1 = W+1
rw [min_eq_left hWidth]
rw [normalizeSlotLabel,hw',hLab,← wireValue_portWord]
exact hExact
· simp [normalizeWordRows,hLong]
end CNFEncComplexity.Robson
/- RobsonTrieFrame -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- The names touched by a word are raw shared inputs or scratch variables
within that word's private interval. -/
def normalizeWordFrame (base n t : ℕ) (s : ℕ × ℕ) (r f k : ℕ) : Prop :=
k < sharedLimit n t ∨
normalizeWordBase base t s r f ≤ k ∧ k < normalizeWordBase base t s r f+normalizeStride t
theorem normalizeWordFrame_raw (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3) :
(∀ i < 2^s.2, (normalizeSlotWires base n t b s r f).raw i < sharedLimit n t) ∧
(normalizeSlotWires base n t b s r f).present < sharedLimit n t := by
rcases s with ⟨a,j⟩
obtain ⟨ha,hj,-⟩ := layout_mem.mp hs
have hj' : (2:ℕ)^j ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hj
refine ⟨?_,?_⟩
· intro i hi
exact port_lt_shared ha hj (by omega) (hi.trans_le hj')
· exact port_lt_shared ha hj (by omega) (by unfold layoutHorizon; positivity)
theorem normalizeWordFrame_label (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hs : s ∈ layoutSlots t) (i : ℕ) (hi : i < normalizeWidth b s) :
normalizeWordBase base t s r f ≤ (normalizeSlotWires base n t b s r f).label i ∧
(normalizeSlotWires base n t b s r f).label i <
normalizeWordBase base t s r f+normalizeStride t := by
let u := normalizeWordBase base t s r f
let W := (2:ℕ)^s.2
let K := (2:ℕ)^(s.2-b)
have hk : K ≤ W := Nat.pow_le_pow_right (by decide) (Nat.sub_le ..)
have hw : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
have hi' : i ≤ W := le_trans (Nat.lt_succ_iff.mp hi) (min_le_left ..)
change u ≤ u+3*W+2+K+i ∧ u+3*W+2+K+i < u+6*layoutHorizon t+4
refine ⟨Nat.le_trans (Nat.le_trans (Nat.le_trans (Nat.le_add_right _ _) (Nat.le_add_right _ _))
(Nat.le_add_right _ _)) (Nat.le_add_right _ _),?_⟩
omega
theorem normalizedLongFrame_child (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hs : s ∈ layoutSlots t) (hb : b ≤ s.2) (k i : ℕ)
(hk : k < 2^(s.2-b)) (hi : i < 2^b) :
normalizeWordBase base t s r f ≤ (normalizeSlotWires base n t b s r f).child k i ∧
(normalizeSlotWires base n t b s r f).child k i <
normalizeWordBase base t s r f+normalizeStride t := by
have h := trieWiresAt_rest_bounds (normalizeWordBase base t s r f) (2^b) (2^(s.2-b))
(port n t s (3+5*r) 0) (port n t s (5+5*r+f)) (by positivity) (by positivity)
(.child ⟨k,hk⟩ ⟨i,hi⟩)
simp only [TrieWordWires.restName] at h
rw [normalizeChunkGeometry hb] at h
have hw : (2:ℕ)^s.2 ≤ layoutHorizon t :=
Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
exact ⟨(Nat.le_add_right _ _).trans (Nat.le_add_right _ _ |>.trans h.1),
h.2.trans_le (by unfold normalizeStride; omega)⟩
theorem normalizeWordGates_frame (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
(g : Gate) (hg : g ∈ normalizeWordGates base n t b s r f) (name : ℕ)
(hName : name ∈ CNFEncComplexity.Robson.Gate.names g) :
normalizeWordFrame base n t s r f name := by
let w := normalizeSlotWires base n t b s r f
let u := normalizeWordBase base t s r f
let B := (2:ℕ)^b
let K := (2:ℕ)^(s.2-b)
let W := (2:ℕ)^s.2
let inside := normalizeWordFrame base n t s r f
have hRaw (i : ℕ) (hi : i < W) : inside (w.raw i) :=
.inl ((normalizeWordFrame_raw base n t b s r f hs hr hf).1 i hi)
have hOn : inside w.present := .inl (normalizeWordFrame_raw base n t b s r f hs hr hf).2
have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
have hFlag (i : ℕ) (hi : i ≤ W) : inside (w.mark i) := by
right
change u ≤ u+i ∧ u+i < u+6*layoutHorizon t+4
omega
have hLabel (i : ℕ) (hi : i < normalizeWidth b s) : inside (w.label i) :=
.inr (normalizeWordFrame_label base n t b s r f hs i hi)
by_cases hb : b ≤ s.2
· have he : B*K=W := normalizeChunkGeometry hb
have hx : B ≤ W := Nat.pow_le_pow_right (by decide) hb
have hw : normalizeWidth b s = B+1 := by
change min W B+1 = B+1
rw [min_eq_right hx]
have hRest (a : TrieRest B K) : inside (w.restName a) := by
right
have hh := 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) a
rw [he] at hh
change u+W+1 ≤ w.restName a ∧ w.restName a < u+6*W+4 at hh
change u ≤ _ ∧ _ < u+6*layoutHorizon t+4
exact ⟨(Nat.le_add_right _ _).trans ((Nat.le_add_right _ _).trans hh.1),hh.2.trans_le (by omega)⟩
have hG : g ∈ longTrieGates w B K := by simpa [normalizeWordGates,hb] using hg
simp only [longTrieGates,List.mem_append] at hG
rcases hG with hG | hG
· rcases hG with hG | hG
· rcases hG with hG | hG
· rcases List.mem_cons.mp hG with rfl|hA
· have hm : name = w.mark (B*K) := by simpa [CNFEncComplexity.Robson.Gate.names,TrieWordWires.mark] using hName
rw [hm]
exact hFlag _ (le_of_eq he)
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hA
have hi' : i < W := by simpa [he] using List.mem_range.mp hi
simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl|rfl
· exact hFlag _ hi'.le
· exact hRaw _ hi'
· exact hFlag _ hi'
· simp only [List.mem_cons,List.mem_nil_iff,or_false] at hG
rcases hG with rfl|rfl
· simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl|rfl
· exact hRest .used
· exact hOn
· exact hFlag _ hx
· simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl
· exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
· exact hFlag _ hx
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hG
have hi' := List.mem_range.mp hi
simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl|rfl|rfl
· exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
· exact hFlag _ hx
· exact hRest (.child ⟨0,by unfold K; positivity⟩ ⟨i,hi'⟩)
· exact hRaw _ (hi'.trans_le hx)
· obtain ⟨k,hk,hg⟩ := List.mem_flatMap.mp hG
have hk' : k < K := List.mem_range.mp hk
have hMul (j : ℕ) (hj : j ≤ K) : j*B ≤ W := by rw [← he,Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hj
rcases List.mem_cons.mp hg with rfl | hG
· simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl|rfl
· exact hRest (.emit ⟨k,hk'⟩)
· exact hRest .used
· exact hFlag _ (hMul _ hk'.le)
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hG
have hi' : i < B := List.mem_range.mp hi
simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl|rfl|rfl
· exact hRest (.parent ⟨k,hk'⟩ ⟨i,hi'⟩)
· exact hFlag _ (hMul _ hk')
· by_cases hNext : k+1 < K
· change inside (if k+1 < K then w.child (k+1) i else w.mark (B*K))
rw [if_pos hNext]
exact hRest (.child ⟨k+1,hNext⟩ ⟨i,hi'⟩)
· change inside (if k+1 < K then w.child (k+1) i else w.mark (B*K))
rw [if_neg hNext]
exact hFlag _ (le_of_eq he)
· exact hFlag _ (le_of_eq he)
· have hx : W ≤ B := Nat.pow_le_pow_right (by decide) (by omega)
have hw : normalizeWidth b s = W+1 := by
change min W B+1 = W+1
rw [min_eq_left hx]
have hG : g ∈ shortTrieGates w W := by simpa [normalizeWordGates,hb] using hg
rcases List.mem_cons.mp hG with rfl|hA
· have he : name = w.label 0 := by simpa [CNFEncComplexity.Robson.Gate.names,TrieWordWires.mark] using hName
rw [he]
exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hA
have hi' := List.mem_range.mp hi
simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
rcases hName with rfl|rfl
· exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
· exact hRaw _ hi'
end CNFEncComplexity.Robson
/- RobsonTrieGlobalFrame -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- End of the region reserved for all compact normalization words. -/
def normalizeAfter (base t : ℕ) : ℕ :=
base+((layoutHorizon t*(layoutHeight t+1))*9)*normalizeStride t
def NormalizeKey (t : ℕ) := {s : ℕ × ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3
private def normalizeKeyIdx {t : ℕ} (k : NormalizeKey t) : ℕ :=
((k.1.val.1*(layoutHeight t+1)+k.1.val.2)*3+k.2.1.val)*3+k.2.2.val
private theorem normalize_key_mul_bounds {t : ℕ} (k : NormalizeKey t) :
normalizeKeyIdx k+1 ≤ (layoutHorizon t*(layoutHeight t+1))*9 := by
have hg := layout_mem.mp k.1.property
have ha : (k.1.val.1+1)*(layoutHeight t+1) ≤ layoutHorizon t*(layoutHeight t+1) :=
Nat.mul_le_mul_right _ hg.1
rw [Nat.add_mul,Nat.one_mul] at ha
have hj : k.1.val.2 ≤ layoutHeight t := hg.2.1
have hr := k.2.1.isLt
have hf := k.2.2.isLt
unfold normalizeKeyIdx
omega
def normalizeKeyBase (base t : ℕ) (k : NormalizeKey t) : ℕ :=
normalizeWordBase base t k.1.val k.2.1.val k.2.2.val
theorem normalizeKeyBase_range (base t : ℕ) (k : NormalizeKey t) :
base ≤ normalizeKeyBase base t k ∧ normalizeKeyBase base t k+normalizeStride t ≤ normalizeAfter base t := by
refine ⟨normalizeWordBase_ge _ _ _ _ _,?_⟩
have h := Nat.mul_le_mul_right (normalizeStride t) (normalize_key_mul_bounds k)
rw [Nat.add_mul,Nat.one_mul] at h
simpa [normalizeKeyBase,normalizeWordBase,normalizeAfter,normalizeKeyIdx,Nat.add_assoc] using
Nat.add_le_add_left h base
private theorem numeral_injective {d a b i j : ℕ} (hi : i < d) (hj : j < d)
(h : a*d+i = b*d+j) : a=b ∧ i=j := by
have hp := Nat.zero_lt_of_lt hi
have h' := congrArg (fun n => n / d) h
have h'' := congrArg (fun n => n % d) h
rw [Nat.add_comm (a*d) i,Nat.add_comm (b*d) j] at h' h''
rw [Nat.add_mul_div_right _ _ hp,Nat.add_mul_div_right _ _ hp,
Nat.div_eq_of_lt hi,Nat.div_eq_of_lt hj,Nat.zero_add,Nat.zero_add] at h'
rw [Nat.add_mul_mod_self_right,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lt hi,Nat.mod_eq_of_lt hj] at h''
exact ⟨h',h''⟩
private theorem normalizeKeyIdx_injective (t : ℕ) : Function.Injective (@normalizeKeyIdx t) := by
intro a b he
unfold normalizeKeyIdx at he
obtain ⟨h,j⟩ := numeral_injective a.2.2.isLt b.2.2.isLt he
obtain ⟨h,i⟩ := numeral_injective a.2.1.isLt b.2.1.isLt h
obtain ⟨ha,hb⟩ := numeral_injective
(Nat.lt_succ_iff.mpr (layout_mem.mp a.1.property).2.1)
(Nat.lt_succ_iff.mpr (layout_mem.mp b.1.property).2.1) h
exact Prod.ext (Subtype.ext (Prod.ext ha hb)) (Prod.ext (Fin.ext i) (Fin.ext j))
theorem normalizeBlocks_unique {base t i : ℕ} {a b : NormalizeKey t}
(ha : normalizeKeyBase base t a ≤ i ∧ i < normalizeKeyBase base t a+normalizeStride t)
(hb : normalizeKeyBase base t b ≤ i ∧ i < normalizeKeyBase base t b+normalizeStride t) : a = b := by
have hNo_lt (a b : NormalizeKey t) (h : normalizeKeyIdx a < normalizeKeyIdx b) :
normalizeKeyBase base t a+normalizeStride t ≤ normalizeKeyBase base t b := by
have h' : normalizeKeyIdx a+1 ≤ normalizeKeyIdx b := h
have hh := Nat.mul_le_mul_right (normalizeStride t) h'
rw [Nat.add_mul,Nat.one_mul] at hh
simpa [normalizeKeyBase,normalizeWordBase,normalizeKeyIdx,Nat.add_assoc] using
Nat.add_le_add_left hh base
apply normalizeKeyIdx_injective t
by_contra hh
rcases Nat.lt_or_gt_of_ne hh with hh|hh
· exact (not_lt_of_ge ((hNo_lt _ _ hh).trans hb.1)) ha.2
· exact (not_lt_of_ge ((hNo_lt _ _ hh).trans ha.1)) hb.2
/-- Agreement on shared input names and the current word's interval suffices
to preserve every emitted numerical edge. -/
theorem normalizeWordRows_congr (a a' : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
(hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
(h : ∀ i, normalizeWordFrame base n t s r f i → a i = a' i) :
normalizeWordRows a base n t b s r f = normalizeWordRows a' base n t b s r f := by
let w := normalizeSlotWires base n t b s r f
let u := normalizeWordBase base t s r f
let B := (2:ℕ)^b
let K := (2:ℕ)^(s.2-b)
let W := (2:ℕ)^s.2
by_cases hb : b ≤ s.2
· have he : B*K=W := normalizeChunkGeometry hb
have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
have hRest (a : TrieRest B K) : normalizeWordFrame base n t s r f (w.restName a) := by
right
have hh := 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) a
rw [he] at hh
change u+W+1 ≤ w.restName a ∧ w.restName a < u+6*W+4 at hh
exact ⟨(Nat.le_add_right _ _).trans ((Nat.le_add_right _ _).trans hh.1),
hh.2.trans_le (by unfold normalizeStride; omega)⟩
simp only [normalizeWordRows,if_pos hb,trieWordRows]
change ((List.range K).filter fun k => a (w.emit k)).map (trieEdge a w B) =
((List.range K).filter fun k => a' (w.emit k)).map (trieEdge a' w B)
have hSame : ((List.range K).filter fun k => a (w.emit k)) =
((List.range K).filter fun k => a' (w.emit k)) := by
apply List.filter_congr
intro k hk
exact h _ (hRest (.emit ⟨k,List.mem_range.mp hk⟩))
rw [hSame]
apply List.map_congr_left
intro k hk
have hk' := List.mem_range.mp (List.mem_filter.mp hk).1
have hBound : k*B+B ≤ W := by
have hn := Nat.mul_le_mul_right B hk'
simpa [Nat.succ_mul,Nat.mul_comm K B,he] using hn
have hp : wireValue a (w.parent k) B = wireValue a' (w.parent k) B :=
wireValue_congr (fun i hi => h _ (hRest (.parent ⟨k,hk'⟩ ⟨i,hi⟩)))
have hc : wireValue a (w.child k) B = wireValue a' (w.child k) B :=
wireValue_congr (fun i hi => h _ (hRest (.child ⟨k,hk'⟩ ⟨i,hi⟩)))
have hg : wireValue a (fun i => w.raw (k*B+i)) B = wireValue a' (fun i => w.raw (k*B+i)) B :=
wireValue_congr (fun i hi => h _ (.inl ((normalizeWordFrame_raw base n t b s r f hs hr hf).1
(k*B+i) (by omega))))
simp only [trieEdge,hp,hc,hg]
· simp [normalizeWordRows,hb]
end CNFEncComplexity.Robson
/- RobsonTrieNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime
section
variable {α : Type} {enc : α ↪ List Bool}
theorem trieMux_polytime {w sel : α → ℕ} {out yes no : α → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w enc encUnary)
(hsel : ComputableTidilyInPolyTime sel enc encUnary)
(hout : ComputableTidilyInPolyTime (fun p : α × ℕ => out p.1 p.2) (encPair enc encUnary) encUnary)
(hyes : ComputableTidilyInPolyTime (fun p : α × ℕ => yes p.1 p.2) (encPair enc encUnary) encUnary)
(hno : ComputableTidilyInPolyTime (fun p : α × ℕ => no p.1 p.2) (encPair enc encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => trieMux (w x) (sel x) (out x) (yes x) (no x))
enc (encList gateEnc) := by
exact mapWithInput (f := fun x i => Gate.mux (out x i) (sel x) (yes x i) (no x i))
(range.comp hw) (gate_mux hout (hsel.comp (fst enc encUnary)) hyes hno)
theorem normalizeShort_polytime {base W K B on : α → ℕ} {raw : α → ℕ → ℕ}
(hBase : ComputableTidilyInPolyTime base enc encUnary)
(hW : ComputableTidilyInPolyTime W enc encUnary)
(hK : ComputableTidilyInPolyTime K enc encUnary)
(hRaw : ComputableTidilyInPolyTime (fun p : α × ℕ => raw p.1 p.2) (encPair enc encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => shortTrieGates (trieWiresAt (base x) (W x) (K x)
(B x) (raw x) (on x)) (W x)) enc (encList gateEnc) := by
let L := fun x => base x + 3*W x + 2 + K x
have hL : ComputableTidilyInPolyTime L enc encUnary := by
unfold L
fun_prop
have hLabel : ComputableTidilyInPolyTime (fun p : α×ℕ => L p.1+(p.2+1))
(encPair enc encUnary) encUnary := by fun_prop
have hBlock := mapWithInput (f := fun x i => Gate.copy (L x+(i+1)) (raw x i))
(range.comp hW) (gate_copy hLabel hRaw)
simpa [shortTrieGates,trieWiresAt,wordCopy,L] using cons' (gate_pin false hL) hBlock
theorem normalizeLong_polytime {base B K on : α → ℕ} {raw : α → ℕ → ℕ}
(hBase : ComputableTidilyInPolyTime base enc encUnary)
(hB : ComputableTidilyInPolyTime B enc encUnary)
(hK : ComputableTidilyInPolyTime K enc encUnary)
(hOn : ComputableTidilyInPolyTime on enc encUnary)
(hRaw : ComputableTidilyInPolyTime (fun p : α × ℕ => raw p.1 p.2) (encPair enc encUnary) encUnary) :
ComputableTidilyInPolyTime (fun x => longTrieGates
(trieWiresAt (base x) (B x*K x) (K x) (B x) (raw x) (on x)) (B x) (K x))
enc (encList gateEnc) := by
let W := fun x => B x*K x
let P := fun x => base x+W x+2+K x
let C := fun x => base x+2*W x+2+K x
let L := fun x => base x+3*W x+2+K x
let U := fun x => base x+W x+1
have hW : ComputableTidilyInPolyTime W enc encUnary := unary_mul.comp (hB.prod hK)
have hP : ComputableTidilyInPolyTime P enc encUnary := by unfold P; fun_prop
have hC : ComputableTidilyInPolyTime C enc encUnary := by unfold C; fun_prop
have hL : ComputableTidilyInPolyTime L enc encUnary := by unfold L; fun_prop
have hU : ComputableTidilyInPolyTime U enc encUnary := by unfold U; fun_prop
have hWide : ComputableTidilyInPolyTime (fun x => base x+B x) enc encUnary := unary_add.comp (hBase.prod hB)
have hWidth := widthCircuit_polytime hBase hW hRaw
have hInit := cons' (gate_conj hU hOn hWide) (cons' (gate_copy hL hWide) (const []))
have hLabel : ComputableTidilyInPolyTime (fun p : α×ℕ => L p.1+(p.2+1))
(encPair enc encUnary) encUnary := by fun_prop
have hFirst : ComputableTidilyInPolyTime (fun p : α×ℕ => C p.1+p.2)
(encPair enc encUnary) encUnary := by fun_prop
have hSelectLabel := trieMux_polytime (out := fun x i => L x+(i+1))
(yes := fun x i => C x+i) (no := raw) hB hWide hLabel hFirst hRaw
let e := encPair enc encUnary
let e₂ := encPair e encUnary
have hX := fst enc encUnary
have hI := snd enc encUnary
have hY := fst e encUnary
have hJ := snd e encUnary
have hX₂ := hX.comp hY
have hI₂ := hI.comp hY
have hEmit : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1 + W p.1 + 2 + p.2) e encUnary := by
unfold e
fun_prop
have hUsed := hU.comp hX
have hThis : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+p.2*B p.1) e encUnary := by
unfold e
fun_prop
have hNext : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+(p.2+1)*B p.1) e encUnary := by
unfold e
fun_prop
have hEnd : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+W p.1) e encUnary := by
unfold e
fun_prop
have hParent : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
P p.1.1+p.1.2*B p.1.1+p.2) e₂ encUnary := by
unfold e₂ e
fun_prop
have hChild : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
C p.1.1+(p.1.2+1)*B p.1.1+p.2) e₂ encUnary := by
unfold e₂ e
fun_prop
have hIsNext : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ => decide (p.1.2+1 < K p.1.1)) e₂ encBool :=
unary_lt' (unary_add.comp (hI₂.prod (const 1))) (hK.comp hX₂)
have hEnd₂ : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ => base p.1.1+W p.1.1)
e₂ encUnary := hEnd.comp hY
have hChildOrZero : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
if p.1.2+1 < K p.1.1 then C p.1.1+(p.1.2+1)*B p.1.1+p.2 else base p.1.1+W p.1.1) e₂ encUnary := by
simpa only [decide_eq_true_eq] using hIsNext.ite' hChild hEnd₂
have hStep := cons' (gate_conj hEmit hUsed hThis)
(trieMux_polytime (out := fun p j => P p.1+p.2*B p.1+j)
(yes := fun p j => if p.2+1 < K p.1 then C p.1+(p.2+1)*B p.1+j
else base p.1+W p.1)
(no := fun p _ => base p.1+W p.1)
(hB.comp hX) hNext hParent hChildOrZero hEnd₂)
have hAllSteps := flatMapWithInput
(f := fun x k => trieStepGates (trieWiresAt (base x) (W x) (K x) (B x) (raw x) (on x))
(B x) (K x) k) (range.comp hK)
(by
convert hStep using 1 <;> rfl)
simpa [longTrieGates,trieWiresAt,TrieWordWires.mark,widthFlagWire,L,C,W,U] using
listAppend' (listAppend' (listAppend' hWidth hInit) hSelectLabel) hAllSteps
end
end CNFEncComplexity.Robson
/- RobsonTrieNativeSlot -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {enc : A ↪ List Bool}
theorem normalizeWordGates_polytime {base n t b a j r f : A → ℕ}
(hBase : ComputableTidilyInPolyTime base enc encUnary)
(hN : ComputableTidilyInPolyTime n enc encUnary)
(hT : ComputableTidilyInPolyTime t enc encUnary)
(hB : ComputableTidilyInPolyTime b enc encUnary)
(hA : ComputableTidilyInPolyTime a enc encUnary)
(hJ : ComputableTidilyInPolyTime j enc encUnary)
(hR : ComputableTidilyInPolyTime r enc encUnary)
(hF : ComputableTidilyInPolyTime f enc encUnary)
(hJL : ∀ x, j x ≤ layoutHeight (t x))
(hBL : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x =>
normalizeWordGates (base x) (n x) (t x) (b x) (a x,j x) (r x) (f x))
enc (encList gateEnc) := by
have hH := layoutHeight_poly.comp hT
have hW := layoutHorizon_poly.comp hT
have hL : ComputableTidilyInPolyTime (fun x => normalizeWordBase (base x) (t x) (a x,j x) (r x) (f x))
enc encUnary := by
unfold normalizeWordBase normalizeStride
dsimp
fun_prop
have hOn : ComputableTidilyInPolyTime (fun x => port (n x) (t x) (a x,j x) (3+5*r x) 0) enc encUnary :=
slotPort_poly hN hT hA hJ (by fun_prop) (const 0)
have hX := fst enc encUnary
have hI := snd enc encUnary
have hField : ComputableTidilyInPolyTime (fun x => 5+5*r x+f x) enc encUnary := by fun_prop
have hRaw := slotPort_poly (hN.comp hX) (hT.comp hX) (hA.comp hX) (hJ.comp hX)
(hField.comp hX) hI
have hPowJ := unary_pow2_of_bound hJ hW (fun x => Nat.pow_le_pow_right (by decide) (hJL x))
have hPowB := unary_pow2_of_bound hB hW (fun x => Nat.pow_le_pow_right (by decide) (hBL x))
have hExpK := unary_sub.comp (hJ.prod hB)
have hPowK := unary_pow2_of_bound hExpK hW
(fun x => Nat.pow_le_pow_right (by decide) ((Nat.sub_le (j x) (b x)).trans (hJL x)))
let raw := fun x i => port (n x) (t x) (a x,j x) (5+5*r x+f x) i
have hShort := normalizeShort_polytime (raw := raw) (B := fun x => 2^b x) (on := fun x =>
port (n x) (t x) (a x,j x) (3+5*r x) 0) hL hPowJ hPowK hRaw
have hLong := normalizeLong_polytime (raw := raw) hL hPowB hPowK hOn hRaw
have hChoice := (unary_le' hB hJ).ite' hLong hShort
convert hChoice using 1
funext x
by_cases hj : b x ≤ j x
· simp [normalizeWordGates,normalizeSlotWires,hj,normalizeChunkGeometry hj,raw,Function.comp_def]
· simp [normalizeWordGates,normalizeSlotWires,hj,raw,Function.comp_def]
theorem normalizeSlotGates_polytime {base n t b a j : A → ℕ}
(hBase : ComputableTidilyInPolyTime base enc encUnary)
(hN : ComputableTidilyInPolyTime n enc encUnary)
(hT : ComputableTidilyInPolyTime t enc encUnary)
(hB : ComputableTidilyInPolyTime b enc encUnary)
(hA : ComputableTidilyInPolyTime a enc encUnary)
(hJ : ComputableTidilyInPolyTime j enc encUnary)
(hJL : ∀ x, j x ≤ layoutHeight (t x))
(hBL : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x =>
normalizeSlotGates (base x) (n x) (t x) (b x) (a x,j x))
enc (encList gateEnc) := by
let e := encPair enc encUnary
have hX := fst enc encUnary
have hR := snd enc encUnary
have hY := fst e encUnary
have hF := snd e encUnary
let left := hX.comp hY
exact flatMapWithInput (f := fun x r =>
(List.range 3).flatMap fun f =>
normalizeWordGates (base x) (n x) (t x) (b x) (a x,j x) r f) (const (List.range 3))
(flatMapWithInput (f := fun (p : A×ℕ) f =>
normalizeWordGates (base p.1) (n p.1) (t p.1) (b p.1) (a p.1,j p.1) p.2 f)
(const (List.range 3))
(normalizeWordGates_polytime (hBase.comp left) (hN.comp left) (hT.comp left)
(hB.comp left) (hA.comp left) (hJ.comp left) (hR.comp hY) hF
(fun p => hJL p.1.1) (fun p => hBL p.1.1)))
end
def normalizeLayoutGates (base n t b : ℕ) : List Gate :=
(layoutSlots t).flatMap (normalizeSlotGates base n t b)
theorem normalizeLayoutGates_polytime {A : Type} {enc : A ↪ List Bool} {base n t b : A → ℕ}
(hBase : ComputableTidilyInPolyTime base enc encUnary)
(hN : ComputableTidilyInPolyTime n enc encUnary)
(hT : ComputableTidilyInPolyTime t enc encUnary)
(hB : ComputableTidilyInPolyTime b enc encUnary)
(hBL : ∀ x, b x ≤ layoutHeight (t x)) :
ComputableTidilyInPolyTime (fun x => normalizeLayoutGates (base x) (n x) (t x) (b x))
enc (encList gateEnc) := by
let e := encPair encUnary encUnary
have hX := fst enc e
have hS := snd enc e
have hA := (fst encUnary encUnary).comp hS
have hJ := (snd encUnary encUnary).comp hS
have hH := layoutHeight_poly.comp (hT.comp hX)
have hMin := unary_min.comp (hJ.prod hH)
have hList : ComputableTidilyInPolyTime (fun x => layoutSlots (t x)) enc (encList e) :=
layoutSlots_poly.comp hT
have hGate := normalizeSlotGates_polytime (hBase.comp hX) (hN.comp hX) (hT.comp hX)
(hB.comp hX) hA hMin (fun _ => min_le_right ..) (fun p => hBL p.1)
have hAll := flatMapWithInput (f := fun x (s : ℕ×ℕ) => normalizeSlotGates (base x) (n x) (t x)
(b x) (s.1,min s.2 (layoutHeight (t x)))) hList hGate
convert hAll using 1
funext x
apply List.flatMap_congr
intro s hs
have hj := (layout_mem.mp hs).2.1
simp [min_eq_left hj]
end CNFEncComplexity.Robson
/- RobsonTrieGlobal -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- The independently allocated per-word witnesses combine while keeping the
original shared interface and every subsequent circuit region fixed. -/
theorem normalizeLayout_complete (a : Assignment) (base n t b : ℕ)
(hBase : sharedLimit n t ≤ base) (dict : List WordEdge) (lab : ℕ → ℕ)
(hDict : ∀ e ∈ dict, e.child < 2^(2^b))
(hLab : ∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, a (port n t s (3+5*r) 0) = true →
WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (lab (portWord a n t s (5+5*r+f)))) :
∃ a' : Assignment,
(∀ i, i < base ∨ normalizeAfter base t ≤ i → a' i = a i) ∧
(∀ g ∈ normalizeLayoutGates base n t b, g.Holds a') ∧
(∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, a (port n t s (3+5*r) 0) = true →
normalizeSlotLabel a' base n t b s r f = lab (portWord a n t s (5+5*r+f))) ∧
∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, ∀ e ∈ normalizeWordRows a' base n t b s r f, e ∈ dict := by
classical
let contains (k : NormalizeKey t) (i : ℕ) : Prop :=
normalizeKeyBase base t k ≤ i ∧ i < normalizeKeyBase base t k+normalizeStride t
have hh (k : NormalizeKey t) :
∃ β : Assignment, (∀ i, ¬contains k i → β i = a i) ∧
(∀ g ∈ normalizeWordGates base n t b k.1.val k.2.1.val k.2.2.val, g.Holds β) ∧
(a (port n t k.1.val (3+5*k.2.1.val) 0) = true →
normalizeSlotLabel β base n t b k.1.val k.2.1.val k.2.2.val =
lab (portWord a n t k.1.val (5+5*k.2.1.val+k.2.2.val))) ∧
∀ e ∈ normalizeWordRows β base n t b k.1.val k.2.1.val k.2.2.val, e ∈ dict := by
obtain ⟨β,hFr,hs,hl,hE⟩ :=
normalizeWord_complete a base n t b k.1.val k.2.1.val k.2.2.val hBase k.1.property
k.2.1.isLt k.2.2.isLt dict _ hDict
(hLab _ k.1.property _ k.2.1.isLt _ k.2.2.isLt)
refine ⟨β,?_,hs,hl,hE⟩
intro i hI
apply hFr
change ¬(normalizeKeyBase base t k ≤ i ∧ i < normalizeKeyBase base t k + normalizeStride t) at hI
change i < normalizeKeyBase base t k ∨ normalizeKeyBase base t k + normalizeStride t ≤ i
omega
choose assign hFrame hHold hExact hRows using hh
let a' : Assignment := fun i => if h : ∃ k, contains k i then assign h.choose i else a i
have hFr (i : ℕ) (hi : i < base ∨ normalizeAfter base t ≤ i) : a' i = a i := by
unfold a'
apply dif_neg
rintro ⟨k,hk⟩
have hBounds := normalizeKeyBase_range base t k
change normalizeKeyBase base t k ≤ i ∧ i < _ at hk
omega
have hA (k : NormalizeKey t) (i : ℕ)
(hI : normalizeWordFrame base n t k.1.val k.2.1.val k.2.2.val i) : a' i = assign k i := by
rcases hI with hLow | hIn
· have hbl : i < base := hLow.trans_le hBase
rw [hFr i (.inl hbl)]
apply (hFrame k i ?_).symm
intro h
exact (not_le_of_gt (hbl.trans_le (normalizeKeyBase_range base t k).1)) h.1
· have hI : contains k i := hIn
have hEx : ∃ c, contains c i := ⟨k,hI⟩
have hEq : hEx.choose = k := normalizeBlocks_unique hEx.choose_spec hI
simp [a',hEx,hEq]
refine ⟨a',hFr,?_,?_,?_⟩
· intro g hg
obtain ⟨s,hs,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨r,hr,hg⟩ := List.mem_flatMap.mp hg
obtain ⟨f,hf,hg⟩ := List.mem_flatMap.mp hg
let k : NormalizeKey t := (⟨s,hs⟩,⟨r,List.mem_range.mp hr⟩,⟨f,List.mem_range.mp hf⟩)
refine (gate_congr (α := a') (β := assign k) g ?_).mpr (hHold k g hg)
intro i hi
exact hA k i (normalizeWordGates_frame base n t b s r f hs (List.mem_range.mp hr)
(List.mem_range.mp hf) g hg i hi)
· intro s hs r hr f hf hv
let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
refine Eq.trans ?_ (hExact k hv)
apply wireValue_congr
intro i hi
exact hA k _ (.inr (normalizeWordFrame_label base n t b s r f hs i hi))
· intro s hs r hr f hf e hE
let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
have hEq := normalizeWordRows_congr a' (assign k) base n t b s r f hs hr hf (hA k)
exact hRows k e (hEq ▸ hE)
theorem normalizeLayoutGates_length (base n t b : ℕ) :
(normalizeLayoutGates base n t b).length ≤ 72*(layoutHorizon t*(layoutHeight t+1)) := by
have aux (ls : List (ℕ×ℕ)) : (ls.flatMap (normalizeSlotGates base n t b)).length ≤
72*(ls.map fun s => 2^s.2).sum := by
induction ls with
| nil => simp
| cons s ls ih =>
rw [List.flatMap_cons,List.length_append,List.map_cons,List.sum_cons,Nat.mul_add]
exact Nat.add_le_add (normalizeSlotGates_length base n t b s) ih
unfold normalizeLayoutGates
have h := layoutSlots_totalWidth_le t
exact (aux _).trans (Nat.mul_le_mul_left _ (by simpa only [Nat.mul_comm] using h))
end CNFEncComplexity.Robson
/- RobsonTrieIntegration -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem normalizedWord_mem_input (a : Assignment) (n t : ℕ) (s : ℕ×ℕ) (hs : s ∈ layoutSlots t)
(r f : ℕ) (hr : r < 3) (hf : f < 3)
(hv : a (port n t s (3+5*r) 0) = true) :
portWord a n t s (5+5*r+f) ∈ observationWords (memoryStream a n t) := by
let row : ObservedAccess :=
⟨⟨portWord a n t s (3+5*r+2),portWord a n t s (3+5*r+3),
a (port n t s (3+5*r+1) 0)⟩,portWord a n t s (3+5*r+4)⟩
have hr' : portMemory a n t s r = some row := by simp [portMemory,hv,row]
have hPos : row ∈ (List.range 3).filterMap (portMemory a n t s) :=
List.mem_filterMap.mpr ⟨r,List.mem_range.mpr hr,hr'⟩
have hMem : row ∈ memoryStream a n t :=
List.mem_flatMap.mpr ⟨s,hs,hPos⟩
apply List.mem_flatMap.mpr
refine ⟨row,hMem,?_⟩
interval_cases f <;> simp [row] <;> first
| left; congr 1; omega
| right; left; congr 1; omega
| right; right; congr 1; omega
theorem normalizeWord_name_below {base n t : ℕ}
(hs : sharedLimit n t ≤ base) {s : ℕ×ℕ} (hS : s ∈ layoutSlots t) {r f i : ℕ}
(hr : r < 3) (hf : f < 3) (hi : normalizeWordFrame base n t s r f i) :
i < normalizeAfter base t := by
have hBounds := normalizeKeyBase_range base t (⟨s,hS⟩,⟨r,hr⟩,⟨f,hf⟩)
rcases hi with hh | hh
· exact (hh.trans_le hs).trans_le (hBounds.1.trans ((Nat.le_add_right _ _).trans hBounds.2))
· exact hh.2.trans_le hBounds.2
theorem normalizeSlotLabel_frame (a α : Assignment) (base n t b : ℕ)
(hBase : sharedLimit n t ≤ base) (s : ℕ×ℕ)
(hs : s ∈ layoutSlots t) (r f : ℕ) (hr : r < 3) (hf : f < 3)
(hFrame : ∀ i < normalizeAfter base t, a i = α i) :
normalizeSlotLabel a base n t b s r f = normalizeSlotLabel α base n t b s r f := by
unfold normalizeSlotLabel
apply wireValue_congr
intro i hi
exact hFrame _ (normalizeWord_name_below hBase hs hr hf
(.inr (normalizeWordFrame_label base n t b s r f hs i hi)))
theorem slotCompactMemory_witness (a α : Assignment) (base n t b : ℕ) (s : ℕ×ℕ)
(hs : s ∈ layoutSlots t) (r : ℕ) (hr : r < 3) (lab : ℕ → ℕ)
(hFrame : ∀ i < sharedLimit n t, α i = a i)
(hLabel : ∀ f < 3, a (port n t s (3+5*r) 0)=true →
normalizeSlotLabel α base n t b s r f = lab (portWord a n t s (5+5*r+f))) :
slotCompactMemory α base n t b s r = (portMemory a n t s r).map (compactRow lab) := by
have hPort (f : ℕ) (hF : f < 19) : port n t s f 0 < sharedLimit n t := by
rcases s with ⟨start,j⟩
have hh := layout_mem.mp hs
exact port_lt_shared hh.1 hh.2.1 hF (by unfold layoutHorizon; positivity)
unfold slotCompactMemory portMemory
rw [hFrame _ (hPort _ (by omega)), hFrame _ (hPort _ (by omega))]
by_cases h : a (port n t s (3+5*r) 0) = true
· have h0 := hLabel 0 (by decide) h
have h1 := hLabel 1 (by decide) h
have h2 := hLabel 2 (by decide) h
have hh0 : 5+5*r+0 = 3+5*r+2 := by omega
have hh1 : 5+5*r+1 = 3+5*r+3 := by omega
have hh2 : 5+5*r+2 = 3+5*r+4 := by omega
rw [hh0] at h0
rw [hh1] at h1
rw [hh2] at h2
simp only [h,if_true,Option.map_some,h0,h1,h2,compactRow]
· simp only [h,Bool.false_eq_true,if_false,Option.map_none]
end CNFEncComplexity.Robson
/- RobsonMemLanesLocal -/
namespace CNFEncComplexity.Robson
open CookLevin
def memoryTierSlots (t j : ℕ) : List (ℕ × ℕ) :=
(layoutSlots t).filter fun s => j-2 ≤ s.2
def memoryTierRows (t j : ℕ) : ℕ := 6*(memoryTierSlots t j).length
def memoryGroupCap (j : ℕ) : ℕ := 2^(2^j)
def memoryGroupCount (t j : ℕ) : ℕ := memoryTierRows t j / memoryGroupCap j + 1
theorem memoryTierRows_width (t j : ℕ) : memoryTierRows t j * 2^j ≤ 48*layoutHorizon t := by
have h := slotsAtLeast_bound t (j-2)
have hD := Nat.div_mul_le_self (2*layoutHorizon t) (2^(j-2))
have hW : 2^j ≤ 4*2^(j-2) := by
have hh : j ≤ 2+(j-2) := by omega
simpa [pow_add] using Nat.pow_le_pow_right (by decide : 0 < (2:ℕ)) hh
unfold memoryTierRows memoryTierSlots
calc
6 * _ * 2^j ≤ 6 * ((2*layoutHorizon t)/2^(j-2)) * (4*2^(j-2)) :=
Nat.mul_le_mul (Nat.mul_le_mul_left _ h) hW
_ = 24*(((2*layoutHorizon t)/2^(j-2))*2^(j-2)) := by ring
_ ≤ 48*layoutHorizon t := (Nat.mul_le_mul_left 24 hD).trans_eq (by ring)
theorem memoryGroupCount_cap (t j : ℕ) :
memoryTierRows t j ≤ memoryGroupCap j * memoryGroupCount t j := by
have hq : 0 < memoryGroupCap j := by unfold memoryGroupCap; positivity
have hMod := Nat.mod_lt (memoryTierRows t j) hq
have hDiv := Nat.div_add_mod (memoryTierRows t j) (memoryGroupCap j)
unfold memoryGroupCount
rw [Nat.mul_add,Nat.mul_one]
omega
/-- Compressed observations retain the source chronology and are small enough
to use both the global label bound and the original slot width. -/
structure PackedSlots (α : Assignment) (n t b : ℕ) (dict : List WordEdge)
(packed : (ℕ×ℕ) → List ObservedAccess) : Prop where
labels : ∀ s ∈ layoutSlots t, List.Forall₂ (ObservedLabels b dict) (slotRows α n t s) (packed s)
widths : ∀ s ∈ layoutSlots t, ∀ r ∈ packed s,
r.action.address.size ≤ min (2^s.2) b+1 ∧
r.action.value.size ≤ min (2^s.2) b+1 ∧ r.old.size ≤ min (2^s.2) b+1
def packMemoryStream (t : ℕ) (packed : (ℕ×ℕ) → List ObservedAccess) : List ObservedAccess :=
(layoutSlots t).flatMap packed
private theorem atTier_append' (j : ℕ) (ps qs : List TierRecord) :
atTier j (ps++qs) = atTier j ps ++ atTier j qs := by
simp [atTier,List.filter_append]
private theorem tieredObs_append (l r : List ObservedAccess) :
tieredObservations bitTier (l++r) = tieredObservations bitTier l ++ tieredObservations bitTier r := by
simp [tieredObservations,List.flatMap_append]
private theorem lane_padding {A : Type} (l : List A) (n : ℕ) :
((l.map some) ++ List.replicate n none).filterMap id = l := by
rw [List.filterMap_append,List.filterMap_map]
have hx : (List.replicate n (none : Option A)).filterMap id = [] := by
apply List.filterMap_eq_nil_iff.mpr
intro a ha
exact List.eq_of_mem_replicate ha
simp [hx]
def perSlotTierRows (j : ℕ) (rows : List ObservedAccess) : List (Option LocalRecord) :=
let l := atTier j (tieredObservations bitTier rows)
(l.map some) ++ List.replicate (6-l.length) none
def memoryTierLanes (t j : ℕ) (packed : (ℕ×ℕ) → List ObservedAccess) : List (Option LocalRecord) :=
(memoryTierSlots t j).flatMap (fun s => perSlotTierRows j (packed s))
private theorem packed_length {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
{s : ℕ×ℕ} (hs : s ∈ layoutSlots t) : (p s).length ≤ 3 := by
have hL := (h.labels s hs).length_eq
rw [← hL]
simpa [slotRows] using (List.length_filterMap_le (f := portMemory α n t s) (l:=List.range 3))
theorem memoryTierLanes_length {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) (j : ℕ) :
(memoryTierLanes t j p).length = memoryTierRows t j := by
have hLength (xs : List (ℕ×ℕ)) (hx : ∀ s ∈ xs, s ∈ layoutSlots t) :
(xs.flatMap (fun s => perSlotTierRows j (p s))).length = 6*xs.length := by
induction xs with
| nil => rfl
| cons s ss ih =>
have hS := packed_length h (hx s (by simp))
have hh := tieredObservations_length bitTier (p s)
have hF : (atTier j (tieredObservations bitTier (p s))).length ≤
(tieredObservations bitTier (p s)).length := by
simpa [atTier] using List.length_filter_le
(fun r : TierRecord => r.addr.1=j) (tieredObservations bitTier (p s))
rw [List.flatMap_cons,List.length_append,List.length_cons,
ih (fun s hs => hx s (List.mem_cons_of_mem _ hs))]
simp only [perSlotTierRows,List.length_append,List.length_map,List.length_replicate]
omega
exact hLength _ (fun s hs => (List.mem_filter.mp hs).1)
private theorem packed_eligible {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
{s : ℕ×ℕ} (hs : s ∈ layoutSlots t) {r : TierRecord}
(hr : r ∈ tieredObservations bitTier (p s)) : r.addr.1 ≤ s.2+2 := by
obtain ⟨obs,ho,hMem⟩ := List.mem_flatMap.mp hr
obtain ⟨ha,hv,hold⟩ := h.widths s hs obs ho
have hm : min (2^s.2) b + 1 ≤ 2^s.2+1 := Nat.add_le_add_right (min_le_left _ _) _
have hx := tieredRow_eligible (s:=s) (r:=obs) (f:=id) (ha.trans hm) (hv.trans hm) (hold.trans hm)
exact hx r hMem
theorem memoryTierLanes_projection {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) (j : ℕ) :
(memoryTierLanes t j p).filterMap id =
atTier j (tieredObservations bitTier (packMemoryStream t p)) := by
have hProj (xs : List (ℕ×ℕ)) (hx : ∀ s ∈ xs, s ∈ layoutSlots t) :
(((xs.filter fun s => j-2 ≤ s.2).flatMap (fun s => perSlotTierRows j (p s))).filterMap id) =
atTier j (tieredObservations bitTier (xs.flatMap p)) := by
induction xs with
| nil => rfl
| cons s ss ih =>
have ht := ih (fun r hr => hx r (List.mem_cons_of_mem _ hr))
rw [List.flatMap_cons,tieredObs_append,atTier_append']
by_cases hj : j-2 ≤ s.2
· simp only [List.filter_cons,decide_eq_true_eq,hj,if_true,List.flatMap_cons,
List.filterMap_append,ht]
have he : (perSlotTierRows j (p s)).filterMap id =
atTier j (tieredObservations bitTier (p s)) := lane_padding _ _
rw [he]
· have hEmpty : atTier j (tieredObservations bitTier (p s)) = [] := by
unfold atTier
have hFilter : ((tieredObservations bitTier (p s)).filter fun r => r.addr.1=j) = [] := by
apply List.filter_eq_nil_iff.mpr
intro r hr
have hh := packed_eligible h (hx s (by simp)) hr
have hne : r.addr.1 ≠ j := by omega
simp [hne]
simp [hFilter]
simp only [List.filter_cons,decide_eq_true_eq,hj,if_false,ht,hEmpty,List.nil_append]
exact hProj _ (fun _ hs => hs)
private theorem related_append {A B : Type} {R : A → B → Prop}
{l m : List A} {l' m' : List B} (h : List.Forall₂ R l l') (h' : List.Forall₂ R m m') :
List.Forall₂ R (l++m) (l'++m') := by
induction h with
| nil => exact h'
| cons hr _ ih => exact .cons hr ih
private theorem packMemory_labels {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) :
List.Forall₂ (ObservedLabels b dict) (memoryStream α n t) (packMemoryStream t p) := by
have hJoin (ls : List (ℕ×ℕ)) (hm : ∀ s ∈ ls, s ∈ layoutSlots t) :
List.Forall₂ (ObservedLabels b dict) (ls.flatMap (slotRows α n t)) (ls.flatMap p) := by
induction ls with
| nil => exact .nil
| cons s ss ih =>
exact related_append (h.labels s (hm s (by simp)))
(ih (fun r hr => hm r (List.mem_cons_of_mem _ hr)))
exact hJoin _ (fun _ hs => hs)
theorem memoryTierLanes_exact {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
{p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
(good : WordEdge.Interned dict) :
observedMemoryValid (fun _ => 0) (memoryStream α n t) ↔
∀ j < (b+1).size+1,
TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j) (memoryTierLanes t j p)
(fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
have hFits : ∀ r ∈ tieredObservations bitTier (packMemoryStream t p), TierRecordFits (b+1) r := by
intro r hr
obtain ⟨o,ho,hex⟩ := List.mem_flatMap.mp hr
obtain ⟨s,hs,ho'⟩ := List.mem_flatMap.mp ho
obtain ⟨ha,hv,hold⟩ := h.widths s hs o ho'
have hm : min (2^s.2) b+1 ≤ b+1 := Nat.add_le_add_right (min_le_right _ _) _
exact tieredAccess_fits (ha.trans hm) (hv.trans hm) (hold.trans hm) r hex
exact observed_compactBatches_iff good (packMemory_labels h) hFits (memoryGroupCount t)
(fun j => memoryTierLanes t j p) (fun j _ => memoryTierLanes_projection h j)
(fun j _ => (memoryTierLanes_length h j).trans_le (memoryGroupCount_cap t j))
end CNFEncComplexity.Robson
/- RobsonTierBridge -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem sorterTierCertificate_eq (R w tier : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment) :
sorterTierCertificate R w tier src a ↔
TierBatchCertificate (2^w) (R/2^w+1) (rawMemoryRows a w R src) (groupInitial (some tier)) := by
by_cases hs : R ≤ 2^w
· simp [sorterTierCertificate,TierBatchCertificate,rawMemoryRows,hs]
· simp [sorterTierCertificate,TierBatchCertificate,rawMemoryRows,hs,sorterCount_split hs]
theorem tierBatch_mission_certificate (t j base z o : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment)
(hzBase : z < base) (hoBase : o < base)
(hData : ∀ i < memoryTierRows t j, ∀ k < memLaneWidth (2^j) 0, src i k < base)
(hz : a z = false) (ho : a o = true) :
(∃ b : Assignment,
(∀ k, k < base ∨ sorterTierTop (memoryTierRows t j) (2^j) base ≤ k → b k = a k) ∧
(∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j base z o src, g.Holds b)) ↔
TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j)
(rawMemoryRows a (2^j) (memoryTierRows t j) src) (groupInitial (some j)) :=
(tierBatchGates_exact _ _ _ _ _ _ _ _ hzBase hoBase hData hz ho (bitTier_initial_restricted j)).trans
(sorterTierCertificate_eq ..)
theorem tierBatchGates_layout_budget (t j base z o : ℕ) (src : ℕ → ℕ → ℕ) :
(tierBatchGates (memoryTierRows t j) (2^j) j base z o src).length ≤ 393216*layoutHorizon t*2^j := by
calc
_ ≤ 8192*memoryTierRows t j*2^j*2^j := tierBatchGates_budget _ _ _ _ _ _ _ (Nat.two_pow_pos _)
_ = (8192*(memoryTierRows t j*2^j))*2^j := by ring
_ ≤ (8192*(48*layoutHorizon t))*2^j :=
Nat.mul_le_mul_right _ (Nat.mul_le_mul_left _ (memoryTierRows_width t j))
_ = _ := by ring
private theorem sorter_sum_geometric (n : ℕ) : (∑ j ∈ Finset.range n, (2:ℕ)^j) ≤ 2^n := by
induction n with
| zero => simp
| succ n ih =>
rw [Finset.sum_range_succ,pow_succ]
omega
theorem tierBatchGates_total_budget (t b : ℕ) (cost : ℕ → ℕ)
(hCost : ∀ j < (b+1).size+1, cost j ≤ 393216*layoutHorizon t*2^j) :
(∑ j ∈ Finset.range ((b+1).size+1), cost j) ≤ 1572864*layoutHorizon t*(b+1)+786432*layoutHorizon t := by
have h := Nat.size_pos.mpr (show 0 < b+1 by omega)
have hp : 2^(b+1).size ≤ 2*(b+1)+1 := by
have hk : (b+1).size-1 < (b+1).size := by omega
have hsmall := Nat.lt_size.mp hk
calc
_ = 2^((b+1).size-1)*2 := by conv_lhs => rw [show (b+1).size = (b+1).size-1+1 by omega]; rw [pow_succ]
_ ≤ _ := by omega
calc
_ ≤ ∑ j ∈ Finset.range ((b+1).size+1), 393216*layoutHorizon t*2^j :=
Finset.sum_le_sum fun j hj => hCost j (Finset.mem_range.mp hj)
_ = (393216*layoutHorizon t)*(∑ j ∈ Finset.range ((b+1).size+1), 2^j) := by rw [Finset.mul_sum]
_ ≤ (393216*layoutHorizon t)*2^((b+1).size+1) :=
Nat.mul_le_mul_left _ (sorter_sum_geometric _)
_ = (786432*layoutHorizon t)*2^(b+1).size := by rw [pow_succ]; ring
_ ≤ (786432*layoutHorizon t)*(2*(b+1)+1) := Nat.mul_le_mul_left _ hp
_ = _ := by ring
end CNFEncComplexity.Robson
/- RobsonTierBatchNative -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
section
variable {A : Type} {e : A ↪ List Bool}
set_option maxHeartbeats 1000000 in
theorem tierWindowGates_polytime {R w tier base z o g : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary)
(ht : ComputableTidilyInPolyTime tier e encUnary)
(hb : ComputableTidilyInPolyTime base e encUnary)
(hz : ComputableTidilyInPolyTime z e encUnary)
(ho : ComputableTidilyInPolyTime o e encUnary)
(hg : ComputableTidilyInPolyTime g e encUnary)
(hs : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime
(fun a => tierWindowGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a) (g a)) e
(encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
let e₃ := encPair e₂ encUnary
let e₄ := encPair e₃ encUnary
let e₅ := encPair e₄ encUnary
let f₁ := fst e encUnary
let f₂ := fst e₁ encUnary
let f₃ := fst e₂ encUnary
let f₄ := fst e₃ encUnary
let f₅ := fst e₄ encUnary
let a := f₁.comp f₂
let i := (snd e encUnary).comp f₂
let j := snd e₁ encUnary
let p := a.comp (f₃.comp (f₄.comp f₅))
let k := (snd e₂ encUnary).comp (f₄.comp f₅)
let u := (snd e₃ encUnary).comp f₅
let b := snd e₄ encUnary
have hSnap : ComputableTidilyInPolyTime
(fun q : (((((A×ℕ)×ℕ)×ℕ)×ℕ)×ℕ) =>
sorterSnapshotName (R q.1.1.1.1.1) (w q.1.1.1.1.1) (base q.1.1.1.1.1) q.1.1.2 q.1.2 q.2)
e₅ encUnary :=
sorterSnapshotName_poly (hr.comp p) (hw.comp p) (hb.comp p) k u b
let proj : ComputableTidilyInPolyTime
(fun q : (((A×ℕ)×ℕ)×ℕ)×ℕ => ((q.1.1.1.1,q.1.2),q.2)) e₄ e₂ :=
(((a.comp (f₃.comp f₄)).prod ((snd e₂ encUnary).comp f₄))).prod (snd e₃ encUnary)
have hData := hs.comp proj
have hSrc : ComputableTidilyInPolyTime (fun q : (A×ℕ)×ℕ =>
memoryWindowSource (w q.1.1) (tier q.1.1) (sorterCappedCap (R q.1.1) (w q.1.1))
(R q.1.1) (g q.1.1) (z q.1.1) (o q.1.1) (src q.1.1)
(sorterSnapshotName (R q.1.1) (w q.1.1) (base q.1.1)) q.1.2 q.2) e₂ encUnary :=
memoryWindowSource_poly (A := (A×ℕ)×ℕ) (e := e₂) (src := fun p => src p.1.1)
(snap := fun p => sorterSnapshotName (R p.1.1) (w p.1.1) (base p.1.1))
(hw.comp a) (ht.comp a) ((sorterCappedCap_poly hr hw).comp a)
(hr.comp a) (hg.comp a) (hz.comp a) (ho.comp a) i j hData hSnap
unfold tierWindowGates
exact memSortGates_polytime (A := A) (e := e)
(src := fun a i j => memoryWindowSource (w a) (tier a) (sorterCappedCap (R a) (w a))
(R a) (g a) (z a) (o a) (src a) (sorterSnapshotName (R a) (w a) (base a)) i j)
hw (sorterHeight_poly hr hw) (sorterGroupBase_poly hr hw hb hg) (sorterTierCode_poly hr hw ht)
(sorterWires_poly hr hw) hSrc
theorem tierBatchGates_polytime {R w tier base z o : A → ℕ} {src : A → ℕ → ℕ → ℕ}
(hr : ComputableTidilyInPolyTime R e encUnary)
(hw : ComputableTidilyInPolyTime w e encUnary)
(ht : ComputableTidilyInPolyTime tier e encUnary)
(hb : ComputableTidilyInPolyTime base e encUnary)
(hz : ComputableTidilyInPolyTime z e encUnary)
(ho : ComputableTidilyInPolyTime o e encUnary)
(hs : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
(encPair (encPair e encUnary) encUnary) encUnary) :
ComputableTidilyInPolyTime
(fun a => tierBatchGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a)) e
(encList gateEnc) := by
let e₁ := encPair e encUnary
let e₂ := encPair e₁ encUnary
let a := fst e encUnary
let f₁ := fst e₁ encUnary
let f₂ := fst e₂ encUnary
have hData := hs.comp (((a.comp (f₁.comp f₂)).prod ((snd e₁ encUnary).comp f₂)).prod
(snd e₂ encUnary))
unfold tierBatchGates
exact flatMapWithInput
(f := fun a g => tierWindowGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a) g)
(range.comp (sorterCount_poly hr hw))
(tierWindowGates_polytime (A := A×ℕ) (e := e₁) (src := fun p => src p.1)
(hr.comp a) (hw.comp a) (ht.comp a) (hb.comp a) (hz.comp a)
(ho.comp a) (snd e encUnary) hData)
end
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).