The tier memory gate list from a uniform normalizer
DefinitionCNFEncComplexity_RobsonMemoryTierGateListcomplexity-theorysatisfiability
The gate list assembled from the supplied normalizer, tier emission, and sorted-window checks. The definitions identify the single gate family whose generation, exactness, and size are needed for the memory gate component.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierRowGates
import Definitions.Def_CNFEncComplexity_RobsonMemoryNormalizationInterface
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
/-- All tiers read the same low. Their scratch variables occupy distinct residue classes. -/
def memoryTierWire (low levels j r : ℕ) : ℕ :=
if r < low then r else low+levels*(r-low)+j
def memoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (j : ℕ) : List Gate :=
(tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j)).map
(Gate.rename (memoryTierWire low (emitLevels t) j))
def allMemoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) : List Gate :=
(List.range (emitLevels t)).flatMap (memoryTierGates t low z o src)
def boundedMemoryTierWidth (t j : ℕ) : ℕ := 2^(min j (emitLevels t-1))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
abbrev EmitLane := (ℕ×ℕ)×ℕ×Bool
def emitLaneList (slots : List (ℕ×ℕ)) : List EmitLane :=
slots.flatMap fun s => (List.range 3).flatMap (fun r => [(s,r,false),(s,r,true)])
def emitLaneKey (base region n t j z o : ℕ) (p : EmitLane) : ℕ→ℕ :=
let u := emitInputs base n t p.1 p.2.1
let start := emitBlockBase region t j p.1 p.2.1+8
if p.2.2 then emitSecondRow u (2^j) z o start else emitFirstRow u (2^j) z o start
def emitSource (base region n t j z o : ℕ) (slots : List (ℕ×ℕ)) (k : ℕ) : ℕ→ℕ :=
match (emitLaneList slots)[k]? with
| none => fun _ => z
| some p => emitLaneKey base region n t j z o p
def compactSlotOptions (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
(List.range 3).map (slotCompactMemory a base n t (trieLevel t) s)
abbrev EmitWidthBlock (t : ℕ) := {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3
abbrev EmitCoreBlock (t : ℕ) := Fin (emitLevels t) × {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3
def emitCoreLayoutGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
(List.range (emitLevels t)).flatMap fun j => emitTierGateList base region n t j z (slots j)
def emitAllGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
emitWidthLayoutGates base region n t ++ emitCoreLayoutGates base region n t z slots
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
def emitSlotTier (j : ℕ) (slots : List (Option ObservedAccess)) : List (Option LocalRecord) :=
slots.flatMap (emitTier j)
def memoryEmitLanes (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
List (Option LocalRecord) :=
(memoryTierSlots t j).flatMap fun s => emitSlotTier j (packed s)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
def memoryZero (n t : ℕ) : ℕ := sharedLimit n t
def memoryOne (n t : ℕ) : ℕ := sharedLimit n t+1
def memoryNormalizeBase (n t : ℕ) : ℕ := sharedLimit n t+2
def memorySortBase (stop : ℕ → ℕ → ℕ) (n t : ℕ) : ℕ := emitBlockTop (stop n t) t
def memoryConstants (n t : ℕ) : List Gate :=
[.pin (memoryZero n t) false,.pin (memoryOne n t) true]
def memoryEmitter (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
emitAllGates (memoryNormalizeBase n t) (stop n t) n t (memoryZero n t) (memoryTierSlots t)
def capMemoryTier (t j : ℕ) : ℕ := min j (emitLevels t-1)
theorem capMemoryTier_lt (t j : ℕ) : capMemoryTier t j < emitLevels t := by
unfold capMemoryTier
have hp : 0 < emitLevels t := Nat.succ_pos _
exact (min_le_right _ _).trans_lt (by omega)
def memorySorterSource (stop : ℕ → ℕ → ℕ) (n t j : ℕ) : ℕ → ℕ → ℕ :=
let k := capMemoryTier t j
emitSource (memoryNormalizeBase n t) (stop n t) n t k
(memoryZero n t) (memoryOne n t) (memoryTierSlots t k)
theorem memorySorterSource_eq (stop : ℕ → ℕ → ℕ) (n t j : ℕ) (hj : j < emitLevels t) :
memorySorterSource stop n t j = emitSource (memoryNormalizeBase n t) (stop n t) n t j
(memoryZero n t) (memoryOne n t) (memoryTierSlots t j) := by
have hm : capMemoryTier t j = j := min_eq_left (by omega)
simp [memorySorterSource, hm]
def memorySorter (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
allMemoryTierGates t (memorySortBase stop n t) (memoryZero n t) (memoryOne n t) (memorySorterSource stop n t)
def rawMemoryGates (normalize : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ) (n t : ℕ) : List Gate :=
((memoryConstants n t++normalize n t)++memoryEmitter stop n t)++memorySorter stop n t
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).