AFTD Auto-Formalizing Theoretical Domains

deadline_paging_feasible_sublist

theoremverified

Feasibility of a schedule for a request list passes to any sublist of the requests.

Statement

theorem deadline_paging_feasible_sublist
    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α)
    {reqs reqs' : List (DeadlineRequest α)} (hsub : reqs' ⊆ reqs)
    (h : IsFeasibleSchedule k C₀ sched reqs) :
    IsFeasibleSchedule k C₀ sched reqs'
Source
step towards deadline_paging_optimal_competitive_ratio_two_holes
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • IsFeasibleScheduleA schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it…
  • DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…

The proof, explained

Feasibility of a schedule requires an initial cache condition, a capacity bound at each step, and timely satisfaction of every request in the list. The first two requirements are independent of the request sequence, while every request in a sublist is already present in the original list. The proof directly reuses the initial state and capacity bounds from the original feasibility hypothesis, and applies its request-satisfaction guarantee to each request in the sublist via the inclusion `reqs' ⊆ reqs`.

  1. The schedule `sched` is feasible for the sublist `reqs'`.

    A schedule is feasible for `reqs'` if: (1) its initial configuration is `C₀`, (2) the cache capacity `k` is respected at all times, and (3) every request in `reqs'` is served between its arrival and deadline. The first two conditions do not depend on the request list and hold directly from the feasibility of `sched` for `reqs` (`h.1` and `h.2.1`). For the third condition, given any request `r ∈ reqs'`, the assumption `hsub` implies `r ∈ reqs`, so the service guarantee from feasibility on `reqs` (`h.2.2`) applies directly. Combining these three facts establishes feasibility for `reqs'`.

    line 6

        IsFeasibleSchedule k C₀ sched reqs' := ⟨h.1, h.2.1, fun r hr => h.2.2 r (hsub hr)⟩

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Feasibility is inherited by sublists, hence in particular by arrival prefixes. -/theorem deadline_paging_feasible_sublist    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α)    {reqs reqs' : List (DeadlineRequest α)} (hsub : reqs' ⊆ reqs)    (h : IsFeasibleSchedule k C₀ sched reqs) :    IsFeasibleSchedule k C₀ sched reqs' := ⟨h.1, h.2.1, fun r hr => h.2.2 r (hsub hr)⟩
See it in the graphDiscuss this resultChallenge it