Correctness and size of the mass-production formula
ProvedCNFEncComplexity.MassProduction.massBuild_speccomplexity-theorysatisfiability
If a neighbor function supplies Hall expansion at every required threshold, its mass-production CNF builder realizes repeated conjunction and obeys the square-root polylogarithmic clause bound.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionData import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_andPow import Mathlib.Data.Finset.Option import Mathlib.Data.Finset.Range import Mathlib.Data.Finset.Union import Mathlib.Analysis.SpecialFunctions.Log.Base open CNFEncComplexity CNFEncComplexity.MassProduction CookLevin
Formal statement
theorem CNFEncComplexity.MassProduction.massBuild_spec (nbr : Neighbor) (c : ℕ)
(hExpand : ∀ k N : ℕ, 2 ^ k ≤ N → ∃ r : ℕ, r < 2 ^ (k + 3) ∧
(∀ l < N, ∀ i ρ : ℕ, nbr (N, k, l, i) = some ρ → ρ < r) ∧
∀ S : Finset (Fin N), S.card ≤ 2 ^ k →
S.card ≤ (S.biUnion fun l => (Finset.range (c * (Nat.log 2 N + 1) ^ c)).biUnion
fun i => (nbr (N, k, l.val, i)).toFinset).card) :
∃ C K : ℕ, ∀ (n : ℕ) (f : (Fin n → Bool) → Bool) (b : ℕ), 1 ≤ b → b ≤ 2 ^ n →
IsEncoding (massBuild nbr c (n, truthTable f, b)) (fun i : Fin (b * n) => (i : ℕ)) (andPow f b) ∧
((massBuild nbr c (n, truthTable f, b)).length : ℝ) ≤
(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.