A1 Journal article – refereed
On the complexity of the identification problem in Hamming spaces

List of Authors: Honkala I, Lobstein A
Publication year: 2002
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume number: 38
Issue number: 11-12
Number of pages: 7
ISSN: 0001-5903

A binary code C subset of or equal to {0, 1}(n) is called w-identifying if the sets B-w(x) boolean AND C for x is an element of x {0, 1}(n) are all nonempty and no two are the same. Here B-w(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.

Internal Authors/Editors

Research Areas

Last updated on 2019-20-07 at 04:26