Uniform polynomial-time construction of the mass-production formula
ProvedCNFEncComplexity.MassProduction.massBuild_TM2complexity-theorysatisfiability
Given a native polynomial-time neighbor function, the concrete mass-production CNF builder has a polynomial-time TM2 certificate on the truth-table input encoding of Lemma 11.
Preamble
import Definitions.Def_CNFEncComplexity_MassProductionData import Mathlib.Computability.TuringMachine.Computable open CNFEncComplexity CNFEncComplexity.MassProduction CookLevin Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.MassProduction.massBuild_TM2 (nbr : Neighbor) (c : ℕ)
(hNbr : ComputableTidilyInPolyTime nbr neighborNative (encOption encNat)) :
Nonempty (Turing.TM2ComputableInPolyTime encMassIn encodeFormula (massBuild nbr c)) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.