On the Complexity of the Identification Problem in Hamming Spaces
Acta Informatica, Vol. 38, pp. 839-845, 2002.
Iiro HONKALA
Department of Mathematics
University of Turku
20014 Turku, Finland
e-mail: honkala@utu.fi
&
Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
e-mail: lobstein@infres.enst.fr
Abstract. A binary code C included in {0,1}n is called w-identifying if for all x in {0,1}n, the sets Bw(x) $\cap$ C are all nonempty and no two are the same. Here Bw(x) denotes the set of all vectors in {0,1}n within Hamming distance w from x. We show that the problem of deciding whether or not a given code C is w-identifying is co-NP-complete.