Advice lookup as a Boolean function
DefinitionCNFEncComplexity_AnramLookupPredicatecomplexity-theorysatisfiability
The padded advice lookup predicate holds when an encoded address is valid and its claimed bit is the stored advice value.
Definition code
import Definitions.Def_CNFEncComplexity_AnramConstruction
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Data.Nat.Bitwise
namespace CNFEncComplexity.ANRAM
def adviceAddressWord (n v : ℕ) : Fin n → Bool :=
fun i => v.testBit (n - 1 - i.val)
private theorem adviceAddressWord_injective (n : ℕ) :
Function.Injective (fun v : Fin (2 ^ n) => adviceAddressWord n v.val) := by
intro a b hab
apply Fin.ext
apply Nat.eq_of_testBit_eq
intro i
by_cases hi : i < n
· let j : Fin n := ⟨n-1-i, by omega⟩
have h : a.val.testBit (n-1-j.val) = b.val.testBit (n-1-j.val) := congrFun hab j
rw [show n - 1 - j.val = i by dsimp [j]; omega] at h
exact h
· have ha : a.val < 2 ^ i :=
a.isLt.trans_le (Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi))
have hb : b.val < 2 ^ i :=
b.isLt.trans_le (Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi))
rw [Nat.testBit_lt_two_pow ha, Nat.testBit_lt_two_pow hb]
noncomputable def adviceAddressEquiv (n : ℕ) : Fin (2 ^ n) ≃ (Fin n → Bool) :=
Equiv.ofBijective (fun v => adviceAddressWord n v.val) <| by
apply (Fintype.bijective_iff_injective_and_card _).2
refine ⟨adviceAddressWord_injective n, ?_⟩
simp
noncomputable def adviceLookup (A : List Bool) (W : ℕ) (x : Fin W → Bool) : Bool :=
(adviceTable A (2^W))[((adviceAddressEquiv W).symm x).val]?.getD false
end CNFEncComplexity.ANRAM
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.