Polynomial-time machine for the rectangular sparse CNF constructor
ProvedCNFEncComplexity.sparseRectangle_polytimecnfsparse-functionsturing-machines
The rectangular sparse CNF constructor has a deterministic multi-tape Turing machine implementation. Its input is the unary width followed by the list of Boolean words in the mission's separator encoding. Its output is the exact Cook–Levin encoding of the constructor's CNF formula. One polynomial in the length of the encoded input bounds the running time for all inputs.
This is the algorithmic component of Lemma 13. The constructor is specified independently, so the statement asks only for the machine and its running-time certification.
Preamble
import Definitions.Def_CNFEncComplexity_encSparseIn import Definitions.Def_CNFEncComplexity_sparseRectangleBuild
Formal statement
namespace CNFEncComplexity
theorem sparseRectangle_polytime :
Nonempty (Turing.TM2ComputableInPolyTime encSparseIn CookLevin.encodeFormula
sparseRectangleBuild) := by sorry
end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614v1, Lemma 13, Section 3.3, construction and last sentence of its proof. https://arxiv.org/html/2611.05614v1#S3.SS3