AFTD Auto-Formalizing Theoretical Domains

tsp_opt

def

OPT is the infimum length of a tour on V under edge weights ℓ.

Statement

noncomputable def tsp_opt {V : Type*} [Fintype V] [DecidableEq V] (ℓ : V → V → ℝ) : ℝ
Defined in
arXiv:2611.09421 Section 1
Verified
10 Nov 2026
Axioms
none listed
Built on 2
  • is_tsp_tourA tour on a finite set V is a permutation σ of V that forms an n-cycle (it is a cycle and has full support).
  • tsp_tour_lengthThe length of a tour σ on a finite set V under edge weight function ℓ is ∑_{v ∈ V} ℓ(v, σ(v)).

Read back from the Lean

Given a finite type V with decidable equality and an edge-weight function ℓ : V → V → ℝ, tsp_opt ℓ is defined as the real infimum (sInf) of the set of tour lengths tsp_tour_length ℓ σ over all permutations σ : Equiv.Perm V satisfying is_tsp_tour σ.

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

/-- OPT is the infimum length of a tour on V under edge weights ℓ. -/
noncomputable def tsp_opt {V : Type*} [Fintype V] [DecidableEq V] (ℓ : V → V → ℝ) : ℝ := sInf {tsp_tour_length ℓ σ | (σ : Equiv.Perm V) (_ : is_tsp_tour σ)}
See it in the graphDiscuss this resultChallenge it