NP-hardness of computing lattice diameters of lattice polytopes
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.
References
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).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.