Exact finite-horizon verification of chunk-system online cost bounds
ProvedKServer.finite_chunk_certificate_iffLet X be a finite metric space with marked points s,t. Fix a size window [cₗ,cᵤ], a required expected total T, an escape price p, and a minimum chunk count m₀. The following existence statements are equivalent:
A finite-horizon certificate records a common bound H on the length of every sampled complete request sequence and tests the conditional cost bounds against tables of positions and bailout decisions on histories of length at most H. The full model instead quantifies over online algorithms and escape rules on arbitrary finite histories. All request-feasibility, filtration, size-window, offline-cost, expected-total, and minimum-count constraints are retained.
The equivalence makes the online-adversary test family finite for every fixed horizon on a finite metric space. It does not assert an efficient search algorithm or the existence of a certificate for arbitrary parameters.
import Definitions.Def_KServer_finite_chunk_certificates open KServer
theorem KServer.finite_chunk_certificate_iff {X : Type*} [MetricSpace X] [Finite X] {s t : X}
{cLo cHi T p : ℝ} {mLo : ℕ} :
(∃ C : FiniteChunkSystemB X s t cLo cHi T p mLo,
∀ ω₁ ω₂ : C.Ω, C.hist 0 ω₁ = C.hist 0 ω₂) ↔
(∃ D : ChunkSystemB X s t cLo cHi T p mLo,
∀ ω₁ ω₂ : D.Ω, D.hist 0 ω₁ = D.hist 0 ω₂) := by sorry