The RAM memory gate component from a uniform normalizer
ProvedCNFEncComplexity.Robson.memoryComponent_of_normalizercomplexity-theorysatisfiability
Given any family of normalization gates satisfying the normalizer contract, tier emission and sorted-window checks construct the full memory gate component for every program bound. The construction uses the gate list and wire boundary supplied by that same normalizer.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryNormalizationInterface open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF
Formal statement
theorem CNFEncComplexity.Robson.memoryComponent_of_normalizer
(gates : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ)
(spec : NormalizationSpec gates stop) (P : ℕ) : GateComponent P 1 := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).