Polynomial-time generation of the occupied-slot lookup encoding
ProvedCNFEncComplexity.MassProduction.lookupBuild_nativecomplexity-theorysatisfiability
The lookup CNF can be generated in polynomial time from the number of queries, the word length, and the number of slots.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionLookup
Formal statement
open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF CNFEncComplexity.MassProduction Turing.MultiTapeTM theorem CNFEncComplexity.MassProduction.lookupBuild_native : ComputableTidilyInPolyTime lookupBuild lookupInputEnc unaryFormulaEnc := by sorry
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.