AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_opt

def

For a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some list os of configurations satisfies List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ (os has the same length as ρ and its t-th configuration serves the t-th request) and gen_k_server_uniform_path_cost a os = c.

Statement

noncomputable def gen_k_server_uniform_opt {k m : ℕ} (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℕ
Defined in
arXiv:2610.37192, Sec. 2: OPT(ρ), the minimum cost of an offline solution starting from a
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…
Used by 4

Read back from the Lean

Given natural numbers k and m (implicit), a starting configuration a : Fin k → Fin m, and a sequence of request configurations ρ : List (Fin k → Fin m), gen_k_server_uniform_opt a ρ evaluates to the infimum (in ℕ) of the set of natural numbers c for which there exists a sequence of configurations os : List (Fin k → Fin m) such that: 1. os and ρ have the same length, and for every corresponding pair (o, r) in os and ρ, there exists some index i : Fin k such that o i = r i (i.e., List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ). 2. The path cost gen_k_server_uniform_path_cost a os equals c.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Offline optimum OPT(ρ): the least movement cost of a sequence of configurations, started from `a`, whose t-th configuration serves the t-th request. -/
noncomputable def gen_k_server_uniform_opt {k m : ℕ} (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℕ :=
  sInf {c | ∃ os : List (Fin k → Fin m),
    List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c}
See it in the graphDiscuss this resultChallenge it