Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
type: Item
instance of: scholarly article
title: Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
zbMATH Open document ID: 0758.90060
DOI: 10.1016/0020-0190(92)90134-H
author: Boleslaw Szymanski
author: Balaram Sinharoy
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: The paper establishes complexity of the well-known closest vector problem in an arbitrary norm in a lattice generated by a (0,1)-matrix --- the authors refer to this problem as (0,1)-CVP. In finite norms, this problem is NP-hard when the input vector contains nonzero elements. (0,1)-CVP in infinite norm is NP-hard if, and only if, the input vector contains at least one element with the absolute value bigger than 1. These results are applicable to problems on graphs and networks in which the corresponding incidence matrix generating the CVP lattice contains elements restricted to \(\{0,1\}\) or \(\{-1,0,1\}\). The authors used these result to establish complexity of data alignment in SIMD architectures. The presented complexity proofs use a reduction technique that can be useful in analyzing other minimization problems. The essence of this technique is to reduce a propositional logic problem to a satisfiability problem of an inequality over integers, which in turn is reduced to some minimization problem. The techniques generalize readily to complexity analysis of the related shortest vector problem (SVP) in infinity norm. SVP is NP-hard in infinity norm even if the lattice generating matrix contains elements restrited to \(\{0,1,r\}\), where \(| r|>1\). However, this problem has a (trivial) polynomial-time solution if the lattice generating matrix has all its elements in \(\{-1,0,1\}\). Recently, the authors extended the results of this paper as follows. Let \(A\) denote the matrix that generates the problem lattice, \(v\) stands for the input vector and \(r=gcd(A_{ij})\), \(s=\max\{| v_ i|\}\). In all norms CVP has a polynomial-time solution if \(s\leq| r|/2\), otherwise, it is NP-hard. For SVP in infinity norm, the problem is NP- hard if matrix \(A\) contains at least two nonzero elements with different absolute values. Otherwise, this problem has a polynomial-time solution.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 92104
zbMATH Keywords: NP-completeness
zbMATH Keywords: closest vector problem
zbMATH Keywords: lattice
zbMATH Keywords: satisfiability
zbMATH Keywords: shortest vector problem
MaRDI profile type: Publication
cites work: Minkowski's Convex Body Theorem and Integer Programming
cites work: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
cites work: Reducibility among Combinatorial Problems
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: Q4095873
full work available at URL: 0020-0190(92)90134-h
OpenAlex ID: W2006958860
description: scientific article; zbMATH DE number 92104