Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Certified replacements need exist only when the default answer fails

Proved
StudentTeacher976.Adaptivity.conditional_certified_refinement_resources

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

adaptivitycomputational-complexitystudent-teacher

Let RRR be a total polynomially bounded search relation with a refutable presentation at hierarchy level iii. Let eee denote the empty answer string. Suppose a predicate VVV, decidable in Δi+1p\Delta_{i+1}^pΔi+1p​, and a polynomial ccc satisfy

∣v∣=c(∣x∣) ∧ V(x,y,v) ⟹ R(x,y),¬R(x,e) ⟹ ∃y,v∣v∣=c(∣x∣) ∧ V(x,y,v).\begin{aligned} |v|=c(|x|)\ \wedge\ V(x,y,v)&\ \Longrightarrow\ R(x,y),\\ \neg R(x,e)&\ \Longrightarrow\ \exists y,v\quad |v|=c(|x|)\ \wedge\ V(x,y,v). \end{aligned}∣v∣=c(∣x∣) ∧ V(x,y,v)¬R(x,e)​ ⟹ R(x,y), ⟹ ∃y,v∣v∣=c(∣x∣) ∧ V(x,y,v).​

Thus certificates soundly identify valid answers. They need exist only on inputs where the empty default answer is invalid.

Let r,qr,qr,q be polynomial-time length functions whose effective resource counts are positive at every length, and suppose that at least two rounds are available at all sufficiently large lengths. Then

R∈STΣip[r,q].R\in\mathrm{ST}^{\Sigma_i^p}[r,q].R∈STΣip​[r,q].

Membership permits a different faithful refutation presentation of the same underlying relation and evaluates the unchanged resource functions at the same raw input lengths. This extends the total certified-refinement construction to refinements that need cover only the inputs where a fixed default answer fails. The empty input uses the published length-one resource convention.

Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game
set_option autoImplicit false
open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.conditional_certified_refinement_resources {i : ℕ} {R : SearchRelation} (P : RefutablePresentation i R)
    (c : Polynomial ℕ) (V : Word → Word → Word → Prop)
    (heff : {s | ∃ x y z, s = tup [x,y,z] ∧ V x y z} ∈ Delta i)
    (hsound : ∀ x y v, v.length = c.eval x.length → V x y v → R x y)
    (htotal : ∀ x, ¬ R x [] → ∃ y v, v.length = c.eval x.length ∧ V x y v)
    (r q : ℕ → ℕ) (hr : PolyTimeLength r) (hq : PolyTimeLength q)
    (hrpos : ∀ n, 1 ≤ resource r n) (hqpos : ∀ n, 1 ≤ resource q n)
    (hevent : ∃ N : ℕ, ∀ n, N ≤ n → 2 ≤ resource r n) : R ∈ ST i r q := by sorry
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, Definitions 1.1–1.2, pp.6–7. Derived generalization of the mission development's total certified-refinement theorem: certificate existence is required only when the empty default answer is invalid. This auxiliary construction is not asserted in the source.

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