Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Correctness and clause bound of the ANRAM formula builder

Proved
CNFEncComplexity.ANRAM.advisorFormula_spec

by bersubs · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-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 sorry
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me