The fixed-presentation adaptivity separation excludes advice students
ProvedStudentTeacher976.Adaptivity.presented_adaptivity_separation_with_adviceFix and assume . Let and satisfy the admissibility conditions of Theorem 1.4, including monotonicity, unboundedness and the positive sublinear bound for .
There exist a total search relation and one faithful refutation presentation of such that:
- A uniform student wins with this presentation in rounds and one query per round.
- No student realized by wins with this same presentation in rounds and simultaneous queries per round.
Writing for uniform solvability of the fixed presentation, and for solvability with polynomial advice,
Advice is shared by all student inputs of each encoded input length and need not be computable. The result strengthens the lower bound for a fixed presentation to exclude advised students. Both resource budgets and the refutation presentation are kept fixed in the comparison. It does not assert noninclusion between classes that permit arbitrary replacement presentations of the underlying relation.
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity open AdviceComputations (InFPAdvice)
theorem StudentTeacher976.Adaptivity.presented_adaptivity_separation_with_advice (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,
(∃ F : Word → Word,InFPAdvice i F ∧ ∀ (x : Word) (t : ℕ) (H : List (List Word)),
F (tup [x,List.replicate (t+1) true,tup (H.map tup)])=tup (g x t H)) ∧
StudentShape P r q g ∧ StudentWins P r q g := by sorry