Certified replacements need exist only when the default answer fails
ProvedStudentTeacher976.Adaptivity.conditional_certified_refinement_resourcesLet be a total polynomially bounded search relation with a refutable presentation at hierarchy level . Let denote the empty answer string. Suppose a predicate , decidable in , and a polynomial satisfy
Thus certificates soundly identify valid answers. They need exist only on inputs where the empty default answer is invalid.
Let 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
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.
import Definitions.Def_StudentTeacher976_Adaptivity_Game set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
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