Adaptivity separation assuming total-search selectors with polynomial advice
ProvedStudentTeacher976.Adaptivity.adaptivity_separation_of_advice_total_search_selectorsadaptivitycomputational-complexitypolynomial-advicestudent-teacher
Let , and suppose . Assume additionally that every total polynomially bounded search relation with a -decidable encoded graph has a selector in . Advice is shared by every input of a given length and is polynomially bounded.
For every polynomial-time, nondecreasing, unbounded satisfying at positive lengths for some , and every positive polynomial-time, polynomially bounded query function ,
The conclusion concerns underlying relations and allows arbitrary faithful presentations. The selector assumption is an explicit additional hypothesis, weaker than requiring uniform selectors. This variant isolates a sufficient search-class condition for handling changes of presentation in the nonuniform lower-bound argument.
Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors set_option autoImplicit false open StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.adaptivity_separation_of_advice_total_search_selectors
(i : ℕ) (hardness : ¬ StudentTeacher976.Adaptivity.Sigma (i+1) ⊆ DeltaPoly i)
(r q : ℕ → ℕ) (hr : AdmissibleRounds r) (hq : AdmissibleQueries q)
(hselectors : AdviceSelectorTranslation.SelectorCollapse i) :
¬ ST i (fun m => r m+1) (fun _ => 1) ⊆ ST i r q := by sorrySource
Ježil–Tsintsilidas, Parallelism and Adaptivity in Student-Teacher Witnessing, STOC 2027 submission #976, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/976.pdf, Theorem 1.4, p.7; §3.1, pp.19–21 and Appendix A, pp.39–40. Variant with an explicit additional selector hypothesis and a strengthened advice-student lower bound.