Advice table and CNF joining for the ANRAM reduction
DefinitionCNFEncComplexity_AnramConstructioncomplexity-theorysatisfiability
The binary advice lookup table, shared query layout, and disjoint renaming of internal variables used to join the lookup and computation formulas.
Definition code
import Definitions.Def_CNFEncComplexity_MassProductionAssembly
import Mathlib.Data.Nat.Log
namespace CNFEncComplexity.ANRAM
open CookLevin
/-- Width of an advice address followed by the bit stored there. -/
def advicePairWidth (m : ℕ) : ℕ := Nat.clog 2 m + 1
/-- Increase the width if needed to support the full batch of lookups. -/
def adviceWidth (m B : ℕ) : ℕ := max (advicePairWidth m) (Nat.clog 2 B)
/-- At indices `2 * i` and `2 * i + 1`, encode whether the claimed bit (zero or one)
equals `A[i]`. The remaining rows reject. -/
def adviceTable (A : List Bool) (N : ℕ) : List Bool :=
A.flatMap (fun a => [!a, a]) ++ List.replicate (N - 2*A.length) false
/-- Robson inputs retain their original names. Private variables use odd offsets
from the dedicated padding wire at `d`. -/
def adviceRobsonRename (d v : ℕ) : ℕ := if v < d then v else d + 2*v + 1
/-- Each lookup block reads the corresponding advice pair, padded by a shared zero.
Private variables use even nonzero offsets from the padding wire. -/
def adviceCheckRename (n B w W v : ℕ) : ℕ :=
if v < B*W then
if v % W < W-w then n+B*w else n+(v/W)*w+(v%W-(W-w))
else n+B*w+2*v+2
def adviceJoinFormula (n B w W : ℕ) (φ ψ : Formula) : Formula :=
[[.Neg (n+B*w)]] ++
MassProduction.renameFormula (adviceRobsonRename (n+B*w)) φ ++
MassProduction.renameFormula (adviceCheckRename n B w W) ψ
end CNFEncComplexity.ANRAM
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.