Clause count of the occupied-slot lookup encoding
ProvedCNFEncComplexity.MassProduction.lookupBuild_budgetcomplexity-theorysatisfiability
The lookup CNF has a clause count linear in the number of rows times a squared bound on row width and binary index length.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionLookup
Formal statement
open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF CNFEncComplexity.MassProduction
theorem CNFEncComplexity.MassProduction.lookupBuild_budget (b n q : ℕ) :
(lookupBuild (b,n,q)).length ≤ 6000*(q+b+1)*(n+(q+b).size+1)^2 := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.