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.

See also

Binary Code, Euclidean Norm, Lattice Reduction, NP-Hard Problem, PCP Theorem, Point Lattice, Projection Games Conjecture, Satisfiability Problem, Syndrome Decoding Problem

Explore with Wolfram|Alpha

References

Berlekamp, E. R.; McEliece, R. J.; and van Tilborg, H. C. A. "On the Inherent Intractability of Certain Coding Problems." IEEE Trans. Inform. Th. 24, 384-386, 1978. https://doi.org/10.1109/TIT.1978.1055873.Dinur, I.; Kindler, G.; Raz, R.; and Safra, S. "Approximating CVP to Within Almost-Polynomial Factors Is NP-Hard." Combinatorica 23, 205-243, 2003. https://doi.org/10.1007/s00493-003-0019-y.OpenAI. "-Hardness of the Euclidean Closest Vector Problem." Ch. 7 in Ten Advances in Mathematics and Theoretical Computer Science. Aug. 1, 2026. https://cdn.openai.com/pdf/ten-proofs-oai.pdf.van Emde Boas, P. "Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice." Tech. Rep. MI-UvA-81-04. Amsterdam, Netherlands: Mathematical Institute, University of Amsterdam, 1981. https://staff.fnwi.uva.nl/p.vanemdeboas/vectors/mi8104c.html.

Cite this as:

Weisstein, Eric W. "Closest Vector Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ClosestVectorProblem.html

Subject classifications