Correctness of joining the computation and advice lookup formulas
ProvedCNFEncComplexity.ANRAM.adviceReductionEncodingcomplexity-theorysatisfiability
The computation CNF and padded advice-query CNF combine into a CNF for the ANRAM acceptance predicate.
Preamble
import Definitions.Def_CNFEncComplexity_AnramLookupPredicate import Definitions.Def_CNFEncComplexity_IsEncoding import Definitions.Def_CNFEncComplexity_andPow import Definitions.Def_CNFEncComplexity_AnramEvaluates import Definitions.Def_CNFEncComplexity_NRAMEvaluates import Mathlib.Data.List.OfFn open CookLevin CNFEncComplexity CNFEncComplexity.ANRAM
Formal statement
theorem CNFEncComplexity.ANRAM.adviceReductionEncoding {n B W : ℕ} (A : List Bool) (hw : advicePairWidth A.length ≤ W)
(prog : List Instr) (t : ℕ) (run : (Fin (n+B*advicePairWidth A.length) → Bool) → Bool)
(f : (Fin n → Bool) → Bool) (φ ψ : CookLevin.Formula)
(hRun : NRAMEvaluates prog t run) (hAN : AnramEvaluates prog A B t f)
(hφ : IsEncoding φ Fin.val run) (hψ : IsEncoding ψ Fin.val (andPow (adviceLookup A W) B)) :
IsEncoding (adviceJoinFormula n B (advicePairWidth A.length) W φ ψ) Fin.val f := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.