Theorem 10 (Robson's theorem) — for nondeterministic RAM time
ProvedCNFEncComplexity.theorem_10Fix a bound on the number of instructions. There are a constant and a deterministic polynomial-time construction such that for every , every program with at most instructions and every that evaluates in time (nondeterministic RAM, logarithmic cost):
- the construction, given , and , outputs a CNF encoding of with input variables ;
- this encoding has at most clauses;
- consequently
This is Robson's optimized Cook–Levin theorem [Rob91], in the uniform form the paper uses: one formula, with as input variables, works for every input. The proof of Theorem 2 applies it to the advice-free machine of an ANRAM, and the proof of Lemma 11 to the slot-check function .
Formalization Note The construction depends on only, following the paper's convention that the number of instructions is bounded by a fixed constant. Time is measured in Mathlib's Turing.TM2ComputableInPolyTime on the input encRobsonIn (, in unary, then the program), output CookLevin.encodeFormula. No is assumed, as in the printed statement. The proof is in [Rob91].
Differences from the source:
- reading: the number of instructions is upper-bounded by a fixed constant (p.10) → ∀ P, ∃ constants and construction, for all programs with prog.length ≤ P; reason: the paper's convention, made explicit: the constants depend on the bound and on nothing else
- reading: nondeterministic RAM with logarithmic cost (§3.1, informal) → AcceptsWithin: the listed instruction set, sequential read-only input with end marker 2, cost 1 + Σ(size(v)+1) per step; reason: the paper describes Robson's model informally; Õ(·) is insensitive to the usual variations of the instruction set and cost function
- encoding: enc(f) = O(t lg t) → C·(t+1)·log₂(t+2) with C fixed after P; reason: the bare t·lg t vanishes at t ≤ 1, where f may be constant 0 with enc = 1; for t ≥ 2 the two forms are within a constant factor
- reading: constructed deterministically in time polynomial in n + t → TM2ComputableInPolyTime encRobsonIn CookLevin.encodeFormula build, with n and t in unary; reason: polynomial time is model-robust; Mathlib's TM2 is the platform's standard machine model, and polynomial in the stated quantity is polynomial in the input length of this encoding
- encoding: an encoding (φ, X, Y) with input variables x₁, …, xₙ → IsEncoding φ (fun i => i) f, inputs the variables 0, …, n−1, auxiliary variables all others; reason: the construction must name its input variables; any injective renaming gives the same formulas up to variable names
import Mathlib import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_enc import Definitions.Def_CNFEncComplexity_Instr import Definitions.Def_CNFEncComplexity_AcceptsWithin import Definitions.Def_CNFEncComplexity_NRAMEvaluates import Definitions.Def_CNFEncComplexity_encWords import Definitions.Def_CNFEncComplexity_encRobsonIn
namespace CNFEncComplexity
/-- **Theorem 10 (Robson's theorem [Rob91]).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Theorem 10, p.10 (PDF 11): "Let f : {0, 1}ⁿ →
{0, 1}, and suppose that f can be evaluated in time t by a nondeterministic RAM machine. Then,
enc(f) = O(t lg t). Furthermore, such an encoding can be constructed deterministically in time
polynomial in n + t."
For every bound `P` on the number of instructions there are a constant `C` and a polynomial-time
function `build` such that, for every `n`, `t`, every program `prog` with at most `P` instructions and
every `f : {0,1}ⁿ → {0,1}` that `prog` evaluates in time `t` (`NRAMEvaluates`):
1. `build (prog, n, t)` is a CNF encoding of `f` with input variables `0, …, n − 1`;
2. it has at most `C·(t + 1)·log₂(t + 2)` clauses;
3. hence `enc(f) ≤ C·(t + 1)·log₂(t + 2)`.
**Formalization Note.** "we follow Robson in assuming that the number of instructions is upper-bounded
by a fixed constant" (p.10): the constant `C` and the construction depend on `P` only. `O(t lg t)` is
written `C·(t + 1)·log₂(t + 2)`: the bare `t·lg t` vanishes at `t ≤ 1`, where `f` may be constant
`0` with `enc(f) = 1`. The construction receives `n` and `t` in unary and the program
(`encRobsonIn`); polynomial time is Mathlib's `Turing.TM2ComputableInPolyTime`, output
`CookLevin.encodeFormula`. No `t ≥ n` is assumed, as printed. The proof is in [Rob91]. -/
theorem theorem_10 (P : ℕ) :
∃ C : ℕ, ∃ build : List Instr × ℕ × ℕ → CookLevin.Formula,
Nonempty (Turing.TM2ComputableInPolyTime encRobsonIn CookLevin.encodeFormula build) ∧
∀ (n t : ℕ) (prog : List Instr) (f : (Fin n → Bool) → Bool),
prog.length ≤ P → NRAMEvaluates prog t f →
IsEncoding (build (prog, n, t)) (fun i : Fin n => (i : ℕ)) f ∧
((build (prog, n, t)).length : ℝ) ≤ (C : ℝ) * ((t : ℝ) + 1) * Real.logb 2 ((t : ℝ) + 2) ∧
(enc f : ℝ) ≤ (C : ℝ) * ((t : ℝ) + 1) * Real.logb 2 ((t : ℝ) + 2) := by sorry
end CNFEncComplexity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.