Theorem 2 — ANRAM time with advice bits and queries gives
ProvedCNFEncComplexity.theorem_2Fix a bound on the number of instructions. There are constants and a deterministic polynomial-time construction such that the following holds for every , every , every advice string (), every advice-free program with at most instructions and every that the ANRAM with advice queries evaluates in time . Writing :
- the construction, given , , , and the advice string , outputs a CNF encoding of with input variables ;
- this encoding has at most clauses;
- consequently
This is the paper's main result. Robson's theorem with the whole advice string guessed gives only ; for an arbitrary function, taking the truth table as advice (, , ) gives instead of the trivial .
Formalization Note Constants and construction depend only on the instruction bound (the paper's fixed-constant convention, p.10). The construction's input encAnramIn has and in unary, in binary, the advice bits and the program; "time polynomial in given the advice string" is time polynomial in that input length, in Mathlib's Turing.TM2ComputableInPolyTime, output CookLevin.encodeFormula. No relation between and is assumed (the proof's "assume " is a reduction, not a hypothesis), and is allowed.
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: ANRAM: guess i₁, …, i_b, pass x⃗ with ((i₁, A[i₁]), …, (i_b, A[i_b])) to a nondeterministic RAM (§3.1, p.11); time t → AnramEvaluates: exactly b guessed indices (repetitions allowed), each written as ⌈lg m⌉ bits most significant first followed by its advice bit, appended to the input tape; t bounds the cost of the advice-free program; reason: the paper's model made concrete; the query encoding matches the proof's input length n + b(lg m + 1), and repeated indices cover "at most b"
- 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: Õ(g) = O(g·polylog g) (footnote 2, p.2) → C·(g+1)·log₂(g+2)^K with C, K fixed before the instance; reason: Lean convention for the asymptotic statement; the shifts only matter at g = 0, where the paper's bound O(0) cannot hold for the constant-0 function with enc = 1
- reading: constructed deterministically in time polynomial in n + t + m given the advice string → TM2ComputableInPolyTime encAnramIn CookLevin.encodeFormula build, with n and t in unary, b in binary, the advice bits and the program; 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_AnramEvaluates import Definitions.Def_CNFEncComplexity_encWords import Definitions.Def_CNFEncComplexity_encAnramIn
namespace CNFEncComplexity
/-- **Theorem 2 (main result).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Theorem 2, p.2 (PDF 3); restated p.10 (PDF 11), proof p.12
(PDF 13): "Let f : {0, 1}ⁿ → {0, 1}, and suppose that f can be evaluated in time t ⩾ n with m bits of
advice by an ANRAM machine that accesses at most b bits of the advice for each input. Then,
enc(f) = Õ(t + √(mb)). Furthermore, such an encoding can be constructed deterministically in time
polynomial in n + t + m given the advice string."
For every bound `P` on the number of instructions there are constants `C, K` and a polynomial-time
function `build` such that for every `n ≤ t`, every `b`, every advice string `A` (of length `m`),
every program `prog` with at most `P` instructions and every `f : {0,1}ⁿ → {0,1}` that the ANRAM
`(prog, A, b)` evaluates in time `t` (`AnramEvaluates`), with `g = t + √(mb)`:
1. `build (prog, n, t, b, A)` is a CNF encoding of `f` with input variables `0, …, n − 1`;
2. it has at most `C·(g + 1)·log₂(g + 2)^K` clauses;
3. hence `enc(f) ≤ C·(g + 1)·log₂(g + 2)^K`.
**Formalization Note.** The number of instructions is bounded by a fixed constant (p.10, following
Robson), so `C, K` and the construction depend on `P` only. Õ(g) = O(g·polylog g) (footnote 2, p.2)
is `C·(g + 1)·log₂(g + 2)^K`; the shifts matter only at `g = 0` (`n = t = 0`), where `f` may be
constant `0` with `enc(f) = 1`. The construction receives the program, `n` and `t` in unary, `b`
in binary and the advice bits (`encAnramIn`); "time polynomial in n + t + m" is read as polynomial in
this input length, in Mathlib's `Turing.TM2ComputableInPolyTime` with output
`CookLevin.encodeFormula`. No relation between `b` and `m` is assumed (the proof's "assume
1 ⩽ b ⩽ m" is a reduction, not a hypothesis), and `m = 0` is allowed. -/
theorem theorem_2 (P : ℕ) :
∃ C K : ℕ, ∃ build : List Instr × ℕ × ℕ × ℕ × List Bool → CookLevin.Formula,
Nonempty (Turing.TM2ComputableInPolyTime encAnramIn CookLevin.encodeFormula build) ∧
∀ (n t b : ℕ) (prog : List Instr) (A : List Bool) (f : (Fin n → Bool) → Bool),
prog.length ≤ P → n ≤ t → AnramEvaluates prog A b t f →
IsEncoding (build (prog, n, t, b, A)) (fun i : Fin n => (i : ℕ)) f ∧
((build (prog, n, t, b, A)).length : ℝ) ≤
(C : ℝ) * ((t : ℝ) + Real.sqrt ((A.length : ℝ) * b) + 1) *
Real.logb 2 ((t : ℝ) + Real.sqrt ((A.length : ℝ) * b) + 2) ^ K ∧
(enc f : ℝ) ≤
(C : ℝ) * ((t : ℝ) + Real.sqrt ((A.length : ℝ) * b) + 1) *
Real.logb 2 ((t : ℝ) + Real.sqrt ((A.length : ℝ) * b) + 2) ^ K := by sorry
end CNFEncComplexity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.