Completeness of the shared slotted RAM certificate
ProvedCNFEncComplexity.Robson.completePortscomplexity-theoryramsat
For any RAM program, input length , and time bound , an accepting execution within bit cost gives a shared port assignment passing the three certificate tests. The first variables are the original input. The remaining shared variables encode disjoint occupied dyadic intervals, the source machine’s chronological memory observations, and its sequence of reads. The construction allows .
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints
Formal statement
namespace CNFEncComplexity.Robson theorem completePorts : HasCompletePorts := by sorry end CNFEncComplexity.Robson
Source
Robson, An O(T log T) reduction from RAM computations to satisfiability, TCS 82 (1991), pp. 141–149, Sections 2 and 3.1, https://www.sciencedirect.com/science/article/pii/0304397591901774. Dyadic trace certificate adapted to Krapivin–Przybocki–Subercaseaux, arXiv:2611.05614, Theorem 10.