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 in {0, 1}n is at a distance at most r from some code word. Our main result 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 such 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 Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem. A central tool in our reduction is a metrical characterization of the set of doubled vectors of length 2n: {υ = (υ1υ2 • • • υ2n) | ∀i : υ2i = υ2i -1}. We show that there is a set Υ ⊂ {0, 1}2n such that for every υ ∈ {0, 1}2n: υ is doubled iff Υ is contained in the radius-n ball centered at υ moreover, Υ can be constructed in time polynomial in n.