Closest Vector Problem

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.