Existence of a uniform RAM memory normalizer
ProvedCNFEncComplexity.Robson.memoryNormalizer_existscomplexity-theorysatisfiability
A single family of Boolean gate lists normalizes the words in the dyadic RAM layout. Its gates and the end of its reserved wire interval are polynomial-time computable. For every well-formed layout the gate constraints admit an extension, and any satisfying assignment gives a consistent dictionary labeling the shared word slots. The family also has the stated layout-size and wire-preservation bounds.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryNormalizationInterface open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF
Formal statement
theorem CNFEncComplexity.Robson.memoryNormalizer_exists : ∃ gates stop, NormalizationSpec gates stop := by sorry
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).