The covering radius of a full-rank point lattice 
is
 |
Equivalently, it is the smallest 
such that the closed Euclidean 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 and drafted and revised the paper under his direction. He then digested and simplified the proof and takes responsibility for its correctness.
