Length-uniform oracle advice computation and total-search selectors
DefinitionStudentTeacher976_Adaptivity_AdviceSelectorscomputational-complexitypolynomial-advicestudent-teacher
Fix a hierarchy level . A string function belongs to if a single fixed oracle-polynomial function , a polynomial , and one advice word for every input length satisfy
The function uses one fixed oracle and has a fixed polynomial clock on every encoded input, including malformed encodings. Advice need not be computable and is the same for all words of a given length.
The accompanying selector-collapse predicate is the explicit hypothesis that every total polynomially bounded search relation with an encoded graph in has such a selector:
These predicates support analysis of presentation changes when the final lower-bound argument permits polynomial advice. They do not assert any collapse, hardness assumption or game separation.
Definition code
import Definitions.Def_StudentTeacher976_Adaptivity_Complexity
set_option autoImplicit false
open QAdvFew.PoQOracle
namespace StudentTeacher976.Adaptivity.AdviceComputations
/-- A fixed oracle transducer, with one polynomially bounded advice word per input length.
Its underlying InFP program has a polynomial clock on every raw input string. -/
def InFPAdvice (i : ℕ) (f : Word → Word) : Prop :=
∃ (G : Word → Word) (b : Polynomial ℕ) (a : ℕ → Word),
InFP i G ∧ (∀ n,(a n).length ≤ b.eval n) ∧
∀ x,G (tup [x,a x.length])=f x
end StudentTeacher976.Adaptivity.AdviceComputations
namespace StudentTeacher976.Adaptivity.AdviceSelectorTranslation
/-- An explicit search-class hypothesis allowing length-uniform polynomial advice.
It asserts no hardness condition or game separation. -/
def SelectorCollapse (i : ℕ) : Prop :=
∀ T : SearchRelation,{s | ∃ x y,s=tup [x,y] ∧ T x y}∈Delta i →
(∀ x,∃ y,T x y) →
∀ b : Polynomial ℕ,(∀ x y,T x y → y.length ≤ b.eval x.length) →
∃ F : Word → Word,AdviceComputations.InFPAdvice i F ∧ ∀ x,T x (F x)
end StudentTeacher976.Adaptivity.AdviceSelectorTranslation
Source
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, §1.2.1, pp.6–7, and the length-uniform advice condition of Theorem 1.4, p.7; functional and selector interfaces introduced explicitly for this development.