Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix (Q1198041)

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.