Word dimensions and uniform Boolean word gates for RAM memory
DefinitionCNFEncComplexity_RobsonMemoryParameterscomplexity-theorysatisfiability
Computes the trie chunk width and tier counts, and generates fixed-width word copies, padded wire access, and constant-word gates in polynomial time.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives
set_option maxHeartbeats 4000000
set_option linter.all false
/- RobsonMemoryDimensions -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
def trieLevel (t : ℕ) : ℕ :=
min (layoutHeight t) (slotLevel (18*layoutHorizon t).size)
def trieWidth (t : ℕ) : ℕ := 2^trieLevel t
theorem trieLevel_cap (t : ℕ) : trieLevel t ≤ layoutHeight t := min_le_left _ _
theorem trieWidth_in_horizon (t : ℕ) : trieWidth t ≤ layoutHorizon t :=
Nat.pow_le_pow_right (by decide) (trieLevel_cap t)
theorem trieWidth_allow (t : ℕ) :
layoutHorizon t ≤ trieWidth t ∨ 18*layoutHorizon t < 2^trieWidth t := by
let b := (18*layoutHorizon t).size
by_cases h : layoutHeight t ≤ slotLevel b
· left
change layoutHorizon t ≤ 2^(min (layoutHeight t) (slotLevel b))
rw [min_eq_left h]
exact le_refl _
· have h' : slotLevel b ≤ layoutHeight t := by omega
right
change 18*layoutHorizon t < 2^(2^min (layoutHeight t) (slotLevel b))
rw [min_eq_right h']
exact (Nat.lt_size_self _).trans_le (Nat.pow_le_pow_right (by decide) (le_slotWidth b))
theorem trieWidth_bound (t : ℕ) : trieWidth t ≤ 22*(t.size+1) := by
let m := 18*layoutHorizon t
have hm : m.size ≤ t.size+11 := by
apply Nat.size_le.mpr
have hHor : layoutHorizon t ≤ 8*(9*t+1) := by
change slotWidth (4*(9*t+1)) ≤ _
have h := slotWidth_le_double (cost:=4*(9*t+1)) (by omega)
omega
rw [pow_add]
norm_num
have ht := Nat.lt_size_self t
unfold m
omega
have hb : 0 < m.size := Nat.size_pos.mpr (by
dsimp [m,layoutHorizon]
positivity)
have hw := slotWidth_le_double hb
have h' : trieWidth t ≤ slotWidth m.size :=
Nat.pow_le_pow_right (by decide) (min_le_right _ _)
omega
set_option maxHeartbeats 2000000 in
theorem trieLevel_poly : ComputableTidilyInPolyTime trieLevel encUnary encUnary := by
have hx := unary_mul.comp ((const 18).prod layoutHorizon_poly)
have hSize := unary_size_poly.comp hx
have hLevel := unary_size_poly.comp (unary_sub.comp (hSize.prod (const 1)))
exact unary_min.comp (layoutHeight_poly.prod hLevel)
theorem trieWidth_poly : ComputableTidilyInPolyTime trieWidth encUnary encUnary :=
unary_pow2_of_bound trieLevel_poly layoutHorizon_poly trieWidth_in_horizon
end CNFEncComplexity.Robson
/- RobsonTraceBasicNative -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime
theorem dynamic_pin_poly {A : Type} {e : A ↪ List Bool} {r : A → ℕ} {b : A → Bool}
(hr : ComputableTidilyInPolyTime r e encUnary) (hb : ComputableTidilyInPolyTime b e encBool) :
ComputableTidilyInPolyTime (fun a => Gate.pin (r a) (b a)) e gateEnc := by
have hh := hb.ite' (gate_pin true hr) (gate_pin false hr)
convert hh using 1
funext a
cases hb : b a <;> simp
theorem wordConst_poly {A : Type} {e : A ↪ List Bool} {w v : A → ℕ} {key : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e encUnary)
(hv : ComputableTidilyInPolyTime v e encNat)
(hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2)
(encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => wordConst (w a) (key a) (v a)) e (encList gateEnc) := by
have hBit := binary_testBit (hv.comp (fst e encUnary)) (snd e encUnary)
exact mapWithInput (range.comp hw) (dynamic_pin_poly hk hBit)
theorem wordCopy_poly {A : Type} {e : A ↪ List Bool} {w : A → ℕ} {l r : A → ℕ→ℕ}
(hw : ComputableTidilyInPolyTime w 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 => wordCopy (w a) (l a) (r a)) e (encList gateEnc) := by
exact mapWithInput (range.comp hw) (gate_copy hl hr)
theorem boundedWordConst_poly {A : Type} {e : A ↪ List Bool} {w v : A → ℕ} {key : A → ℕ → ℕ}
(hw : ComputableTidilyInPolyTime w e encUnary)
(hv : ComputableTidilyInPolyTime v e encNat)
(hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2)
(encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => boundedWordConst (w a) (key a) (v a)) e (encList gateEnc) := by
have hh := (ComputableTidilyInPolyTime.binary_lt' hv (binary_two_pow.comp hw)).ite'
(wordConst_poly hw hv hk) (const [.assert []])
simpa only [boundedWordConst,decide_eq_true_eq,Function.comp_def] using hh
theorem paddedKey_poly {A : Type} {e : A ↪ List Bool} {n z : A → ℕ} {k : A → ℕ → ℕ}
(hn : ComputableTidilyInPolyTime n e encUnary)
(hz : ComputableTidilyInPolyTime z e encUnary)
(hk : ComputableTidilyInPolyTime (fun p : A×ℕ => k p.1 p.2) (encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun p : A×ℕ => paddedKey (n p.1) (z p.1) (k p.1) p.2)
(encPair e encUnary) encUnary := by
have hDim := fst e encUnary
have hIdx := snd e encUnary
have hh := (unary_lt' hIdx (hn.comp hDim)).ite' hk (hz.comp hDim)
simpa only [paddedKey,decide_eq_true_eq, Function.comp_def] using hh
theorem paddedWordCopy_poly {A : Type} {e : A ↪ List Bool} {w n m z : A → ℕ}
{l r : A → ℕ→ℕ}
(hw : ComputableTidilyInPolyTime w e encUnary)
(hn : ComputableTidilyInPolyTime n e encUnary)
(hm : ComputableTidilyInPolyTime m e encUnary)
(hz : ComputableTidilyInPolyTime z 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 => paddedWordCopy (w a) (n a) (m a) (z a) (l a) (r a))
e (encList gateEnc) :=
wordCopy_poly hw (paddedKey_poly hn hz hl) (paddedKey_poly hm hz hr)
theorem exactSumGates_poly {A : Type} {e : A ↪ List Bool} {base w : A → ℕ} {l r o : A → ℕ→ℕ}
(hb : ComputableTidilyInPolyTime base e encUnary)
(hw : ComputableTidilyInPolyTime w 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)
(ho : ComputableTidilyInPolyTime (fun p : A×ℕ => o p.1 p.2) (encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => exactSumGates (base a) (w a) (l a) (r a) (o a))
e (encList gateEnc) := by
have hp : ComputableTidilyInPolyTime (fun a => rippleCarryWire (base a) (w a)) e encUnary := by
unfold rippleCarryWire
fun_prop
have hk : ComputableTidilyInPolyTime (fun p : A×ℕ => rippleBitWire (base p.1) p.2)
(encPair e encUnary) encUnary := by
have hb' := hb.comp (fst e encUnary)
unfold rippleBitWire
fun_prop
exact listAppend' (rippleCircuit_polytime false hb hw hl hr)
(cons' (gate_pin false hp) (wordCopy_poly hw ho hk))
theorem nonzeroWord_poly {A : Type} {e : A ↪ List Bool} {w : A → ℕ} {key : A → ℕ→ℕ}
(hw : ComputableTidilyInPolyTime w e encUnary)
(hk : ComputableTidilyInPolyTime (fun p : A×ℕ => key p.1 p.2) (encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime
(fun a => CNFEncComplexity.Robson.BinaryPort.nonzeroGates ⟨w a,key a⟩) e (encList gateEnc) := by
have hLiteral := unary_add.comp ((unary_mul.comp ((const 2).prod hk)).prod (const 1))
have hFields := mapWithInput (f:=fun a i => 2*key a i+1) (range.comp hw) hLiteral
have h := gate_assert (c:=fun a => (List.range (w a)).map (fun i => .Pos (key a i))) (by
simpa only [clauseN,List.map_map,Function.comp_def,literalN] using hFields)
exact cons' h (const [])
end CNFEncComplexity.RobsonCNF
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).