Adaptivity separation assuming efficient total-search selectors
ProvedStudentTeacher976.Adaptivity.adaptivity_separation_of_total_search_selectorscomputational-complexitystudent-teacher-gamestotal-search
Fix a hierarchy level , assume , and let satisfy exactly the source's admissibility conditions. Assume additionally that every total polynomially bounded search relation with a verifier has a uniform selector. Then
This is the efficient-selector case of the semantic separation. Both ST classes quantify over faithful presentations of the underlying total search relation; no common presentation is assumed. The additional selector assumption is explicitly part of this supporting theorem, rather than a hypothesis of the mission's main theorem.
Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_Selectors open QAdvFew.PoQOracle
Formal statement
namespace StudentTeacher976.Adaptivity
theorem adaptivity_separation_of_total_search_selectors (i : ℕ)
(hardness : ¬ Sigma (i+1) ⊆ DeltaPoly i)
(r q : ℕ → ℕ) (hr : AdmissibleRounds r) (hq : AdmissibleQueries q)
(hselectors : SelectorPresentationTranslation.SelectorCollapse i) :
¬ ST i (fun m => r m+1) (fun _ => 1) ⊆ ST i r q := by sorry
end StudentTeacher976.AdaptivitySource
Proof-case decomposition of Ježil–Tsintsilidas, Parallelism and Adaptivity in Student-Teacher Witnessing, STOC 2027 submission #976, Theorem 1.4 p.7 and canonical construction §3.1 pp.19–21, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/976.pdf. The explicit total-search case assumption is introduced by this formal development and is not an additional assumption of the source theorem.