A CNF encoding of a boolean function is a CNF formula over the input variables and extra auxiliary variables such that exactly when some setting of the auxiliaries satisfies the formula. Encodings of this kind are how problems are handed to SAT solvers, and the choice of encoding is often decisive for whether a problem can be solved in practice; for a fixed problem, smaller encodings tend to perform better. The SAT community has accordingly studied encodings of many concrete functions (Hamiltonian cycle, graph colouring, -clique, parity, at-most-), but encodings as a model of computation have had little systematic theoretical treatment.
On the theory side, encodings are the output of every Cook–Levin-type reduction. The Cook–Levin theorem turns steps of a nondeterministic machine into a CNF of size ; later work reduced this to , culminating in Robson's theorem (1991): a nondeterministic RAM running in time yields an encoding with clauses. These optimized reductions give the completeness of CNF-SAT for nondeterministic quasilinear time and time–space tradeoffs for SAT.
Krapivin, Przybocki and Subercaseaux (arXiv:2611.05614, 2026) begin a structural theory of the encoding complexity , the minimum number of clauses of an encoding of . This mission formalizes the paper's main results.
A CNF formula is a list of clauses, each a list of literals over variables indexed by natural numbers. A triple encodes if are distinct input variables, are the remaining (auxiliary) variables, and for every assignment of the inputs, iff some makes satisfy (IsEncoding). Then is the minimum number of clauses of such a (enc).
A nondeterministic RAM (NRAM) is a program of accumulator instructions — loads and stores (direct, immediate and indirect), addition, subtraction, unconditional, conditional and nondeterministic jumps, halting — together with an instruction read that reads the input tape sequentially, one bit at a time, returning an end marker at the end. Under the logarithmic cost criterion a step costs plus the bit length of every number it touches. A program evaluates in time if exactly when some run on input halts with accumulator at total cost at most (AcceptsWithin, NRAMEvaluates). As in Robson's work, the number of instructions is bounded by a fixed constant .
An ANRAM adds an advice string that does not depend on the input. On input it guesses indices into , fetches the bits, and runs an advice-free NRAM on followed by the pairs , each index written in bits (AnramEvaluates). The quantity is the time of that NRAM. Throughout, means .
The paper presents four main results: refTheorem 2, refTheorem 4, refTheorem 5 and refTheorem 6. Prove2Me allows one goal, so Theorem 2 remains the goal; the other three are milestones of equal standing.
If is evaluated in time by an ANRAM with advice bits that queries at most of them per input, then
and such an encoding can be constructed deterministically in time polynomial in , given the advice string. The Lean statement fixes the instruction bound first and then asserts one pair of constants and one polynomial-time construction that, for all , , , programs and , outputs an encoding with input variables and at most clauses, where .
In attack order:
Section 4: Encoding -CNF Functions
Section 5: Arbitrary and Sparsely Supported Functions
The Section 4 and 5 milestones were added on 2026-11-16 so that the mission covers every theorem of the paper.
The result. Theorem 2 gives encodings tight up to polylogarithmic factors for a wide class of functions. For an arbitrary , taking its truth table as advice (, , ) yields , whereas Robson's theorem applied with the whole advice guessed gives only the trivial . The paper derives from it compact encodings of classical NP-complete problems (Theorem 4 uses it for -CNF functions via a derandomized data structure), and a near-converse (Proposition 3) shows it is close to optimal: for every some ANRAM makes the bound at most up to polylogarithmic factors. It also shows that the converse of Tseitin's theorem fails strongly: encoding complexity can be far below nondeterministic circuit size.
Formalizing it. The paper's proofs are short but rest on three external results whose proofs are not in the paper: Robson's 1991 reduction (Theorem 10), Teutsch's explicit expander (Lemma 14) and the AtMostOne bound of [KPS26] (Proposition 12). None of these has a machine-checked proof, and no formal library contains a nondeterministic RAM with logarithmic cost or a notion of CNF encoding complexity. A complete development therefore produces a reusable formal model of RAM-to-SAT reductions, explicit expanders with polynomial-time neighbor functions, and the encoding-complexity layer itself. Theorem 2 has been proved on paper (2026); it has not been formalized.
The obvious argument guesses the whole advice string as auxiliary variables and applies Robson's theorem to the resulting advice-free machine; this costs , a quadratic loss when . Guessing only the queried bits is cheap, but then the formula must check that the guessed pairs agree with the fixed string , and independent lookups into a table of size cost clauses. The central step is Lemma 11: checking lookups jointly at cost . Its proof needs a hash table that is explicit (so that the encoding is constructible in polynomial time), which is why an explicit expander and Hall's theorem enter, and a sparse-function encoding (Lemma 13) for each slot. On the formal side, Robson's theorem is the heaviest single component: it requires simulating an arbitrary log-cost RAM computation, with unbounded register contents and addresses, by a formula whose size is only a logarithmic factor above the running time.
CNF formulas, clauses, literals and satisfaction come from the published CookLevin_Satisfiability layer (formulas are lists of clauses; the clause count is the list length). Boolean functions are (Fin n → Bool) → Bool. The NRAM is a local inductive model with the instruction set listed above, a sequential read-only input with end marker , and cost per step; acceptance is existential. The instruction bound is explicit: each RAM statement is constants and construction, for all programs with at most instructions. is written and as , with constants fixed before the instance; the shifts only matter at . Every construction clause is Mathlib's Turing.TM2ComputableInPolyTime on explicit word encodings, with and in unary so that "polynomial in " keeps its meaning; outputs are formulas under CookLevin.encodeFormula, with input variables .
Trivializations are ruled out: the verification files prove that every function has an encoding (so enc is a true minimum), that the RAM acceptance predicate can be both true and false, that nondeterministic branching works, and that all input encoders are injective. Theorem 2 assumes no relation between and , and allows .
Contributions welcome across every target: the three external milestones, a general RAM simulation library, Lemma 11 and Theorem 2, and the Section 4 and 5 milestones (Hall's theorem is in Mathlib as Finset.all_card_le_biUnion_card_iff_exists_injective).
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
Fix 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 :
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:
No open leaves. Every sub-goal is proved or awaiting decomposition.