Hierarchy advice algorithms yield total-search advice selectors
ProvedStudentTeacher976.Adaptivity.advice_selectors_of_hierarchy_adviceFix a hierarchy level . Suppose that every language in is decidable in deterministic polynomial time with a fixed oracle and polynomial advice. Then every total, polynomially bounded search relation with a verifier has a selector in :
More explicitly, let be total, let its encoded graph belong to , and let one polynomial bound the length of every valid answer. There exist one polynomial-time -oracle program and polynomially bounded length-uniform advice realizing a function such that for every input word , 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.
import Definitions.Def_StudentTeacher976_Adaptivity_Game import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors set_option autoImplicit false open StudentTeacher976.Adaptivity
theorem StudentTeacher976.Adaptivity.advice_selectors_of_hierarchy_advice (i : ℕ) (hcontain : StudentTeacher976.Adaptivity.Sigma (i+1)⊆DeltaPoly i) :
AdviceSelectorTranslation.SelectorCollapse i := by sorry