Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Hierarchy advice algorithms yield total-search advice selectors

Proved
StudentTeacher976.Adaptivity.advice_selectors_of_hierarchy_advice

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

computational-complexitypolynomial-advicepolynomial-hierarchytotal-search

Fix a hierarchy level i≥0i\ge0i≥0. Suppose that every language in Σi+1p\Sigma_{i+1}^pΣi+1p​ is decidable in deterministic polynomial time with a fixed Σip\Sigma_i^pΣip​ oracle and polynomial advice. Then every total, polynomially bounded search relation with a Δi+1p\Delta_{i+1}^pΔi+1p​ verifier has a selector in FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly:

Σi+1p⊆Δi+1p/poly⟹TFNPΣip⊆FPΣip/poly.\Sigma_{i+1}^p\subseteq\Delta_{i+1}^p/\mathrm{poly} \quad\Longrightarrow\quad \mathrm{TFNP}^{\Sigma_i^p}\subseteq\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}.Σi+1p​⊆Δi+1p​/poly⟹TFNPΣip​⊆FPΣip​/poly.

More explicitly, let T(x,y)T(x,y)T(x,y) be total, let its encoded graph belong to Δi+1p\Delta_{i+1}^pΔi+1p​, and let one polynomial bbb bound the length of every valid answer. There exist one polynomial-time Σip\Sigma_i^pΣip​-oracle program and polynomially bounded length-uniform advice realizing a function FFF such that T(x,F(x))T(x,F(x))T(x,F(x)) for every input word xxx, including the empty input. Advice is shared by all inputs of each length and need not be computable.

This nonuniform search-to-decision implication explains how a total verifiable search task without an advice selector supplies the decision-class hardness used in the mission. The polynomial advice model and oracle level are the published operational interfaces.

Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game
import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors
set_option autoImplicit false
open StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.advice_selectors_of_hierarchy_advice (i : ℕ) (hcontain : StudentTeacher976.Adaptivity.Sigma (i+1)⊆DeltaPoly i) :
    AdviceSelectorTranslation.SelectorCollapse i := by sorry
Source
Relativized nonuniform extension of Arora–Barak, Computational Complexity: A Modern Approach, January 2007 web draft, https://theory.cs.princeton.edu/complexity/book.pdf, §2.5 Decision versus search, Theorem 2.19, printed p.2.17 (55). Uses the bounded-witness prefix construction and length-uniform advice aggregation; the mission interfaces are Ježil–Tsintsilidas, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/976.pdf, §1.2.1 pp.6–7. The oracle/advice extension is stated explicitly here.

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