The lattice covering radius of a full-rank point lattice 
is
 |
Equivalently, it is the smallest 
such that the Euclidean closed
balls of radius 
centered at the points of 
cover 
.
The lattice covering radius problem takes a rational invertible matrix 
and a positive rational
number 
and asks whether 
.
Vallentin (2026) proved that this decision problem is 
-complete, making it complete for the second level of
the polynomial hierarchy.
Vallentin (2026) states that generative AI developed the hardness reduction under his direction. He then digested and simplified the proof and takes responsibility for its correctness.
