Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Adaptivity separation assuming total-search selectors with polynomial advice

Proved
StudentTeacher976.Adaptivity.adaptivity_separation_of_advice_total_search_selectors

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptivitycomputational-complexitypolynomial-advicestudent-teacher

Let i≥0i\ge0i≥0, and suppose Σi+1p⊈Δi+1p/poly\Sigma_{i+1}^p\not\subseteq\Delta_{i+1}^p/\mathrm{poly}Σi+1p​⊆Δi+1p​/poly. Assume additionally that every total polynomially bounded search relation with a Δi+1p\Delta_{i+1}^pΔi+1p​-decidable encoded graph has a selector in FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly. Advice is shared by every input of a given length and is polynomially bounded.

For every polynomial-time, nondecreasing, unbounded rrr satisfying 1≤r(m)≤m1−ε1\le r(m)\le m^{1-\varepsilon}1≤r(m)≤m1−ε at positive lengths for some ε>0\varepsilon>0ε>0, and every positive polynomial-time, polynomially bounded query function qqq,

STΣip[r(m)+1,1]⊈STΣip[r(m),q(m)].\mathrm{ST}^{\Sigma_i^p}[r(m)+1,1]\not\subseteq\mathrm{ST}^{\Sigma_i^p}[r(m),q(m)].STΣip​[r(m)+1,1]⊆STΣip​[r(m),q(m)].

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 sorry
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me