A bounded uniform gate generator for the RAM trace
ProvedCNFEncComplexity.Robson.gateComponent_tracecomplexity-theoryramsat
Fix an instruction-count bound . A deterministic polynomial-time construction produces a Boolean gate list with gates for the local instruction trace, its original bit-cost clock, and the disjoint occupied intervals. For any assignment of the shared ports, it has an extension to its auxiliary wires exactly when the corresponding trace check holds. The constant depends only on .
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson theorem gateComponent_trace (P : ℕ) : GateComponent P 0 := by sorry end CNFEncComplexity.Robson
Source
Section 3.1. 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.