Presentation transfer with advice is equivalent to total-search advice selectors
ProvedStudentTeacher976.Adaptivity.presentation_transfer_with_advice_iff_total_search_selectorsFix a hierarchy level and admissible round and query functions . A faithful refutation presentation specifies an underlying total search relation by a bounded universally quantified predicate. A uniform student uses one polynomial-time -oracle program. An advised student additionally has one polynomially bounded advice string for each length of its encoded input, shared by all inputs of that length; the advice need not be computable.
The following two conditions are equivalent:
- For every total search relation and every two faithful presentations of , existence of a uniform winning student for within implies existence of an advised winning student for within the same budget.
- Every total, polynomially bounded search relation with a verifier has an selector.
Writing and for the two kinds of solvability, the equivalence is
The criterion concerns unrestricted transfer across all presentations at one fixed admissible budget. It identifies the precise total-search assumption for such transfer even when the new student is allowed polynomial advice. It does not assert that the selector condition holds, or that this unrestricted transfer is necessary for any particular pair of presentations.
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity open AdviceComputations (InFPAdvice)
theorem StudentTeacher976.Adaptivity.presentation_transfer_with_advice_iff_total_search_selectors (i : ℕ) (r q : ℕ → ℕ)
(hr : AdmissibleRounds r) (hq : AdmissibleQueries q) :
(∀ (R : SearchRelation) (P Q : RefutablePresentation i R),
(∃ g : Student,UniformStudent i g ∧ StudentShape Q r q g ∧ StudentWins Q r q g) →
∃ f : Student,
(∃ F : Word → Word,InFPAdvice i F ∧ ∀ (x : Word) (t : ℕ) (H : List (List Word)),
F (tup [x,List.replicate (t+1) true,tup (H.map tup)])=tup (f x t H)) ∧
StudentShape P r q f ∧ StudentWins P r q f) ↔
AdviceSelectorTranslation.SelectorCollapse i := by sorry