Exactness and size bound of the tier memory gate list
ProvedCNFEncComplexity.Robson.memoryTierGateList_exact_budgetcomplexity-theorysatisfiability
For any normalizer satisfying the uniform normalizer specification, the tier memory gate list has size at most 3000000000 times the layout time bound plus one times its bit length plus one. On a well-formed layout, the gates admit an extension exactly when the observed memory stream is valid.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierGateList open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.Robson.memoryTierGateList_exact_budget (normalize : ℕ → ℕ → List Gate) (stop : ℕ → ℕ → ℕ)
(spec : NormalizationSpec normalize stop) :
(∀ n t, (rawMemoryGates normalize stop n t).length ≤ 3000000000 * (t+1) * (t.size+1)) ∧
(∀ (n t : ℕ) (a : Assignment), SlotsWellFormed a n t →
(ExtendsWith (sharedLimit n t) (rawMemoryGates normalize stop n t) a ↔
observedMemoryValid (fun _ => 0) (memoryStream a n t))) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).