On the complexity of the identification problem in Hamming spaces



: Honkala I, Lobstein A

Publisher: SPRINGER-VERLAG

: 2002

: Acta Informatica

: ACTA INFORMATICA

: ACTA INFORM

: 38

: 11-12

: 839

: 845

: 7

: 0001-5903

DOI: https://doi.org/10.1107/s00236-002-0093-4


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.



Last updated on 2024-26-11 at 14:58