A1 Journal article – refereed

On the complexity of the identification problem in Hamming spaces

List of 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 number: 38

Issue number: 11-12

Number of pages: 7

ISSN: 0001-5903

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.