Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Presentation invariance is equivalent to total-search selectors

Proved
StudentTeacher976.Adaptivity.presentation_invariance_iff_total_search_selectors

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

computational-complexityrefutation-presentationstudent-teachertotal-search

Fix a hierarchy level iii and admissible round and query functions r,qr,qr,q, with the conventions of Theorem 1.4. A faithful refutation presentation specifies an underlying total search relation RRR by a bounded universally quantified refutation predicate. For a fixed presentation, solvability means that one uniform FPΣip\mathrm{FP}^{\Sigma_i^p}FPΣip​ student satisfies the shape and winning conditions of Definition 1.2.

The following two conditions are equivalent:

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

In symbols, writing Win⁡r,q(P)\operatorname{Win}_{r,q}(P)Winr,q​(P) for solvability with the fixed presentation PPP,

[∀R ∀P,Q presenting R,Win⁡r,q(Q)⇒Win⁡r,q(P)]⟺TFNPΣip⊆FPΣip.\bigl[\forall R\,\forall P,Q\text{ presenting }R,\quad \operatorname{Win}_{r,q}(Q)\Rightarrow\operatorname{Win}_{r,q}(P)\bigr] \quad\Longleftrightarrow\quad \mathrm{TFNP}^{\Sigma_i^p}\subseteq\mathrm{FP}^{\Sigma_i^p}.[∀R∀P,Q presenting R,Winr,q​(Q)⇒Winr,q​(P)]⟺TFNPΣip​⊆FPΣip​.

This criterion identifies exactly the extra search assumption required for unrestricted presentation invariance at any one admissible resource budget. It does not assume a decision-class hardness condition or assert that the selector condition holds.

Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game
import Definitions.Def_StudentTeacher976_Adaptivity_Selectors
set_option autoImplicit false
Formal statement
theorem StudentTeacher976.Adaptivity.presentation_invariance_iff_total_search_selectors (i : ℕ) (r q : ℕ → ℕ)
    (hr : StudentTeacher976.Adaptivity.AdmissibleRounds r)
    (hq : StudentTeacher976.Adaptivity.AdmissibleQueries q) :
    (∀ (R : StudentTeacher976.Adaptivity.SearchRelation)
      (P Q : StudentTeacher976.Adaptivity.RefutablePresentation i R),
      (∃ g : StudentTeacher976.Adaptivity.Student,
        StudentTeacher976.Adaptivity.UniformStudent i g ∧
        StudentTeacher976.Adaptivity.StudentShape Q r q g ∧
        StudentTeacher976.Adaptivity.StudentWins Q r q g) →
      ∃ f : StudentTeacher976.Adaptivity.Student,
        StudentTeacher976.Adaptivity.UniformStudent i f ∧
        StudentTeacher976.Adaptivity.StudentShape P r q f ∧
        StudentTeacher976.Adaptivity.StudentWins P r q f) ↔
      StudentTeacher976.Adaptivity.SelectorPresentationTranslation.SelectorCollapse i := by sorry
Source
Derived 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, with the admissible budgets of Theorem 1.4, p.7. This equivalence is a proved formalization consequence, not a separately numbered assertion in the source.

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