Presentation invariance is equivalent to total-search selectors
ProvedStudentTeacher976.Adaptivity.presentation_invariance_iff_total_search_selectorscomputational-complexityrefutation-presentationstudent-teachertotal-search
Fix a hierarchy level and admissible round and query functions , with the conventions of Theorem 1.4. A faithful refutation presentation specifies an underlying total search relation by a bounded universally quantified refutation predicate. For a fixed presentation, solvability means that one uniform student satisfies the shape and winning conditions of Definition 1.2.
The following two conditions are equivalent:
- For every total search relation and every two faithful presentations of , solvability using within the budget implies solvability using within the same budget.
- Every total, polynomially bounded search relation with a verifier has a uniform selector.
In symbols, writing for solvability with the fixed presentation ,
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 sorrySource
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.