Approximating the number of error locations within a constant ratio is N P-complete

Jacques Stern

Laboratoire d’Informatique, Ecole Normale Supérieure

Abstract. Using recent results from complexity theory, we show that, under the assumption P ≠ N P, no polynomial time algorithm can compute an upper bound for the number of error locations of a word y with respect to a code C, which is guaranteed to be within a constant ratio of the true (Hamming) distance of y to C. Thus the barrier which prevents the design of very general decoding algorithms that would apply to unstructured codes is even more solid than was thought before. We also give an analogous result for integer lattices.

1 Introduction

The notion of N P-completeness is by now classical and has produced in the last twenty years an elegant body of results(see [5]). Recently, progress in complexity theory using the notion of interactive proofs has produced various results, culminating in a paper by Arora, Lund, Motwani, Sudan and Szegedy ([1]). These authors constructed proofs of membership for any N P language that can be checked probabilistically by querying only a constant number of bits in the proof.

This new achievement has startling consequences for the approximation of N P-complete problems. For example, it implies that, unless P = N P, there exists a constant ϵ such that no polynomial time algorithm can approximate within (1 + ϵ) the maximal number of 3-clauses of a 3-SAT instance which can be simultaneously satisfiable: we say that the underlying optimization problem (called MAX3SAT) does not have a polynomial approximation scheme. Actually, MAX3SAT is a member of a larger family of problems, called MAXSNP - complete and whose definition is due to Papadimitriou and Yannakakis ( [7]). In [1], it is shown that, unless P = N P, none of these problems can have an approximation scheme. Other results rule out the possibility of having good approximation algorithms for specific problems: for example, the maximal size of a clique in a graph with n vertices cannot be approximated within n^{ϵ}, for some constant ϵ.

The present paper investigates an optimization problem that appears in the theory of error-correcting codes, namely the computation of the (Hamming) distance of a vector y from the nearest codeword of a given code (also called the number of error locations of y). Shortly after the appearence of the notion of N P-completeness, the following decision problem was shown to be N P-complete (see [3]):

instance: a linear binary code C of length n, a word y of length n, an integer k. question: Is there a codeword x of C such that

d(x, y) ≤ k

where d denotes the Hamming distance.

Thus, unless P = N P, no polynomial time algorithm can compute the value inf{d(x, y) : x ∈ C}. We now discuss the possibility of obtaining an approximation of this value. Rather than giving general definitions, for which we refer to [7], we restrict ourselves to the specific problem under dicussion:

Definition: Let α, β be real numbers. An algorithm approximates the number of error locations with performance (α, β) if, when given as input a linear binary error-correcting code C of length n and a word y, it computes an integer t such that

α(inf{d(x, y) : x ∈ C}) ≤ t ≤ β(inf{d(x, y) : x ∈ C})

Remarks.

1. The use of real numbers in the above is quite artificial and, by weakening the performances of an algorithm, we can restrict ourselves to rational numbers.

2. If an algorithm approximates the number of error locations with performance (α, β), then by outputing tα^{−1}, we get another algorithm approximating the number of error locations with performance (1, α^{−1}β). Thus we will restrict our attention to performances of type (1, ρ), and write performance ρ to simplify notation.

Our main result reads as follows.

Theorem 1 Assume P ≠ N P.Then, given any constants α, β, there is no polynomial time algorithm which approximates the number of error locations with performance (α, β).

As oberved above, it will be enough to rule out approximation algorithms with performance ρ. Our starting point will be the following result which we quote from reference [1]

Theorem 2 Let L be a language in N P. There exists a polynomial time algorithm A and a rational constant γ, 0 < γ < 1 such that, given an input x, algorithm A produces an instance Φ_{x} of 3-SAT consisting of polynomially many clauses satisfying the following

1. if x ∈ L then Φ_{x} is satisfiable.

2. if x ∉ L, then at most a fraction 1 − γ of the clauses in Φ_{x} are satisfiable simultaneously.

The proof of theorem 1 will be based on a polynomial time reduction from MAX3SAT: taking as an input a set of clauses Φ, this reduction outputs the generating matrix of a binary code C_{Φ} and an integer K_{Φ} such that, denoting by u the word whose bits are all one, the following holds:

1. if Φ_{x} is satisfiable, then the distance of u to C_{Φ} is K_{Φ}.

2. if at most a fraction 1 − γ of the clauses in Φ_{x} are satisfiable simultaneously, then the distance of u to C_{Φ} is at least λK_{Φ}, where λ is a constant depending only on γ.

Such a reduction clearly rules out the existence of a polynomial time algorithm approximating the number of error locations with performance (1, λ − ϵ), for any fix ϵ such that λ − ϵ > 0: by combining the reduction of theorem 2, the reduction just defined and finally applying such a polynomial algorithm, we could solve any problem in N P in polynomial time.

Thus if we can build an infinite sequence of reductions whose corresponding constants form a sequence λ_{q} such that lim_{q→∞} λ_{q}(γ) = ∞, our result will follow.

2 A simplified result.

We first prove a weaker version of theorem 1

Theorem 3 Assume P ≠ N P. Then, there exists a constant ρ such that no polynomial time algorithm can approximate the number of error locations with performance ρ.

In other terms, there is no polynomial time approximation scheme for the number of error locations. As was pointed out by one of the referees, this result was somehow implicit in the literature: a paper of Bruck and Naor ( [4]) mentions that the set of cuts in a graph form a linear space (when viewed as vectors of length the number of edges representing the characteristic function of the set of edges crossing the cut). This yields a polynomial time reduction of the problem MAXCUT to the maximum likelihood decoding problem. Furthermore, this reduction preserves aprroximations. Hence, we can apply the results from [1].

We give a different reduction which uses, as a building block, of the (7, 3, 4) simplex code whose generating matrix is

( \begin{matrix}0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} )

As is well known, all non-zero codewords of this code have weight 4.

We start from an instance of 3-SAT Φ consisting of m clauses c_{1}, ⋯, c_{m}, each having three literals taken from v_{1}, ⋯, v_{r}; \overline{v_{1}} ⋯ \overline{v_{r}}. The generating matrix of the code C_{Φ} has the following form

M = ( B_{1} ⋯ B_{m}  A_{1}  ⋯  A_{r}  )

Matrices A_{i} and B_{j} have 2r rows, which we will number by the literals v_{1}, \overline{v_{1}}, ⋯, v_{r}, \overline{v_{r}}.

Each of the matrices A_{i} corresponds to one propositional variable v_{i} and has 8m columns. All its rows are zero except for the two rows corresponding to v_{i}, \overline{v_{i}} which consist of ones.

Each of the matrices B_{j} corresponds to one clause of Φ say c_{j} and has seven columns. All its rows are zero except the three rows labelled by the three literals which appear in c_{j}. These three rows are filled in such a way that by discarding the zero rows one obtains a copy of the generating matrix of the simplex code described above.

Now, we observe that M generates a (7m + 8mn, 2r) code. Any codeword is produced by a linear combination of the rows, where the coefficients are obtained by assigning values τ(v_{i}), τ(\overline{v_{i}}) to the literals. We denote by w(τ) the codeword built from τ. We say that an assignment is legal if τ(v_{i}) = 1−τ(\overline{v_{i}}) and we make the following easy remarks (recall that u is the all-ones word). Remarks

1. For any codeword w(τ) built from an illegal assignment τ the Hamming weight of u ⊕ w(τ) is at least 8m.

2. For a codeword w(τ) built from a legal assignment satisfying the set of clauses Φ, the Hamming weight of u ⊕ w(τ) is exactly 3m.

3. For a codeword w(τ) built from a legal assignment satisfying at most a proportion (1 − γ) of the set of clauses Φ, the Hamming weight of u ⊕ w(τ) is at least (3 + 4γ)m and at most 7m.

The proofs of the first remark is easy: an illegal τ uses the two non-zero rows of one of the matrices A_{i} and therefore cannot cancel the 8m corresponding ones in u. As for other remarks, they follow from the fact that legal τ’s are proper truth assignments and cancel 4 ones of u at positions corresponding to a matrix B_{j}, where τ satisfies c_{j} and do not cancel anything at other positions because the non-zero rows of B_{j} are not hit in this case.

From the remarks, it follows that we have built a reduction of the kind described at the end of section 1 with λ(γ) = \frac{3+4γ}{3} . As observed in section 1, this rules out approximation algorithms with performance 1 + \frac{4}{3}γ and proves theorem 3.

3 Proof of the main theorem.

In order to prove theorem 1, we will build a sequence of reductions similar to the one that was described at the end of the previous section but with λ(γ) being replaced by λ_{q}(γ) = (1 + \frac{4}{3}γ)^{q}. As mentioned in section 1, this yields the result.

Actually, our construction is recursive and we will simply explain how to go from the case q = 1 (covered by the previous section) to q = 2. The general inductive step is similar and will be only sketched very briefly. We start from the generating matrix M of the code constructed in section 2. M is a (2r, p) matrix with p = 7m+8mr, following previous notations. We let M̃ be the (2r, p^{2}) matrix obtained from M by replacing each one by a block of p ones and each zero by a block of p zeros (this is a concatenation construction). The generating matrix of the code C_{Φ}^{2} has the form

M_{2} = (  M̃ ; M′  )

where M′ is built as shown on the diagram displayed on the next page. In this diagram, each matrix P_{k} has 2r rows and p columns and is a copy of M. Thus, we have built a matrix M_{2} with 2r(p + 1) rows and p^{2} columns through a construction that can clearly be achieved in polynomial time.

We now make the following remarks where u stands for the all-ones word of suitable length. Remarks

1. If Φ (the given set of clauses) is satisfiable, then there is a codeword w built as a linear combination of the first 2n rows of M_{2} such that u⊕w has exactly 3m non-zero blocks. In each of these blocks, ones can be further cancelled by using the corresponding matrix P_{k} so as to leave exactly 3m ones. Thus, the distance of u to C_{Φ}^{2} is exactly (3m)^{2}.

2. If at most a proportion (1 − γ) of the set of clauses Φ can be satisfied simultaneously, then any codeword w built as a linear combination of the first 2n rows of M_{2} will leave at least (3 + 4γ)m non-zero blocks in u ⊕ w. In each of these blocks, use of the corresponding matrix will cancel more ones but will leave at least (3 + 4γ)m ones. Therefore the distance of u to C_{Φ}^{2} is at least ((3 + 4γ)m)^{2}.

M′ = (  \begin{matrix}P_{1} & ⋯ & 0 & 0 \\ 0 & P_{2} & ⋯ & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & ⋯ & P_{p} \end{matrix}  )

Thus, as announced, we have built a reduction with λ_{2}(γ) = (1 + \frac{4}{3}γ)^{2}. The same construction can be repeated so as to get λ_{q}(γ) = (1 + \frac{4}{3}γ)^{q}. The construction involves replacing the generating matrix M_{q} obtained at step q by the matrix M̃_{q} obtained from M_{q} by replacing each one by a block of p ones and each zero by a block of p zeros. The generating matrix of the code C_{Φ}^{q+1} is constructed by adding below M̃_{q} a diagonal matrix, each element of the diagonal being a copy of the initial matrix M, defined in section 2. This proves theorem 1.

4 Approximating the closest lattice vector.

A lattice is an additive subgroup of Z^{n}. Lattices have received a lot of attention recently because of their use in algorithmic and cryptographic problems. From this point of view, the main achievement is the celebrated LLL algorithm (see [6]), which produces in polynomial time a so-called reduced basis. Using such a basis, it is possible to approximate the length of the shortest non-zero vector of a lattice with performance 2^{n−1}, where n is the dimension of the lattice (the reader will easily supply a definition of performance modelled after those in section 1). It is also possible to approximate the distance of a given point to the closest lattice point but the performance is worse (see [2]).

It turns out that a lattice can be attached to any linear binary code C of length n by letting

L(C) = {x ∈ Z^{n} : x mod 2 ∈ C}

Now, it is easily seen that the distance of the all-ones vector u to L(C) is precisely the square root of the (Hamming) distance of u to L. From this, we get the following:

Theorem 4 Assume P ≠ N P.Then, there is no polynomial time algorithm which, given a lattice L and a vector y approximates the distance of y to the closest point of L within a constant ratio.

Acknowledgements. The author wishes to thank Adi Shamir for drawing his attention to reference [1], for going through this paper with him and for discussions on the present work. The author is also grateful to the anonymous referees for their positive suggestions.

References

1. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and intractability of approximation problems. Proc. 31st IEEE Symp. on Foundations of Computer Science (1992), to appear.

2. L. Babai. On Lovàsz lattice reduction and the nearest point problem, Proc STACS 85, Lecture Notes in Computer Science 182, Springer, Berlin, 13-20.

3. E. R. Berlekamp, R. J. Mc Eliece and H. C. A. Van Tilborg. On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, (1978) 384-386.

4. J. Bruck and M. Naor. The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, (1990), 381-385.

5. M. R. Garey, D. S. Johnson. Computers and Intractability: a Guide to the Theory of NP-completeness, Freeman, San Francisco (1979).

6. A. K. Lenstra, H. W. Lenstra and L. Lovàsz. Factoring polynomials with rational coefficients. Math. Annalen 261 (1982) 515-534.

7. C. H. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. J. Comp. Syst. Sc. 43 (1990), 425-440.

This article was processed using the LaTEX macro package with LLNCS style