Capping ANRAM advice queries by the time bound
ProvedCNFEncComplexity.ANRAM.anramEvaluates_capcomplexity-theorysatisfiability
With nonempty advice, capping the number of prefetched advice pairs at the time bound preserves the function evaluated by the ANRAM.
Preamble
import Definitions.Def_CNFEncComplexity_AnramEvaluates open CNFEncComplexity
Formal statement
theorem CNFEncComplexity.ANRAM.anramEvaluates_cap {n : ℕ} (prog : List Instr) (A : List Bool) (b t : ℕ)
(f : (Fin n → Bool) → Bool) (hA : 0 < A.length) :
AnramEvaluates prog A b t f ↔ AnramEvaluates prog A (min b t) t f := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 2, Section 3.2.