A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the complexity of the identification problem in Hamming spaces
Tekijät: Honkala I, Lobstein A
Kustantaja: SPRINGER-VERLAG
Julkaisuvuosi: 2002
Journal: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 38
Numero: 11-12
Aloitussivu: 839
Lopetussivu: 845
Sivujen määrä: 7
ISSN: 0001-5903
DOI: https://doi.org/10.1107/s00236-002-0093-4
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali