Correctness and size of the sparse rectangle CNF generator
ProvedCNFEncComplexity.sparseRectangleBuild_speccomplexity-theorysatisfiability
The concrete rectangle builder encodes membership in any nonempty duplicate-free list of words of the given length, with the clause bound used by Lemma 13.
Preamble
import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_sparseRectangleBuild import Mathlib.Analysis.Real.Sqrt open CNFEncComplexity CookLevin
Formal statement
theorem CNFEncComplexity.sparseRectangleBuild_spec (n : ℕ) (L : List (List Bool))
(hL : L ≠ []) (_ : L.Nodup) (hwidth : ∀ v ∈ L, v.length = n) :
IsEncoding (sparseRectangleBuild (n, L)) (fun i : Fin n => (i : ℕ))
(fun x => decide (List.ofFn x ∈ L)) ∧
((sparseRectangleBuild (n, L)).length : ℝ) ≤
(11 : ℝ) * ((n : ℝ) + Real.sqrt ((n : ℝ) * L.length)) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.