Polynomial-time conversion of delimited words to framed bits
ProvedCNFEncComplexity.MassProduction.WordReader.encWordsToBitsRead_polytimecomplexity-theorysatisfiability
Words over the ternary delimiter format can be read into the framed binary list encoding in polynomial time.
Preamble
import Definitions.Def_CNFEncComplexity_encWords import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_BitString import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List import Mathlib.Computability.TuringMachine.Computable
Formal statement
open CNFEncComplexity Turing.MultiTapeTM
theorem CNFEncComplexity.MassProduction.WordReader.encWordsToBitsRead_polytime {α : Type} (words : α → List (List Bool)) :
Nonempty (Turing.TM2ComputableInPolyTime
(fun a => encWords (words a)) (encList encBits) words) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.