A total certified refinement suffices for two-round presentation membership
ProvedStudentTeacher976.Adaptivity.total_certified_refinement_resourcesLet be a total polynomially bounded search relation with a refutable presentation at hierarchy level . Suppose a predicate , decidable in , and a polynomial satisfy
These conditions give a sound certificate for at least one valid answer on each input. Other valid answers need not have such certificates.
Let be polynomial-time length functions with positive effective resource counts at every length, and assume that the effective round count is at least two at all sufficiently large lengths. Then
Membership permits an alternative faithful refutation presentation of the same relation and preserves the original raw input length and resource functions. This strengthens the positive-validity-certificate construction to total verifiable refinements. It is useful for checking whether a search construction can separate intrinsic round budgets when changes of presentation are allowed. The empty input follows the published length-one resource convention.
import Definitions.Def_StudentTeacher976_Adaptivity_Game set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
theorem StudentTeacher976.Adaptivity.total_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, ∃ 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