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 N5676c9e5a481469083ff700cdf3ac2d4
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 N052f2bd90ca2429e89462c06110bf789
11 Ne45020a140754f249e95625902add7d3
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 N247db6ed3ae641e28cb0d1ce6747b772
64 N8333f609673e449faac39c8f5ec44798
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 N08d78bbe51cb44fbab2680a4ca3a4e89
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 N052f2bd90ca2429e89462c06110bf789 schema:issueNumber 2
75 rdf:type schema:PublicationIssue
76 N081ad63052804cd3bf70e7b1a0939331 rdf:first sg:person.014327203705.47
77 rdf:rest rdf:nil
78 N08d78bbe51cb44fbab2680a4ca3a4e89 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N247db6ed3ae641e28cb0d1ce6747b772 schema:name doi
81 schema:value 10.1007/bf02679443
82 rdf:type schema:PropertyValue
83 N5676c9e5a481469083ff700cdf3ac2d4 rdf:first sg:person.016216656215.39
84 rdf:rest N081ad63052804cd3bf70e7b1a0939331
85 N8333f609673e449faac39c8f5ec44798 schema:name dimensions_id
86 schema:value pub.1037262625
87 rdf:type schema:PropertyValue
88 Ne45020a140754f249e95625902add7d3 schema:volumeNumber 30
89 rdf:type schema:PublicationVolume
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)


...