Adaptivity separation for a fixed refutable presentation
ProvedStudentTeacher976.Adaptivity.presented_adaptivity_separationadaptivitycomputational-complexitystudent-teacher
Let and suppose . Let be a polynomial-time, nondecreasing, unbounded round function with at positive lengths for some , and let be a positive polynomial-time, polynomially bounded query function. There are a total bounded search relation and a refutable presentation of , with a test, such that
Both students are measured against this same presentation. This result isolates the operational separation proved by the witness-tuple and advice-cover construction; it does not exclude students using other faithful presentations of .
Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.presented_adaptivity_separation (i : ℕ) (hardness : ¬ StudentTeacher976.Adaptivity.Sigma (i+1)⊆DeltaPoly i)
(r q : ℕ → ℕ) (hr : AdmissibleRounds r) (hq : AdmissibleQueries q) :
∃ (R : SearchRelation) (P : RefutablePresentation i R),
(∃ g : Student,UniformStudent i g ∧ StudentShape P (fun m => r m+1) (fun _ => 1) g ∧
StudentWins P (fun m => r m+1) (fun _ => 1) g) ∧
¬∃ g : Student,UniformStudent i g ∧ StudentShape P r q g ∧ StudentWins P r q g := 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, Theorem 1.4, p.7, fixed-predicate construction in §3.1, pp.19–21.