Clause bound for mass-production CNF assembly
ProvedCNFEncComplexity.massProduction_clause_boundcomplexity-theorysatisfiability
A linear number of sparse slot encodings with a bounded total support size, together with a checker of polynomial cost per query, has the shifted square-root polylogarithmic clause bound of Lemma 11.
Preamble
import Mathlib.Analysis.Real.Sqrt import Mathlib.Analysis.SpecialFunctions.Log.Base import Mathlib.Algebra.BigOperators.Group.Finset.Basic open scoped BigOperators
Formal statement
theorem CNFEncComplexity.massProduction_clause_bound (A D H e j : ℕ) :
∃ C K : ℕ, ∀ n b q d : ℕ, 1 ≤ b → b ≤ 2 ^ n → q ≤ 16 * b →
(d : ℝ) ≤ (D : ℝ) * ((n : ℝ) + 1) ^ e →
∀ deg clauses : Fin q → ℕ, (∑ r, deg r) ≤ 2 ^ n * d →
(∀ r, (clauses r : ℝ) ≤ (A : ℝ) * ((n : ℝ) + 1 + Real.sqrt ((n : ℝ) * deg r))) →
∀ checker : ℕ, (checker : ℝ) ≤ (H : ℝ) * (b : ℝ) * ((n : ℝ) + 1) ^ j →
((∑ r, clauses r : ℕ) : ℝ) + checker ≤
(C : ℝ) * (Real.sqrt ((2 : ℝ) ^ n * b) + 1) *
Real.logb 2 (Real.sqrt ((2 : ℝ) ^ n * b) + 2) ^ K := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.