TM2 construction of CNFs from delimited input words
ProvedCNFEncComplexity.RobsonCNF.formulaBuilderTM2complexity-theorysatisfiability
A polynomial-time CNF generator on framed bit words gives a Mathlib TM2 builder on delimited words with the standard Cook–Levin formula output.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives
Formal statement
open CNFEncComplexity CNFEncComplexity.RobsonCNF CookLevin Turing.MultiTapeTM
theorem CNFEncComplexity.RobsonCNF.formulaBuilderTM2 {α : Type} (words : α → List (List Bool))
(generator : List (List Bool) → Formula)
(hgen : ComputableInPolyTime generator (encList encBits) unaryFormulaEnc) :
Nonempty (Turing.TM2ComputableInPolyTime
(fun a => encWords (words a)) encodeFormula (generator ∘ words)) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.