Proposition 12 —
ProvedCNFEncComplexity.proposition_12cnf-encodingscomputational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1sat
There are constants such that for every ,
The leading terms are exact; only the lower-order term is asymptotic. This is the best known upper bound on the encoding complexity of AtMostOne, quoted from [KPS26]; the sparse-function encoding of Lemma 13 uses an AtMostOne encoding with clauses.
Formalization Note is written with fixed before ; . The proof is in [KPS26], not in this paper.
Differences from the source:
- encoding: Õ(∜n) (footnote 2, p.2) → C·(n^{1/4}+1)·log₂(n+2)^K with C, K fixed before n; reason: Lean convention for the lower-order term; the shifts only matter at n ≤ 1
Preamble
import Mathlib import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_enc import Definitions.Def_CNFEncComplexity_atMostOne
Formal statement
namespace CNFEncComplexity
/-- **Proposition 12 ([KPS26]).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Proposition 12, p.12 (PDF 13): "We have
enc(AtMostOne(x₁, . . . , xₙ)) ⩽ 2n + 2√(2n) + Õ(∜n)."
There are constants `C, K` such that for every `n`,
`enc(AtMostOne(x₁,…,xₙ)) ≤ 2n + 2√(2n) + C·(n^{1/4} + 1)·log₂(n + 2)^K`.
**Formalization Note.** Õ(g) = O(g·polylog g) (footnote 2, p.2) with `g = n^{1/4}` is written
`C·(g + 1)·log₂(n + 2)^K` with `C, K` fixed before `n`; `log(n^{1/4}) = log(n)/4`, and the `+1`,
`+2` shifts only matter for `n ≤ 1`. The leading terms `2n + 2√(2n)` are exact. The proof is in
[KPS26], not in this paper. -/
theorem proposition_12 :
∃ C K : ℕ, ∀ n : ℕ,
(enc (atMostOne n) : ℝ) ≤
2 * (n : ℝ) + 2 * Real.sqrt (2 * (n : ℝ)) +
(C : ℝ) * ((n : ℝ) ^ (1 / 4 : ℝ) + 1) * Real.logb 2 ((n : ℝ) + 2) ^ K := by sorry
end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614 (held version, sha256 97421ce1…), Proposition 12, p.12 (PDF 13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.