NP-hardness of computing lattice diameters of lattice polytopes

From papers

Let d3d \geq 3 and let PP be a lattice dd-polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of PP is an NP\operatorname{\mathsf{NP}}-hard problem. This would extend the established NP-hardness result from bounded semi-algebraic sets, even when the diameter direction is fixed, to lattice polytopes.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Anouk E. Brose, Jesús A. De Loera, Gyivan Lopez-Campos and Antonio J. Torres, “On Lattice Diameter Segments and A Discrete Borsuk Partition Problem”, arXiv:2508.20009 (2025).

Solutions 0

No solutions have been posted yet.