Lemma 11 (mass production) —
ProvedCNFEncComplexity.lemma_11cnf-encodingscomputational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1sat
There are constants and a deterministic polynomial-time construction such that for every , every and every (that is, ), writing :
- the construction, given , the truth table of and , outputs a CNF encoding of with input variables ;
- this encoding has at most clauses;
- consequently
Querying a boolean function times costs substantially fewer clauses than independent encodings, which need up to . The proof of Theorem 2 applies the lemma to the advice-lookup function .
Formalization Note Time is measured in Mathlib's Turing.TM2ComputableInPolyTime on the input encMassIn ( in unary, the -bit truth table with the most significant bit, in unary), output CookLevin.encodeFormula; polynomial in that length is polynomial in and .
Differences from the source:
- 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: obtained deterministically in time polynomial in 2ⁿ and b → TM2ComputableInPolyTime encMassIn CookLevin.encodeFormula build, input n and b in unary and the truth table of f; 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_andPow import Definitions.Def_CNFEncComplexity_encWords import Definitions.Def_CNFEncComplexity_encMassIn
Formal statement
namespace CNFEncComplexity
/-- **Lemma 11 (mass production).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 11, p.11 (PDF 12): "Let f : {0, 1}ⁿ → {0, 1}, and let
b ∈ [2ⁿ]. Let f^∧b : {0, 1}^{bn} → {0, 1} be such that for every x⃗₁, . . . , x⃗_b ∈ {0, 1}ⁿ we have
f^∧b(x⃗₁, . . . , x⃗_b) = ⋀_{i∈[b]} f(x⃗ᵢ). Then, enc(f^∧b) = Õ(√(2ⁿb)). Furthermore, such an encoding
can be obtained deterministically in time polynomial in 2ⁿ and b."
There are constants `C, K` and a polynomial-time function `build` such that for every `n`, every
`f : {0,1}ⁿ → {0,1}` and every `1 ≤ b ≤ 2ⁿ`, with `g = √(2ⁿ b)`:
1. `build (n, truthTable f, b)` is a CNF encoding of `f^∧b` with input variables `0, …, bn − 1`;
2. it has at most `C·(g + 1)·log₂(g + 2)^K` clauses;
3. hence `enc(f^∧b) ≤ C·(g + 1)·log₂(g + 2)^K`.
**Formalization Note.** `b ∈ [2ⁿ]` is `1 ≤ b ≤ 2ⁿ`. Õ(g) = O(g·polylog g) (footnote 2, p.2) is
`C·(g + 1)·log₂(g + 2)^K` with `C, K` fixed before `n, f, b`. The construction receives `n` in
unary, the truth table of `f` (entry `v` = `f` at the binary expansion of `v`, `x₁` most
significant; `truthTable`) and `b` in unary (`encMassIn`); polynomial time is Mathlib's
`Turing.TM2ComputableInPolyTime`, output `CookLevin.encodeFormula`. Block `i` of the input of
`f^∧b` is the variables `i·n, …, i·n + n − 1` (`andPow`). -/
theorem lemma_11 :
∃ C K : ℕ, ∃ build : ℕ × List Bool × ℕ → CookLevin.Formula,
Nonempty (Turing.TM2ComputableInPolyTime encMassIn CookLevin.encodeFormula build) ∧
∀ (n : ℕ) (f : (Fin n → Bool) → Bool) (b : ℕ), 1 ≤ b → b ≤ 2 ^ n →
IsEncoding (build (n, truthTable f, b)) (fun i : Fin (b * n) => (i : ℕ)) (andPow f b) ∧
((build (n, truthTable f, b)).length : ℝ) ≤
(C : ℝ) * (Real.sqrt (2 ^ n * (b : ℝ)) + 1) *
Real.logb 2 (Real.sqrt (2 ^ n * (b : ℝ)) + 2) ^ K ∧
(enc (andPow f b) : ℝ) ≤
(C : ℝ) * (Real.sqrt (2 ^ n * (b : ℝ)) + 1) *
Real.logb 2 (Real.sqrt (2 ^ n * (b : ℝ)) + 2) ^ K := by sorry
end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 11, p.11 (PDF 12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.