NP-hardness of computing lattice diameters of lattice polytopes
NP-hardness of computing lattice diameters of lattice polytopes
From papers
Let and let be a lattice -polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of is an -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
Sign in to submit a solution.
No solutions have been posted yet.