Polynomial-time generation of the tier memory gate list
ProvedCNFEncComplexity.Robson.memoryTierGateList_nativecomplexity-theorysatisfiability
A normalizer satisfying the uniform normalizer specification yields a polynomial-time generator for the corresponding tier memory gate list. The gate list uses the supplied normalizer and wire boundary.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierGateList open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.Robson.memoryTierGateList_native (normalize : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ)
(spec : NormalizationSpec normalize stop) :
ComputableTidilyInPolyTime (fun q : ℕ × ℕ => rawMemoryGates normalize stop q.1 q.2)
(encPair encUnary encUnary) (encList gateEnc) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).