Truth table of the padded advice lookup predicate
ProvedCNFEncComplexity.ANRAM.adviceLookup_truthTablecomplexity-theorysatisfiability
Writing false rows after the valid advice values gives exactly the truth table that is consumed by the mass-production builder.
Preamble
import Definitions.Def_CNFEncComplexity_AnramLookupPredicate import Definitions.Def_CNFEncComplexity_encMassIn open CookLevin CNFEncComplexity CNFEncComplexity.ANRAM
Formal statement
theorem CNFEncComplexity.ANRAM.adviceLookup_truthTable (A : List Bool) (W : ℕ) (hw : advicePairWidth A.length ≤ W) :
truthTable (adviceLookup A W) = adviceTable A (2^W) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.