Guarded assembly of mass-production CNFs
DefinitionCNFEncComplexity_MassProductionAssemblycomplexity-theorysatisfiability
Conjoin a query checker with a sparse CNF for each slot, guarded by occupancy. Shared input variables retain their prescribed locations. The checker and slot encodings have separate sets of auxiliary variables.
Definition code
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CNFEncComplexity_MassProductionLayout
import Mathlib.Data.Finset.Defs
namespace CNFEncComplexity.MassProduction
open CookLevin
def slotPredicate {n q : ℕ} (f : (Fin n → Bool) → Bool) (neighbors : (Fin n → Bool) → Finset (Fin q))
(r : Fin q) (w : (Fin n → Bool)) : Bool :=
f w && decide (r ∈ neighbors w)
def renameLiteral (ren : ℕ → ℕ) : Literal → Literal
| .Neg v => .Neg (ren v)
| .Pos v => .Pos (ren v)
def renameFormula (ren : ℕ → ℕ) (φ : Formula) : Formula :=
φ.map (List.map (renameLiteral ren))
def guardFormula (live : ℕ) (φ : Formula) : Formula :=
φ.map (fun c => .Neg live :: c)
def checkerRename (shared q v : ℕ) : ℕ :=
if v < shared then v else shared + (q + 1) * v
def slotRename (b n q : ℕ) (r : Fin q) (v : ℕ) : ℕ :=
if v < n then b * n + r.val * (n + 1) + v
else b * n + q * (n + 1) + (q + 1) * v + r.val + 1
def assembleFormula (b n q : ℕ) (checker : Formula) (slots : Fin q → Formula) : Formula :=
renameFormula (checkerRename (b * n + q * (n + 1)) q) checker ++
(List.finRange q).flatMap (fun r =>
guardFormula (liveIndex b n r).val (renameFormula (slotRename b n q r) (slots r)))
end CNFEncComplexity.MassProduction
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.