On covering problems of codes View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-04

AUTHORS

M. Frances, A. Litman

ABSTRACT

LetC be a binary code of lengthn (i.e., a subset of {0, 1}n). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}n is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete.This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1}n,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem.A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v1v2 …v2n) | ∀i:v2i=v2i−1}. We show that there is a setY ⊂ {0, 1}2n such that for everyv ε {0, 1}2n:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn. More... »

PAGES

113-119

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02679443

DOI

http://dx.doi.org/10.1007/bf02679443

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1037262625


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Technion, 32000, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, 32000, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Frances", 
        "givenName": "M.", 
        "id": "sg:person.016216656215.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016216656215.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Technion, 32000, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, 32000, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Litman", 
        "givenName": "A.", 
        "id": "sg:person.014327203705.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014327203705.47"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997-04", 
    "datePublishedReg": "1997-04-01", 
    "description": "LetC be a binary code of lengthn (i.e., a subset of {0, 1}n). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}n is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete.This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space \u3008{0, 1}n,d\u3009. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem.A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v1v2 \u2026v2n) | \u2200i:v2i=v2i\u22121}. We show that there is a setY \u2282 {0, 1}2n such that for everyv \u03b5 {0, 1}2n:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02679443", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "30"
      }
    ], 
    "keywords": [
      "binary codes", 
      "main results", 
      "reduction", 
      "ATV", 
      "problem of code", 
      "code", 
      "vector", 
      "code words", 
      "results", 
      "decision problem", 
      "covering radius", 
      "arbitrary binary code", 
      "theradius", 
      "such thatC", 
      "metric spaces", 
      "time polynomial inn", 
      "polynomial inn", 
      "LetC", 
      "lengthn", 
      "integerr", 
      "problem", 
      "NP", 
      "codec", 
      "thatC", 
      "ball", 
      "space", 
      "central tool", 
      "tool", 
      "characterization", 
      "set", 
      "length 2n", 
      "V2I", 
      "radius", 
      "distance", 
      "words", 
      "InN", 
      "TheCovering Radius", 
      "smallest integerr", 
      "mostr", 
      "binary codeC", 
      "smallest integerr such thatC", 
      "integerr such thatC", 
      "Hamming metric space", 
      "Radius decision problem", 
      "metrical characterization", 
      "setY", 
      "everyv \u03b5", 
      "iffY"
    ], 
    "name": "On covering problems of codes", 
    "pagination": "113-119", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037262625"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02679443"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02679443", 
      "https://app.dimensions.ai/details/publication/pub.1037262625"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_263.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02679443"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02679443'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02679443'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02679443'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02679443'


 

This table displays all metadata directly associated to this object as RDF triples.

113 TRIPLES      21 PREDICATES      74 URIs      66 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02679443 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N38801ca32e414c32a1db8b0b0b6fb4df
4 schema:datePublished 1997-04
5 schema:datePublishedReg 1997-04-01
6 schema:description LetC be a binary code of lengthn (i.e., a subset of {0, 1}n). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}n is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete.This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1}n,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem.A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v1v2 …v2n) | ∀i:v2i=v2i−1}. We show that there is a setY ⊂ {0, 1}2n such that for everyv ε {0, 1}2n:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N3970ef9f4c5340fbbb79a970870b3ea2
11 Nff457c37308e4662b06dec9abc0e525d
12 sg:journal.1052098
13 schema:keywords ATV
14 Hamming metric space
15 InN
16 LetC
17 NP
18 Radius decision problem
19 TheCovering Radius
20 V2I
21 arbitrary binary code
22 ball
23 binary codeC
24 binary codes
25 central tool
26 characterization
27 code
28 code words
29 codec
30 covering radius
31 decision problem
32 distance
33 everyv ε
34 iffY
35 integerr
36 integerr such thatC
37 length 2n
38 lengthn
39 main results
40 metric spaces
41 metrical characterization
42 mostr
43 polynomial inn
44 problem
45 problem of code
46 radius
47 reduction
48 results
49 set
50 setY
51 smallest integerr
52 smallest integerr such thatC
53 space
54 such thatC
55 thatC
56 theradius
57 time polynomial inn
58 tool
59 vector
60 words
61 schema:name On covering problems of codes
62 schema:pagination 113-119
63 schema:productId N56bdff8f9410441189b31eff3f18a954
64 Nfdeaba26df9b4e53af2012bdb2e99432
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037262625
66 https://doi.org/10.1007/bf02679443
67 schema:sdDatePublished 2021-11-01T18:00
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N03b75e1650f94526b2d853ca84e5a287
70 schema:url https://doi.org/10.1007/bf02679443
71 sgo:license sg:explorer/license/
72 sgo:sdDataset articles
73 rdf:type schema:ScholarlyArticle
74 N03b75e1650f94526b2d853ca84e5a287 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N2ba222ddbccc4fffa21068aead6d0358 rdf:first sg:person.014327203705.47
77 rdf:rest rdf:nil
78 N38801ca32e414c32a1db8b0b0b6fb4df rdf:first sg:person.016216656215.39
79 rdf:rest N2ba222ddbccc4fffa21068aead6d0358
80 N3970ef9f4c5340fbbb79a970870b3ea2 schema:volumeNumber 30
81 rdf:type schema:PublicationVolume
82 N56bdff8f9410441189b31eff3f18a954 schema:name doi
83 schema:value 10.1007/bf02679443
84 rdf:type schema:PropertyValue
85 Nfdeaba26df9b4e53af2012bdb2e99432 schema:name dimensions_id
86 schema:value pub.1037262625
87 rdf:type schema:PropertyValue
88 Nff457c37308e4662b06dec9abc0e525d schema:issueNumber 2
89 rdf:type schema:PublicationIssue
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:journal.1052098 schema:issn 1432-4350
97 1433-0490
98 schema:name Theory of Computing Systems
99 schema:publisher Springer Nature
100 rdf:type schema:Periodical
101 sg:person.014327203705.47 schema:affiliation grid-institutes:grid.6451.6
102 schema:familyName Litman
103 schema:givenName A.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014327203705.47
105 rdf:type schema:Person
106 sg:person.016216656215.39 schema:affiliation grid-institutes:grid.6451.6
107 schema:familyName Frances
108 schema:givenName M.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016216656215.39
110 rdf:type schema:Person
111 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, 32000, Haifa, Israel
112 schema:name Department of Computer Science, Technion, 32000, Haifa, Israel
113 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...