Lemma 13 — sparse functions have encodings with clauses
ProvedCNFEncComplexity.lemma_13cnf-encodingscomputational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1sat
There are a constant and a deterministic polynomial-time construction such that:
- for every and every nonempty list of distinct vectors in , the construction, given and , outputs a CNF encoding of the indicator function of (the function with ), with input variables and at most clauses;
- for every with ,
The lemma encodes functions with few satisfying inputs; in the proof of Lemma 11 it encodes each slot function of the hash table.
Formalization Note "Given the list of elements of ": a duplicate-free list of length- vectors is exactly a listing of for its indicator function, and then . Polynomial time is Mathlib's Turing.TM2ComputableInPolyTime on the input encSparseIn ( in unary, then the vectors), with output CookLevin.encodeFormula.
Differences from the source:
- encoding: enc(f) = O(n + √(nM)) → ∃ C, enc f ≤ C·(n + √(nM)) for all n and f with M ≥ 1; reason: definition of O(·) with one constant for all f
- reading: constructed deterministically in time polynomial in nM, given the list of elements of f⁻¹(1) → TM2ComputableInPolyTime encSparseIn CookLevin.encodeFormula build, on duplicate-free nonempty lists of length-n vectors; 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
Preamble
import Mathlib import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_enc import Definitions.Def_CNFEncComplexity_encWords import Definitions.Def_CNFEncComplexity_encSparseIn
Formal statement
namespace CNFEncComplexity
/-- **Lemma 13 (sparse functions).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 13, pp.12–13 (PDF 13–14): "Let f : {0, 1}ⁿ → {0, 1},
and let M := |f⁻¹(1)| ⩾ 1. Then, enc(f) = O(n + √(nM)). Given the list of elements of f⁻¹(1), an
encoding attaining this bound can be constructed deterministically in time polynomial in nM."
There are a constant `C` and a function `build`, computable in polynomial time, such that:
1. for every `n` and every nonempty duplicate-free list `L` of vectors of length `n`, `build (n, L)`
is a CNF encoding, with input variables `0, …, n − 1`, of the indicator function of `L`, with at
most `C·(n + √(n·|L|))` clauses;
2. for every `f : {0,1}ⁿ → {0,1}` with `M = |f⁻¹(1)| ≥ 1`, `enc(f) ≤ C·(n + √(nM))`.
**Formalization Note.** "Given the list of elements of f⁻¹(1)": the input is `n` in unary and the
list (`encSparseIn`); a duplicate-free list `L` of length-`n` vectors is exactly a listing of
`f⁻¹(1)` for `f` its indicator, and then `|L| = M`. Polynomial time is Mathlib's
`Turing.TM2ComputableInPolyTime` with output `CookLevin.encodeFormula`. The bound `O(n + √(nM))`
needs no shift: it is `0` only for `n = 0`, where `f ≡ 1` and the empty CNF encodes it. -/
theorem lemma_13 :
∃ C : ℕ, ∃ build : ℕ × List (List Bool) → CookLevin.Formula,
Nonempty (Turing.TM2ComputableInPolyTime encSparseIn CookLevin.encodeFormula build) ∧
(∀ (n : ℕ) (L : List (List Bool)), L ≠ [] → L.Nodup → (∀ v ∈ L, v.length = n) →
IsEncoding (build (n, L)) (fun i : Fin n => (i : ℕ)) (fun x => decide (List.ofFn x ∈ L)) ∧
((build (n, L)).length : ℝ) ≤ (C : ℝ) * ((n : ℝ) + Real.sqrt ((n : ℝ) * L.length))) ∧
∀ (n : ℕ) (f : (Fin n → Bool) → Bool),
1 ≤ (Finset.univ.filter fun x => f x = true).card →
(enc f : ℝ) ≤ (C : ℝ) * ((n : ℝ) +
Real.sqrt ((n : ℝ) * ((Finset.univ.filter fun x => f x = true).card : ℝ))) := by sorry
end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 13, pp.12–13 (PDF 13–14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.