Input and formula builder for mass production
DefinitionCNFEncComplexity_MassProductionDatacomplexity-theorysatisfiability
Enumerate the words accepted by each slot from the truth table and expander. Combine the resulting sparse encodings with the common lookup checker.
Definition code
import Definitions.Def_CNFEncComplexity_encMassIn
import Mathlib.Data.Nat.Log
import Mathlib.Data.Fintype.Pi
import Definitions.Def_CNFEncComplexity_MassProductionAssembly
import Definitions.Def_CNFEncComplexity_MassProductionLookup
import Definitions.Def_CNFEncComplexity_sparseRectangleBuild
namespace CNFEncComplexity.MassProduction
open CookLevin Turing.MultiTapeTM
def addressWord (n v : ℕ) : Fin n → Bool :=
fun i => v.testBit (n - 1 - i.val)
def addressBits (n v : ℕ) : List Bool :=
List.ofFn (addressWord n v)
abbrev Neighbor := ℕ × ℕ × ℕ × ℕ → Option ℕ
def degree (c n : ℕ) : ℕ := c*(n+1)^c
def slotCount (b : ℕ) : ℕ := 16*b
def slotHit (nbr : Neighbor) (c N n b l r : ℕ) : Bool :=
(List.range (degree c n)).any fun i => nbr (N, Nat.clog 2 b, l, i) == some r
def acceptedAddresses (nbr : Neighbor) (c n : ℕ) (T : List Bool) (b r : ℕ) : List ℕ :=
(List.range T.length).filter fun l => T[l]?.getD false && slotHit nbr c T.length n b l r
def slotSupport (nbr : Neighbor) (c n : ℕ) (T : List Bool) (b r : ℕ) : List (List Bool) :=
(acceptedAddresses nbr c n T b r).map (addressBits n)
abbrev MassInput := ℕ × List Bool × ℕ
abbrev massInputNative : MassInput ↪ List Bool :=
encPair encUnary (encPair encBits encUnary)
abbrev neighborNative : (ℕ × ℕ × ℕ × ℕ) ↪ List Bool :=
encPair encNat (encPair encNat (encPair encNat encNat))
def sparseSlot (n : ℕ) (L : List (List Bool)) : Formula :=
if L.isEmpty then [[]] else sparseRectangleBuild (n,L)
def massBuild (nbr : Neighbor) (c : ℕ) (p : ℕ × List Bool × ℕ) : Formula :=
let (n,T,b) := p
let q := slotCount b
assembleFormula b n q (lookupBuild (b,n,q))
(fun r => sparseSlot n (slotSupport nbr c n T b r.val))
end CNFEncComplexity.MassProduction
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.