ON COVERING PROBLEMS OF CODES

Let C be a binary code of length n (i.e., a subset of {0, 1}(n)). The Covering Radius of C is the smallest integer r such that each vector i n {0, 1}(n) is at a distance at most r from some code word. Our main r esult is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete. This result is established as follows. The Radius of a binary code C is the smallest integer r su ch that C is contained in a radius-r ball of the Hamming metric space [{0, 1}(n), d]. It is known [K] that the problems of computing the Rad ius and the Covering Radius are equivalent. We show that the 3SAT prob lem is polynomially reducible to the Radius decision problem. A centra l tool in our reduction is a metrical characterization of the set of d oubled vectors of length 2n: {v = (v(1)v(2) ... v(2n)) / For All i: v( 2i) = v(2i-1)}. We show that there is a set Y subset of {0, 1}(2n) suc h that for every v is an element of {0, 1}(2n): v is doubled iff Y is contained in the radius-n ball centered at v; moreover, Y can be const ructed in time polynomial in n.