Positive validity certificates yield a two-round refutation presentation
ProvedStudentTeacher976.Adaptivity.certified_replacement_resourcesLet be a total polynomially bounded search relation with a refutable presentation at level . Suppose that also has exact-length positive certificates: there are a polynomial and a predicate decidable in such that
Let be polynomial-time length functions. Suppose their effective round and query counts are positive at every length, and the round count is at least two at every sufficiently large length. Then
The membership permits a new faithful refutation presentation of the same underlying relation. Neither monotonicity nor unboundedness of is required; eventual availability of two rounds suffices. The empty input uses the published length-one resource convention. This isolates a reusable consequence of allowing alternative refutation presentations, with the raw input length and both resource functions preserved. It does not assert a round reduction for a fixed presentation.
import Definitions.Def_StudentTeacher976_Adaptivity_Game set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
theorem StudentTeacher976.Adaptivity.certified_replacement_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)
(hV : ∀ x y, 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