Total-search selectors yield efficient refutation translations
ProvedStudentTeacher976.Adaptivity.refutation_translation_of_selectorsadaptivitycomputational-complexitystudent-teacher
Fix and assume that every total polynomially bounded search relation whose encoded graph lies in has an selector. For any two refutable presentations of the same total search relation, there exists an function on encoded triples such that, whenever ,
The tests and in this formula are the presentations' success predicates. The selector hypothesis is an explicit additional assumption. The resulting map is an interface for transferring uniform students between presentations without increasing their resource budgets.
Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_Selectors set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.refutation_translation_of_selectors (i : ℕ) (hselectors : SelectorPresentationTranslation.SelectorCollapse i)
(R : SearchRelation) (P Q : RefutablePresentation i R) :
∃ ψ : Word → Word → Word → Word,
(∃ F : Word → Word,InFP 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 := by sorrySource
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; selector-case refutation-translation interface developed for this formalization.