AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_offline_opt

def

For any natural number n and job processing vector w : Fin n → ℝ, the offline optimal total completion time nonclairvoyant_scheduling_offline_opt w is the minimum over all permutations π of Fin n of the sum ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i).

Statement

noncomputable def nonclairvoyant_scheduling_offline_opt {n : ℕ} (w : Fin n → ℝ) : ℝ
Defined in
arXiv:2610.29037 Section 4 (text before Lemma 4.2)
Verified
25 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given a natural number n (implicit) and a function w : Fin n → ℝ, nonclairvoyant_scheduling_offline_opt w is defined as the minimum (infimum) over all permutations π : Equiv.Perm (Fin n) of the sum ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i), where i : Fin n is coerced to ℝ via its underlying value in {0, …, n - 1}. The nonemptiness of the set of permutations is witnessed by the identity permutation 1.

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

/-- The offline optimal total completion time for jobs with processing times vector w in R^n. -/
noncomputable def nonclairvoyant_scheduling_offline_opt {n : ℕ} (w : Fin n → ℝ) : ℝ := Finset.univ.inf' ⟨1, Finset.mem_univ 1⟩
    (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i))
See it in the graphDiscuss this resultChallenge it