The closest vector problem (CVP) asks for a point of a lattice nearest to a given target. For a full-column-rank integer
matrix , the lattice generated by its columns
is
For a target , its distance from this lattice in the Euclidean
norm is
For an approximation factor and a positive rational radius
, the promise version of CVP distinguishes targets at
distance at most
from those at distance greater than
. Berlekamp et al.
(1978) proved the syndrome decoding problem
NP-complete, van Emde Boas (1981) showed exact CVP to be NP-hard,
and Dinur et al. (2003) established almost-polynomial-factor hardness. An
AI-generated deterministic polynomial time many-one
reduction from
-satisfiability problem given by OpenAI (2026)
proved that
is NP-hard, where
is the lattice rank and the superscript indicates the Euclidean
norm. The same construction proves
-factor hardness for the nearest-codeword and syndrome-decoding
problems for binary codes, where
is the code block length, and
-factor CVP hardness for the
norm for every fixed rational
. The reduction is direct, produces a square integer
basis, and uses neither the PCP theorem nor the projection games conjecture.