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

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

Complexity of the Closest Vector Problem in a Lattice Generated by (0,1)-MatrixBoleslaw K. Szymanski and Balaram SinharoyDepartment of Computer Science Rensselaer Polytechnic Institute Troy, N.Y. 12180-3590, USA

Keywords: NP-completeness, closest vector, lattice, satis ability.

1 IntroductionThe closest vector problem, often referred to as CVP, is to nd 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 f0; 1g or f?1; 0; 1g only, therefore the complexity of such problems cannot be established on the basis of the general result mentioned above. In this paper we investigate complexity of the CVP in a lattice generated by the matrix whose elements are in f0; 1g. We refer to this problem as (0,1)-CVP. Our interest in (0,1)CVP was motivated by the data alignment problem for SIMD architectures 5]. In a Single Instruction stream{ Multiple Data stream (SIMD) computer, a signi cant speedup can be achieved by distributing (or mapping) data structures in a program to individual processors. One processor is allocated (at least conceptually) per data item of an array or other composite data structures. Operations involving arrays can be performed entirely locally if the operand array elements are allocated to the same processor. Otherwise, computation has to be interwovenThis work was partially supported by National Science Foundation under grants CCR-8920694 and CDA8805910. Some results of this paper were presented at XIV International Symposium on Mathematical Programming, Amsterdam, Netherlands, August 5{9, 1991. The paper was published in Information Processing Letters, vol. 42, May 1992, pp. 121-6, Copyright Elsevier Science Publishers B.V.

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

2

2 BASIC DEFINITIONS

with a time consuming interprocessor communication needed to fetch non-local arguments and to store non-local results. The cost of communication depends on network locations of the communicating processors and the network interconnection pattern. One of the major challenges in programming SIMD computers is to distribute data structures among the processors in such a way that the interprocessor communication is minimized. The data alignment problem 5] is to determine the relative shifts of the distributed data structures' dimensions so that the required interprocessor communication is at minimum. The alignment problem is equivalent to nding the closest vector in a lattice generated by a matrix with elements in f-1,0,1g 5]. For hypercubes and the four nearest neighbor mesh, the two networks often used in practice,

the distance between processors is measured in the rst norm. In the eight nearest neighbor interconnection the corresponding norm is in nity. As shown later, the (0,1)-CVP (equivalent to the data alignment problem) is NP-hard in these norms, except in the (trivial) case of in nity norm and the input vector with elements in f0; 1g. The NP-hardness of (0,1)-CVP may be useful in establishing complexity of other minimization problems de ned over (0,1)-matrices, in particular, incidence matrices of graphs and networks which are frequently encountered in applications. The paper is organized as follows. The next section provides the basic de nitions. The proof that (0,1)-CVP is NP-hard in an arbitrary nite norm is given in Section 3. Complexity of (0,1)CVP in in nity norm is analyzed in Section 4. If the input vector elements are in f?1; 0; 1g then (0,1)-CVP has a (trivial) polynomial-time solution. In all other cases it is NP-hard. Unlike the previously published proofs for the general CVP (Kannan 1] used three dimensional matching whereas van Emde Boas 6] used partition), reductions in both sections use 3SAT problem or its variant NOT-ALL-EQUAL 3]. Both sections use the same method of reducing a propositional logic problem to a satis ability of inequality over integers, which in turn is reduced to the relevant minimization problem. This method might be useful in analyzing complexity of other minimization problems. The last section provides nal remarks about the techniques used in the presented proofs and about possible applications of the results.

2 Basic De nitionsThe set L(A)= fY 2<p: Y= AX; X 2 Z q g, where A is a p q matrix with elements in< and linearly independent columns, is called a lattice generated by the columns of A or, in short, a lattice based on matrix A 4]. In other words, a lattice L in<p is the set of all integer linear combinations of a set of linearly independent vectors (i.e. columns of A) in<p. The independent vectors are called a basis of the lattice. The dimension of the lattice is the number of basis vectors (the number of columns in A) that generate it. A distance between two vectors C= c1;:::; cm] and Y= y1;:::; ym] in the l-th norm is de ned as:

vm uX t jjC? Y jjl= u jci? yijll

i=1

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

3 In in nity norm the distance de nition simpli es to:

jjC? Y jj1= i=1;:::;m jci? yij maxThe closest vector problem, abbreviated here as CVP, is to nd the vector in a lattice that is closest to the given input vector C, i.e. to nd a vector Ymin 2 L(A) such that jjC? Yminjjl jjC? Y jjl for all vectors Y 2 L(A). The variant of CVP in which a lattice is based on a matrix with elements in f0; 1g is referred to here as (0,1)-CVP. Two NP-hard problems in propositional logic used in reductions below are 3SAT and its variant NOT-ALL-EQUAL 3]. Let U be a set of boolean variables, and CL be a collection of clauses over U such that each clause is a disjunction of exactly three literals. Each literal is either a variable x

2 U or the boolean negation x of such a variable. The 3SAT problem is to determine if there is a truth assignment for the variables in U such that each clause in CL has at least one true literal. The NOT-ALL-EQUAL problem is to establish whether there is a truth assignment for the variables in U which yields at least one pair of unequal literals in each clause in CL.

3 (0,1)-CVP Complexity in Finite NormsFor a nite norm l and a given integer constant r 6= 0, we reduce the NOT-ALL-EQUAL problem to the (0,1)-CVP. First, we replace each boolean variable in the original problem by a quadruplet of arithmetic variables to represent: the boolean variable itself, its boolean negation and the arithmetic negations of the rst two variables. Then, we de ne inequalities over these arithmetic variables such that a solution to the inequalities exists if and only if there is the truth assignment that satis es the original problem. Introduced inequalities must have a form suitable for a distance de nition that is expressed as a sum of l-th powers of absolute values of some linear combinations of the point coordinates. Moreover, the elements of sought matrix A are in f0; 1g and input vector elements ci are in f0; rg. Hence, coe cients of variables that appear inside each argument of absolute value have to be\+1" and a free term, if any, must be\?r". Even such limited form is su cient to duplicate a given value, say v, by using inequality jv+ xjl+ jx+ xjl 0 (its only solution is x= v=?x). Likewise, inequality jv+ x0 jl+ jv+ x1 jl+ jx2+ x0+ x1 jl 0 creates a double of v in x2, while inequality jv+ y0+ y1jl+ jy2+ y1jl+ jy2+ y0jl 0 has as solution y2= v=2 (but only if v is even). We want to represent boolean values True, False by arithmetic values h; h+ 1. The nice property of such representation is that sum of representation of any boolean value and its negation is a constant 2h+1 while di erence of them has constant absolute value 1. It is also important that for any pair of integers, say x; y, if x+ y? (2h+ 1)= 0 then min jx? yj= 1. If constant r in (0,1)-CVP is odd, it can be readily used as 2h+ 1, otherwise we need to\divide out" all factors of two from r. Finally, it is easy to observe that three boolean values compared pairwise yield three equalities, if all three are equal, and one equality, otherwise. This observation leads to a short inequality (cf. inequality (6)) whose satis ability is equivalent to the existence of the required truth assignment for NOT-ALL-EQUAL problem.

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

4

3 (0,1)-CVP COMPLEXITY IN FINITE NORMS

In summary, the NOT-ALL-EQUAL problem is reduced rst to a problem F, de ned below, expressed in terms of arithmetic inequalities. Then, this problem is reduced to (0,1)-CVP in the l-th norm and the given integer constant r 6= 0. Problem F Let vm uX u f (Y )= t jAi Y? cijll

where Y= y1; y2;:::; yn], Ai such that for a given constant c,

2 f0; 1gn

and ci 2 f0; r 6= 0g are given. Is there a vector Y

2 Z n

i=1

f (Y ) c

Lemma 1 Problem F is NP-complete. Proof It takes polynomial-time (in the problem size) to check whether f (Y ) c for the given

vector Y, thus the problem is in NP. To reduce NOT-ALL-EQUAL problem to problem F we de ne rst an integer variable with an odd value. Consider the given integer r of problem F . It can be represented as 2q (2h+ 1), i.e. q is the highest power of two that is a divisor of r. Consider the sequence of variables (0) (0) v1; v2;::: vi(j);:::, for i= 1; 2; 3 and j= 1;:::; q satisfying the following inequalities(0) (0) (0) (j= 0) t0= j? r+ v1 jl+ jv1+ v2 jl 0 ( ( ( ( ( ( ( (j> 0) tj= jv2j?1)+ v1j)+ v3j)jl+ jv1j)+ v2j)jl+ jv3j)+ v2j)jl

0

(1)

(0) (0) ( ( that can be satis ed only if all terms are zeros. Thus, v1=?v2= r and v1j)=?v2j)= ( ( ( v3j)=?v2j?1)=2, for j> 0. Hence, v2q)=?r=2q=?2h? 1. The above de nition requires at most 3blog2 rc+ 2 variables (they de ne columns of the array A from problem F ) and the same number of terms (that de ne rows of array A). Let's consider an instance of NOT-ALL-EQUAL problem with a set U= fx1;:::; xk g of k boolean variables and a collection CL= fcl1;:::; clpg of p clauses over U . For each boolean variable xj 2 U, we create a quadruplet yj; yj+k; uj; uj+k 2 Z of arithmetic variables. Each literal xj is represented by yj, whereas a literal xj (i.e. boolean negation of xj ) is represented by yj+k. Hence, each clause clj= ltj1 _ ltj2 _ ltj3 in CL has the corresponding triplet of arithmetic variables yj1; yj2; yj3. Consider inequality

s1=

q k 2k X jy+ u jl+ X jv(q)+ y+ y jl+ X t i i+k j i i 2 i=1 i=1 j=0

0

(2)

It is satis able (and becomes an equality) if and only if all terms yield zero, i.e. when yi=?ui and yi+ yi= 2h+ 1 for all i 2k (from now on yi will denote yi+k if i k, and yi?k otherwise). Inequality k X (3) s2= s1+ (s1+ jyi+ uijl ) ki=1

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

5 contains term s1 repeated k+ 1 times. Hence, its solution satis es yi=?ui; yi+ yi= 2h+ 1 and the following inequality also holds:

jyi+ uijl= jyi? yijl= j2(yi? h)? 1jl 1Clearly, inequality (3) is satis able and becomes an equality if and only if (81 i 2k: yi=?ui^ yi 2 fh; h+ 1g) (4) Finally, the truth assignment for U satis es the NOT-ALL-EQUAL instance1 if and only if the triplet of arithmetic variables corresponding to each clause clj 2 CL satis es (4) and the following inequality (which, if holds, becomes an equality) (5) jyj1+ uj2jl+ jyj2+ uj3jl+ jyj3+ uj1jl 1 The left hand side of inequality (5) is non-negative. For ui=?yi; yi= 2h+ 1? yi, it is at least equal to\1". Hence, it is clear that the following inequality:i=1 i=1 p p X s+ s+ X(jy+ u jl+ jy+ u jl+ jy+ u jl) p+ k i3 i2 i1 1 2 i1 i3 i2

(6)

can be satis ed if and only if there is a truth assignment solving the given NOT-ALL-EQUAL problem instance. Indeed, since term s1 is repeated p+ k+ 1 times on the left hand side of the inequality (6) then its

solution satis es (4), consequently the second term is no less than k and the third term no less than p. Hence, for properly selected matrix A=:::; Ai;:::] 2 f0; 1gn m, the following inequality can be satis ed if and only if there is a truth assignment solving the given NOT-ALL-EQUAL problem instance:m X jA Y? c jl p+ k i i i=1

(7)

(0) (0) ( where Y= v1; v2;::: v3q);:::; u1;:::; u2k; y1;:::; y2k] 2 Z n, ci 2 f0; rg, n 4k+ 3blog2 rc+ 2 and m 3(p+ k+ 1)(k+ blog2 rc+ 1)+ 2p? 1. Thus, for every instance of the NOT-ALL-EQUAL problem we can construct an instance of the problem F in polynomial time. Hence, problem F is NP-complete. 2 A simple observation that knowing the minimum of a function f (Y ) is su cient to decide whether the inequality f (Y ) c holds for a given c leads to the following:1 It is possible to use 3SAT problem in reduction, but then the corresponding inequality would involve four additional variables 1 4 for each each clause and would consists of eight terms:dj:::; dj

j 1+yj

dj 1

+

dj 2

j+j 2+l

yj

dj 1

+

dj 2

j+j 1+l

yj

uj 2

j+j 3+l

yj

dj 1

+

dj 2

j+j 3+l

yj

dj 1

+

dj 3

j+l j

X

=j 1;j 2;j 3

j+ 4jdj dj

l

2

Boolean variable

xj

is then equivalent to a predicate ( mod 2).yj

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

6

4 (0,1)-CVP COMPLEXITY IN INFINITY NORM

Corollary (0,1)-CVP in a nite norm l is NP-hard, i.e., the problem of nding a vector of integers X= x1; x2;:::; xn]T that minimizesm X jA X? c jl i i i=1

for given ci 2 f0; r 6= 0g and matrix A= A1;:::; Am] 2 f0; 1gn

m

is NP-hard.

4 (0,1)-CVP Complexity in In nity NormThe complexity of the (0,1)-CVP in in nity norm depends on the elements of the input vector. If all elements of the input vector are in f?1; 0; 1g then (0,1)-CVP has a polynomial-time solution. First step of this solution is to use a polynomial-time algorithm for linear equation integer feasibility problem 1] to nd the vector with a zero distance to the input vector or to show that such vector does not exist. In the latter case, the second step simply produces the zero vector as an answer. The zero vector is at distance\1" from the input vector and in in nity norm this is the smallest nonzero distance between the input vector and any vector in the lattice. For all other input vectors there is an integer r, jrj 2, such that elements of the input vector form the superset of f0; rg. The proof below covers a stronger case, when the input vector elements are exactly in f0; rg; jrj 2. In the proof we will use an analogue of problem F de ned as follows: Problem F: Let f (Y )= i=1;:::;m jAi Y? cij maxwhere Y= y1; y2;:::; yn], and Ai 2 f0; 1gn, ci 2 f0; rg, where jrj vector Y 2 Z n, such that for a given constant c,

2, are given. Is there a

f (Y ) cThe reduction of problem F to (0,1)-CVP in in nity norm is based on the same argument as the reduction of F to (0,1)-CVP in the l-th norm presented in the previous section. Thus, we will only

show how the 3SAT problem can be reduced to problem F . We can assume, without loss of generality, that r> 0. If this is not the case, the proof given below can be recast with signs of all integer variables reversed (i.e. with boolean value True represented by\1"and not, as below, by\?1"). Let k denote the number of boolean variables in the given instance of 3SAT problem and p be the number of its clauses. For each boolean variable xj 2 U, a pair yj; yj+k 2 Z of arithmetic variables is created. By introducing inequalities over these arithmetic variables, we will ensure that a solution to inequalities exists if and only if there is a truth assignment satisfying

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

7 the considered 3SAT problem instance. A solution to the inequalities produces required truth assignment by setting a boolean variable xj to predicate yj=?1. Conversely, the truth assignment yields the solution to inequalities by setting yj=?1, if xj is True and yj= 0 otherwise, and putting yj+k=?1? yj . Following the de nition of a distance in the in nity norm, left hand sides of introduced inequalities will consist of a max operator applied to absolute values of expressions. Each expression will contain a simple sum of variables and a constant\0" or\?r". The right hand side have to be an integer constant, the same for all introduced inequalities (\1" in our proof). It is easy to verify that any solution to inequality

s1= i=1;:::;kf(jyij; jyij; jyi+ yij)g 1 max

(8)

satis es yi 2 f?1; 0; 1g; yi+ yi 1, hence for any solution to the above inequality yi=?1 implies that yi>?1. Let vj(i), where j= 0; 1; 2; i= 0;:::; q and q= blog2 (r? 1)c be a sequence of auxiliary variables de ned as follows: (i= 0) maxj=0;1;2 jvj(0) j 1?1 (i> 0) maxj=0;1;2 jvj(i)+ Pim=0 v((jm) mod 2 j 1+1) (9)

It can be shown by induction that the above inequalities restrict feasible solutions to?2i vj(i) 2i. Let bi 's, where i= 0;:::; q, denote digits of the binary representation of r? 1. The following inequality: X v(i)j 1 max j? r+ (10) j j=0;2(0) (0) ( ( is satis able if and only if v0i)= v2i)= 2i, for i q, hence v0= v2= 1. It is easy to check that the 3SAT problem is satis able if and only if for each clause clj= ltj1 _ ltj2 _ ltj3 there is such assignment to the corresponding arithmetic variables yj1; yj2; yj3 that they satisfy (8) and their sum is negative, or, equivalently, that they make the following inequality hold: (0) (0) jv0+ v2+ yj+ yj+ yj j 11 2 3

fijb=1gi

(11)

Hence, the following inequality is satis ed if and only if the corresponding 3SAT problem is satis able: p (0) (0) max(s1; max jv0+ v2+ yj1+ yj2+ yj3 j) 1 i=1 Inequalities (9{11) can be rewritten in the matrix form as:(0) ( max jAi v0;:::; v3q); y1;:::; y2k]? cij 1 i

where each row Ai is created from terms of inequalities (9{ 11), hence contains only f0; 1g entires and there are only 3(k+ blog2(r? 1)c)+ p+ 5 of such rows. Thus, we can reduce the given 3SAT problem

instance to an instance of problem F in a polynomial time.

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

8

REFERENCES

5 ConclusionThe paper establishes complexity of the well-known closest vector problem in an arbitrary norm in a lattice generated by a (0,1)-matrix. This result can be used to decide complexity of minimization problems in graphs and networks when the CVP lattice is generated by the graph or network incidence matrix with elements in f0; 1g or f?1; 0; 1g. The authors used the presented result to establish complexity of the data alignment problem in SIMD architectures, an important compile-time optimization method for parallel processing 5]. Matrix A created during the presented reductions includes rows that are linearly dependent on others. The question then arises whether the complexity of CVP is in uenced by the introduction of dependent rows, i.e. whether CVP is harder for lattices that are not full-dimensional. The negative answer can be obtained by using the Hermite normal form 2] to reduce CVP in a lattice generated by an arbitrary matrix to the problem in a lattice de ned by a full dimensional matrix. 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 satis ability problem of an inequality over integers, which in turn is reduced to some minimization problem. The presented technique can also be applied to complexity analysis of the related shortest vector problem which is to nd such nonzero vector in the given lattice that is closest to the origin. Using reductions similar to those presented in this paper, it is easy to show that this problem is NP-hard in in nity norm even if the lattice generating matrix elements are restricted to the set f0; 1; rg, where jrj> 1. Similarly as for the corresponding (0,1)-CVP, the shortest vector problem in in nity norm has a (trivial) polynomial-time solution if the lattice generating matrix has all its elements in f?1; 0; 1g.

References1] R. Kannan,\Minkowski's Convex Body Theorem and Integer Programming," Math. Operations Res. Vol. 12, No. 3, August 1987, pp. 415-440 2] R. Kannan and A. Bachem,\Polynomial Time Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix", SIAM J. Comput. Vol. 8, 1979, pp. 499-507. 3] R. M. Karp,\Reducibility among Combinatorial Problems" in R. E. Miller and J. W. Thatcher (Eds.), Complexity of Computer Computations., Plenum Press, New York, 1972, pp. 85-103. 4] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John-Wiley and Sons, 1988. 5] B. Sinharoy and B. K. Szymanski,\Data Alignment in SIMD Machines," submitted to IEEE Trans. on Parallel and Distributed Systems, also Technical Report 91-10, Department of Computer Science, RPI, May, 1991.

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

REFERENCES

9

6] P. van Emde Boas, Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice, Rep. 81-04, Math. Inst. Univ. Amsterdam

, 1981.

本文来源：https://www.bwwdw.com/article/br51.html