Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Presentation transfer with advice is equivalent to total-search advice selectors

Proved
StudentTeacher976.Adaptivity.presentation_transfer_with_advice_iff_total_search_selectors

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

computational-complexitypolynomial-advicerefutation-presentationstudent-teachertotal-search

Fix a hierarchy level iii and admissible round and query functions r,qr,qr,q. A faithful refutation presentation specifies an underlying total search relation by a bounded universally quantified predicate. A uniform student uses one polynomial-time Σip\Sigma_i^pΣip​-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:

  1. For every total search relation RRR and every two faithful presentations P,QP,QP,Q of RRR, existence of a uniform winning student for QQQ within (r,q)(r,q)(r,q) implies existence of an advised winning student for PPP within the same budget.
  2. Every total, polynomially bounded search relation with a Δi+1p\Delta_{i+1}^pΔi+1p​ verifier has an FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly selector.

Writing Wr,q(Q)W_{r,q}(Q)Wr,q​(Q) and Wr,qadv(P)W_{r,q}^{\mathrm{adv}}(P)Wr,qadv​(P) for the two kinds of solvability, the equivalence is

[∀R ∀P,Q presenting R,Wr,q(Q)⇒Wr,qadv(P)]⟺TFNPΣip⊆FPΣip/poly.\bigl[\forall R\,\forall P,Q\text{ presenting }R,\quad W_{r,q}(Q)\Rightarrow W_{r,q}^{\mathrm{adv}}(P)\bigr] \quad\Longleftrightarrow\quad \mathrm{TFNP}^{\Sigma_i^p}\subseteq\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}.[∀R∀P,Q presenting R,Wr,q​(Q)⇒Wr,qadv​(P)]⟺TFNPΣip​⊆FPΣip​/poly.

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.

Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game
import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors
set_option autoImplicit false
open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
open AdviceComputations (InFPAdvice)
Formal statement
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
Source
Derived nonuniform interface criterion for 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, Definitions 1.1–1.2, pp.6–7, admissible budgets of Theorem 1.4, p.7, and length-uniform advice as in the proof of Theorem 1.4, pp.20–21. This equivalence is a proved formalization consequence, not a separately numbered source assertion.

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