A bounded uniform gate generator for consistent RAM memory
ProvedCNFEncComplexity.Robson.gateComponent_memorycomplexity-theoryramsat
Fix an instruction-count bound . A deterministic polynomial-time construction produces Boolean gates for the memory consistency test on the shared interval ports. An extension exists exactly when the occupied slots are well formed and each observation agrees with the last write to the same address, starting with all cells zero. The constant depends only on .
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson theorem gateComponent_memory (P : ℕ) : GateComponent P 1 := by sorry end CNFEncComplexity.Robson
Source
Sections 3.2–3.3. Robson, An O(T log T) reduction from RAM computations to satisfiability, TCS 82 (1991), pp. 141–149, https://www.sciencedirect.com/science/article/pii/0304397591901774. Adapted to the RAM of Krapivin–Przybocki–Subercaseaux, arXiv:2611.05614, Section 3, Theorem 10.