Correctness of guarded mass-production CNF assembly
ProvedCNFEncComplexity.MassProduction.assemble_isEncodingcomplexity-theorysatisfiability
Guarded sparse encodings and an occupied-slot checker encode the conjunction of all queries. Hall expansion up to the number of queries guarantees that every set of accepted inputs can be placed into the slots.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionAssembly import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_andPow import Mathlib.Data.Finset.Union open CNFEncComplexity CNFEncComplexity.MassProduction CookLevin
Formal statement
theorem CNFEncComplexity.MassProduction.assemble_isEncoding {b n q : ℕ} (f : (Fin n → Bool) → Bool)
(neighbors : (Fin n → Bool) → Finset (Fin q)) (checker : Formula) (slots : Fin q → Formula)
(hall : ∀ S : Finset ((Fin n → Bool)), S.card ≤ b → S.card ≤ (S.biUnion neighbors).card)
(hChecker : IsEncoding checker Fin.val (checkerPredicate b n q))
(hSlots : ∀ r, IsEncoding (slots r) Fin.val (slotPredicate f neighbors r)) :
IsEncoding (assembleFormula b n q checker slots) Fin.val (andPow f b) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.