Interface for a uniform RAM memory normalizer
DefinitionCNFEncComplexity_RobsonMemoryNormalizationInterfacecomplexity-theorysatisfiability
An interface for a family of normalization gates and its wire boundary. It specifies polynomial-time generation, the gate bound, preservation of the prescribed wire region, extension on well-formed layouts, and the correctness of labels at the shared normalized ports.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieSlots
import Definitions.Def_CNFEncComplexity_RobsonMemoryParameters
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM
structure NormalizationSpec (gates : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ) : Prop where
gates_poly : ComputableTidilyInPolyTime (fun p : ℕ × ℕ => gates p.1 p.2)
(encPair encUnary encUnary) (encList gateEnc)
stop_poly : ComputableTidilyInPolyTime (fun p : ℕ × ℕ => stop p.1 p.2)
(encPair encUnary encUnary) encUnary
length_le : ∀ n t, (gates n t).length ≤ 5000 * (layoutHorizon t * (layoutHeight t + 1))
room : ∀ n t, normalizeAfter (sharedLimit n t + 2) t ≤ stop n t
frame : ∀ n t (a b : Assignment),
(∀ i < stop n t, b i = a i) → GateSat a (gates n t) → GateSat b (gates n t)
extend_layout : ∀ n t (a : Assignment), SlotsWellFormed a n t →
∃ b : Assignment,
(∀ i, i < sharedLimit n t + 2 ∨ stop n t ≤ i → b i = a i) ∧
GateSat b (gates n t)
sound : ∀ n t (a : Assignment), GateSat a (gates n t) →
∃ dict : List WordEdge, WordEdge.Interned dict ∧
PackedSlots a n t (trieWidth t) dict (slotCompactRows a (sharedLimit n t + 2) n t (trieLevel t))
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).