A1 Refereed original research article in a scientific journal
On the complexity of the identification problem in Hamming spaces
Authors: Honkala I, Lobstein A
Publisher: SPRINGER-VERLAG
Publication year: 2002
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume: 38
Issue: 11-12
First page : 839
Last page: 845
Number of pages: 7
ISSN: 0001-5903
DOI: https://doi.org/10.1107/s00236-002-0093-4
Abstract
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.
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.
UTU Research Portal