NP-hardness of computing lattice diameters of lattice polytopes

About 1 year old · traced to

Let d≥3d \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.

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.