Native polynomial-time construction of sparse rectangle CNFs
ProvedCNFEncComplexity.sparseRectangleBuild_tidycomplexity-theorysatisfiability
The sparse rectangle builder is polynomial-time on unary word length and framed bit vectors, with unary CNF literal codes.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives import Definitions.Def_CNFEncComplexity_sparseRectangleBuild open CNFEncComplexity Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.sparseRectangleBuild_tidy :
ComputableTidilyInPolyTime sparseRectangleBuild (encPair encUnary (encList encBits)) RobsonCNF.unaryFormulaEnc := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.