A bounded uniform gate generator for sequential RAM input
ProvedCNFEncComplexity.Robson.gateComponent_inputcomplexity-theoryramsat
Fix an instruction-count bound . A deterministic polynomial-time construction produces Boolean gates for the sequential input test. An assignment of the shared ports extends to a satisfying assignment exactly when the occupied input symbols, read in chronological order, agree with successive bits of the original input and with the end marker thereafter. The count is independent of input length.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson theorem gateComponent_input (P : ℕ) : GateComponent P 2 := by sorry end CNFEncComplexity.Robson
Source
Section 3.4. 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.