Native polynomial-time builder for mass-production CNFs
ProvedCNFEncComplexity.MassProduction.massBuild_nativecomplexity-theorysatisfiability
Given a native polynomial-time neighbor function, the mass-production builder has a native polynomial-time certificate on a word length, truth table, and query count.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionData open CNFEncComplexity.MassProduction CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.MassProduction.massBuild_native (nbr : Neighbor) (c : ℕ)
(hNbr : ComputableTidilyInPolyTime nbr neighborNative (encOption encNat)) :
ComputableTidilyInPolyTime (massBuild nbr c) massInputNative unaryFormulaEnc := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.