Native polynomial-time generation of the ANRAM encoding
ProvedCNFEncComplexity.ANRAM.anramBuilder_nativecomplexity-theorysatisfiability
The ANRAM builder is native polynomial-time when supplied with native polynomial-time generators for both component formulas.
Preamble
import Definitions.Def_CNFEncComplexity_AnramBuilder import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives open CNFEncComplexity.ANRAM CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.ANRAM.anramBuilder_native (left : WordFormulaBuilder) (right : TableFormulaBuilder)
(hLeft : ComputableTidilyInPolyTime left (encList encBits) unaryFormulaEnc)
(hRight : ComputableTidilyInPolyTime right (encPair encUnary (encPair encBits encUnary)) unaryFormulaEnc) :
ComputableTidilyInPolyTime (anramBuilderOnWords left right) (encList encBits) unaryFormulaEnc := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.