Correctness and clause bound of the ANRAM formula builder
ProvedCNFEncComplexity.ANRAM.advisorFormula_speccomplexity-theorysatisfiability
The joined builder encodes the original ANRAM acceptance predicate and has the shifted-logarithm clause bound in Theorem 2, assuming the input generators satisfy their established specifications.
Preamble
import Definitions.Def_CNFEncComplexity_AnramBuilder import Definitions.Def_CNFEncComplexity_AnramEvaluates import Definitions.Def_CNFEncComplexity_NRAMEvaluates import Definitions.Def_CNFEncComplexity_RobsonConstraints import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_andPow import Definitions.Def_CNFEncComplexity_encMassIn import Mathlib.Analysis.Real.Sqrt import Mathlib.Analysis.SpecialFunctions.Log.Base open CookLevin CNFEncComplexity CNFEncComplexity.ANRAM CNFEncComplexity.RobsonCNF
Formal statement
theorem CNFEncComplexity.ANRAM.advisorFormula_spec (P C_R C_M K : ℕ)
(left : WordFormulaBuilder) (right : TableFormulaBuilder)
(hLeft : ∀ (n t : ℕ) (prog : List Instr) (run : (Fin n → Bool) → Bool),
prog.length ≤ P → NRAMEvaluates prog t run →
IsEncoding (left (robsonWords (prog,n,t))) Fin.val run ∧
((left (robsonWords (prog,n,t))).length : ℝ) ≤
(C_R : ℝ) * ((t : ℝ)+1) * Real.logb 2 ((t : ℝ)+2))
(hRight : ∀ (W : ℕ) (check : (Fin W → Bool) → Bool) (B : ℕ), 1 ≤ B → B ≤ 2^W →
IsEncoding (right (W,truthTable check,B)) Fin.val (andPow check B) ∧
((right (W,truthTable check,B)).length : ℝ) ≤
(C_M : ℝ) * (Real.sqrt (2^W * (B : ℝ)) + 1) *
Real.logb 2 (Real.sqrt (2^W * (B : ℝ)) + 2) ^ K)
{n : ℕ} (t b : ℕ) (prog : List Instr) (A : List Bool) (f : (Fin n → Bool) → Bool)
(hp : prog.length ≤ P) (hEval : AnramEvaluates prog A b t f) :
let formula := advisorFormula left right (progWords prog) n t b A
let G := (t : ℝ) + Real.sqrt ((A.length : ℝ)*b)
IsEncoding formula Fin.val f ∧
(formula.length : ℝ) ≤ ((C_R + 2*C_M*2^K + 1 : ℕ) : ℝ) *
(G+1) * Real.logb 2 (G+2)^max 1 K := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.