Bit-cost RAM acceptance as a dyadically scheduled certificate
ProvedCNFEncComplexity.Robson.acceptsWithin_iff_timedObservationcomplexity-theoryramsat
A RAM program accepts an input word within bit cost exactly when its packet trace, chronological memory observations, and successive input symbols admit the stated timed certificate. The original clock includes the accepting halt. The packets fit into disjoint aligned dyadic intervals with horizon at most , without assuming the input length is bounded by .
Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson
theorem acceptsWithin_iff_timedObservation (prog : List Instr) (w : List Bool) (t : ℕ) :
AcceptsWithin prog w t ↔ TimedObservation prog w t := by sorry
end CNFEncComplexity.RobsonSource
Bit-cost accounting, 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.