Complexity of the Closest Vector Problem in a Lattice Generated by (0,1)-Matrix Balaram Sinharoy Boleslaw K. Szymanski NP-completeness closest vector lattice The closest vector problem, often referred to as CVP, is to find a vector in a lattice that is closest to a given (input) vector. The problem, well-known in mathematical programming, was proven NP-hard for an arbitrary lattice and norm [1, 6]. This general result does not apply, however, to problems in which a lattice is generated by a matrix whose elements belong to some proper subset of integers. For example, minimization problems in graphs and networks can be treated as CVP in a lattice generated by the incidence matrix of a graph or a network. Incidence matrices have their elements in {0,1} 0r {-1, 0, 1} therefore the complexity of such problems cannot be established on the basis of the general result mentioned above. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-91-11
Complexity of the Closest Vector Problem in a Lattice Generated by (0,1)-Matrix
Balaram Sinharoy
Boleslaw K. Szymanski
NP-completeness
closest vector
lattice
The closest vector problem, often referred to as CVP, is to find a vector in a lattice that is closest to a given (input) vector. The problem, well-known in mathematical programming, was proven NP-hard for an arbitrary lattice and norm [1, 6]. This general result does not apply, however, to problems in which a lattice is generated by a matrix whose elements belong to some proper subset of integers. For example, minimization problems in graphs and networks can be treated as CVP in a lattice generated by the incidence matrix of a graph or a network. Incidence matrices have their elements in {0,1} 0r {-1, 0, 1} therefore the complexity of such problems cannot be established on the basis of the general result mentioned above.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-91-11