Soundness of the slotted RAM certificate
ProvedCNFEncComplexity.Robson.slotted_checks_soundcomplexity-theoryramsat
Fix a nondeterministic RAM program, an input length , and a bit-cost time bound . Suppose the same assignment passes three tests: a local instruction trace within the original budget, the chronological memory log, and the successive input symbols. Then the machine accepts the assignment’s input bits within time .
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson
theorem slotted_checks_sound (prog : List Instr) (n t : ℕ) (α : Assignment)
(h : ∀ j : Fin 3, Checks j prog n t α) : AcceptsWithin prog (inputTape α n) t := by sorry
end CNFEncComplexity.RobsonSource
Trace verification and consistency, Sections 2 and 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.