Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Length-uniform oracle advice computation and total-search selectors

Definition
StudentTeacher976_Adaptivity_AdviceSelectors

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexitypolynomial-advicestudent-teacher

Fix a hierarchy level iii. A string function fff belongs to FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly if a single fixed oracle-polynomial function GGG, a polynomial bbb, and one advice word a(n)a(n)a(n) for every input length satisfy

∣a(n)∣≤b(n),f(x)=G(⟨x,a(∣x∣)⟩).|a(n)|\le b(n),\qquad f(x)=G(\langle x,a(|x|)\rangle).∣a(n)∣≤b(n),f(x)=G(⟨x,a(∣x∣)⟩).

The function GGG uses one fixed Σip\Sigma_i^pΣip​ 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 TTT with an encoded graph in Δi+1p\Delta_{i+1}^pΔi+1p​ has such a selector:

∀x  T(x,f(x)).\forall x\;T(x,f(x)).∀xT(x,f(x)).

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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me