Robson’s native polynomial-time CNF builder on words
ProvedCNFEncComplexity.Robson.robsonBuild_wordscomplexity-theorysatisfiability
For each fixed program length bound there is a native polynomial-time formula generator on serialized words, with the correctness and clause bound of Robson’s theorem.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryGatePrimitives import Definitions.Def_CNFEncComplexity_NRAMEvaluates import Mathlib.Analysis.SpecialFunctions.Log.Base open CNFEncComplexity CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.Robson.robsonBuild_words (P : ℕ) :
∃ C : ℕ, ∃ build : List (List Bool) → CookLevin.Formula,
ComputableTidilyInPolyTime build (encList encBits) unaryFormulaEnc ∧
∀ (n t : ℕ) (prog : List Instr) (f : (Fin n → Bool) → Bool),
prog.length ≤ P → NRAMEvaluates prog t f →
IsEncoding (build (robsonWords (prog, n, t))) Fin.val f ∧
((build (robsonWords (prog, n, t))).length : ℝ) ≤
(C : ℝ) * ((t : ℝ) + 1) * Real.logb 2 ((t : ℝ) + 2) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.