Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Advice refutation translation is equivalent to advice total-search selection

Proved
StudentTeacher976.Adaptivity.advice_refutation_translation_iff_selectors

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

computational-complexitypolynomial-advicesearch-complexitystudent-teacher

Fix a hierarchy level iii. The following two statements are equivalent.

  1. For every total bounded search relation RRR and every pair of faithful refutable presentations P,QP,QP,Q with Δi+1p\Delta_{i+1}^pΔi+1p​ success tests, there is a function ψ(x,y,z)\psi(x,y,z)ψ(x,y,z) in FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly on encoded triples satisfying, for each reply of prescribed PPP-length,
∣ψ(x,y,z)∣=bQ(∣x∣),Q(x,y,ψ(x,y,z))⟹P(x,y,z).|\psi(x,y,z)|=b_Q(|x|),\qquad Q(x,y,\psi(x,y,z))\Longrightarrow P(x,y,z).∣ψ(x,y,z)∣=bQ​(∣x∣),Q(x,y,ψ(x,y,z))⟹P(x,y,z).
  1. Every total polynomially bounded search relation whose encoded graph belongs to Δi+1p\Delta_{i+1}^pΔi+1p​ has a selector in FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly:
∀x  T(x,f(x)).\forall x\;T(x,f(x)).∀xT(x,f(x)).

A map in the first statement may depend on both fixed presentations and on the proposed candidate. Each computation uses a fixed oracle program, and its polynomial advice is shared by all inputs of each encoded length. Zero certificate lengths are permitted.

This equivalence characterizes a general presentation-normalization principle. It does not assert either of the equivalent conditions, or that such a universal principle is necessary for a particular game separation.

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.advice_refutation_translation_iff_selectors (i : ℕ) :
    (∀ (R : SearchRelation) (P Q : RefutablePresentation i R),
      ∃ ψ : Word → Word → Word → Word,
        (∃ F : Word → Word,InFPAdvice i F ∧ ∀ x y z,F (tup [x,y,z])=ψ x y z) ∧
        (∀ x y z : Word,z.length=P.refutationLength.eval x.length →
          (ψ x y z).length=Q.refutationLength.eval x.length) ∧
        ∀ x y z : Word,z.length=P.refutationLength.eval x.length →
          Q.test x y (ψ x y z) → P.test x y z) ↔ AdviceSelectorTranslation.SelectorCollapse i := 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, Definition 1.2 p.7 and length-uniform advice condition in Theorem 1.4 p.7. Derived interface classification using the certified-replacement game; both implications formalized in this development.

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