The ANRAM formula builder on input words
DefinitionCNFEncComplexity_AnramBuildercomplexity-theorysatisfiability
Construct a CNF from the serial program, time budget, query budget, and advice bits, using supplied formula builders for the RAM and lookup components.
Definition code
import Definitions.Def_CNFEncComplexity_AnramConstruction
import Definitions.Def_CNFEncComplexity_encAnramIn
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Nat_Words
namespace CNFEncComplexity.ANRAM
open CookLevin Turing.MultiTapeTM
abbrev AnramInput := List Instr × ℕ × ℕ × ℕ × List Bool
abbrev WordFormulaBuilder := List (List Bool) → Formula
abbrev TableFormulaBuilder := ℕ × List Bool × ℕ → Formula
def anramWords (p : AnramInput) : List (List Bool) :=
[unaryWord p.2.1, unaryWord p.2.2.1, binWord p.2.2.2.1, p.2.2.2.2] ++ progWords p.1
def replaceInputHeader (n t : ℕ) (code : List (List Bool)) : List (List Bool) :=
[unaryWord n, unaryWord t] ++ code
def advisorFormula (robson : WordFormulaBuilder) (mass : TableFormulaBuilder)
(code : List (List Bool)) (n t b : ℕ) (A : List Bool) : Formula :=
if A.length = 0 ∧ 0 < b then [[]]
else
let B := min b t
if B = 0 then robson (replaceInputHeader n t code)
else
let w := Nat.clog 2 A.length + 1
let W := adviceWidth A.length B
let φ := robson (replaceInputHeader (n+B*w) t code)
let ψ := mass (W, adviceTable A (2^W), B)
adviceJoinFormula n B w W φ ψ
def anramBuilderOnWords (robson : WordFormulaBuilder) (mass : TableFormulaBuilder)
(ws : List (List Bool)) : Formula :=
advisorFormula robson mass (ws.drop 4) (ws[0]?.getD []).length
(ws[1]?.getD []).length (ofBits (ws[2]?.getD [])) (ws[3]?.getD [])
end CNFEncComplexity.ANRAM
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.