CNF encoding of occupied-slot lookup
ProvedCNFEncComplexity.MassProduction.lookupBuild_encodingcomplexity-theorysatisfiability
The circuit-derived CNF encodes the predicate that every query word agrees with an occupied slot.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionLookup import Definitions.Def_CNFEncComplexity_MassProductionLayout import Definitions.Def_CNFEncComplexity_IsEncoding
Formal statement
open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF CNFEncComplexity.MassProduction
theorem CNFEncComplexity.MassProduction.lookupBuild_encoding (b n q : ℕ) :
IsEncoding (lookupBuild (b,n,q)) Fin.val (checkerPredicate b n q) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.