At-most-two CNF encodings with clauses
ProvedCNFEncComplexity.atMostTwo_encoding_boundcardinality-constraintscnfsat
For each nonnegative integer , let be the Boolean function that accepts precisely the assignments on input bits with at most two true entries. There exist nonnegative integer constants and such that for every , there is a CNF encoding of with the input variables indexed by and with
This is the clause-count consequence of disjunctive grid compression for threshold two. It gives the vertex-indicator encoding used in the clique construction for at-most-one.
Formalization Note The shifts make the bound uniform for small . The statement counts clauses and imposes no bound on the number of auxiliary variables.
Preamble
import Mathlib import Definitions.Def_CNFEncComplexity_IsEncoding
Formal statement
namespace CNFEncComplexity
theorem atMostTwo_encoding_bound :
∃ C K : ℕ, ∀ p : ℕ, ∃ φ : CookLevin.Formula,
IsEncoding φ (fun i : Fin p => (i : ℕ))
(fun x : Fin p → Bool => decide ((Finset.univ.filter fun i => x i = true).card ≤ 2)) ∧
(φ.length : ℝ) ≤
2 * (p : ℝ) + (C : ℝ) * (Real.sqrt (p : ℝ) + 1) *
Real.logb 2 ((p : ℝ) + 2) ^ K := by sorry
end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, Near-Optimal Encodings of Cardinality Constraints, arXiv:2603.28954v2, Theorem 4 (specialized to k=2), Section 5.3 and Appendix D.2. https://arxiv.org/html/2603.28954v2