Name
Abstract | ||
|---|---|---|
LetC be a binary code of lengthn (i.e., a subset of {0, 1}
n
). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}
n
is at a distance at mostr 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. TheRadius of a binary codeC is the smallest integerr such thatC 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 ofdoubled vectors of length 2n: {v=(v
1
v
2 …v
2n
) | ∀i:v
2i
=v
2i−1}. We show that there is a setY ⊂ {0, 1}2n
such that for everyv ε {0, 1}2n
:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/BF02679443 | Theory Comput. Syst. |
Keywords | Field | DocType |
Linear Code,Covering Problem,Code Word,Covering Radius,Minimum Radius | Discrete mathematics,Decision problem,Combinatorics,Covering code,Binary code,Code word,Linear code,Mathematics,Closest string,Covering problems | Journal |
Volume | Issue | ISSN |
30 | 2 | 1432-4350 |
Citations | PageRank | References |
80 | 4.60 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moti Frances | 1 | 84 | 5.20 |
| Ami Litman | 2 | 240 | 49.78 |