Reducibility among Combinatorial Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1972

AUTHORS

Richard M. Karp

ABSTRACT

A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does. More... »

PAGES

85-103

Book

TITLE

Complexity of Computer Computations

ISBN

978-1-4684-2003-6
978-1-4684-2001-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4684-2001-2_9

DOI

http://dx.doi.org/10.1007/978-1-4684-2001-2_9

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley", 
          "id": "https://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karp", 
        "givenName": "Richard M.", 
        "type": "Person"
      }
    ], 
    "datePublished": "1972", 
    "datePublishedReg": "1972-01-01", 
    "description": "A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.", 
    "editor": [
      {
        "familyName": "Miller", 
        "givenName": "Raymond E.", 
        "type": "Person"
      }, 
      {
        "familyName": "Thatcher", 
        "givenName": "James W.", 
        "type": "Person"
      }, 
      {
        "familyName": "Bohlinger", 
        "givenName": "Jean D.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-1-4684-2003-6", 
        "978-1-4684-2001-2"
      ], 
      "name": "Complexity of Computer Computations", 
      "type": "Book"
    }, 
    "name": "Reducibility among Combinatorial Problems", 
    "pagination": "85-103", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4684-2001-2_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2600fbc8aaac025c6b86b351713e5b2b3df653787935a52e0f860632b63b1e18"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007977430"
        ]
      }
    ], 
    "publisher": {
      "location": "Boston, MA", 
      "name": "Springer US", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4684-2001-2_9", 
      "https://app.dimensions.ai/details/publication/pub.1007977430"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T20:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8690_00000013.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-1-4684-2001-2_9"
  }
]
 

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/978-1-4684-2001-2_9'

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/978-1-4684-2001-2_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4684-2001-2_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4684-2001-2_9'


 

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

74 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4684-2001-2_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N125ffb8476244b34a4fb3902d9e28848
4 schema:datePublished 1972
5 schema:datePublishedReg 1972-01-01
6 schema:description A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.
7 schema:editor Naebb5dff09d3483db9d18e06c3940f7c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb9f0eef61248489ba67e1572cf5814c4
12 schema:name Reducibility among Combinatorial Problems
13 schema:pagination 85-103
14 schema:productId N122ae22e659e484e87f1a858825722b6
15 N25a995e831cf41388d61b5125a921683
16 N65c40a327a54422197ecbc26598c02ca
17 schema:publisher Na0c0f47b29ae4e42a1fbbd731d4d2e2a
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
19 https://doi.org/10.1007/978-1-4684-2001-2_9
20 schema:sdDatePublished 2019-04-15T20:47
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N304d9bd3124a40e2bc8aa8b38bfe765d
23 schema:url http://link.springer.com/10.1007/978-1-4684-2001-2_9
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N122ae22e659e484e87f1a858825722b6 schema:name dimensions_id
28 schema:value pub.1007977430
29 rdf:type schema:PropertyValue
30 N125ffb8476244b34a4fb3902d9e28848 rdf:first N19078671073247868aaa3dada52741ca
31 rdf:rest rdf:nil
32 N19078671073247868aaa3dada52741ca schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
33 schema:familyName Karp
34 schema:givenName Richard M.
35 rdf:type schema:Person
36 N25a995e831cf41388d61b5125a921683 schema:name readcube_id
37 schema:value 2600fbc8aaac025c6b86b351713e5b2b3df653787935a52e0f860632b63b1e18
38 rdf:type schema:PropertyValue
39 N304d9bd3124a40e2bc8aa8b38bfe765d schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N65c40a327a54422197ecbc26598c02ca schema:name doi
42 schema:value 10.1007/978-1-4684-2001-2_9
43 rdf:type schema:PropertyValue
44 N878950fe940549f8b4e2c1b477b8f0a8 schema:familyName Bohlinger
45 schema:givenName Jean D.
46 rdf:type schema:Person
47 Na0c0f47b29ae4e42a1fbbd731d4d2e2a schema:location Boston, MA
48 schema:name Springer US
49 rdf:type schema:Organisation
50 Nae3886f4031b421ea16b7766c73bedc5 rdf:first Nea7c004b5e8f40ff8554b1aa40976260
51 rdf:rest Nb1f5cc71ff9b402aacfbae4a62e2f82b
52 Naebb5dff09d3483db9d18e06c3940f7c rdf:first Nb9a5d0504e9c4d6c831343b4b2899c20
53 rdf:rest Nae3886f4031b421ea16b7766c73bedc5
54 Nb1f5cc71ff9b402aacfbae4a62e2f82b rdf:first N878950fe940549f8b4e2c1b477b8f0a8
55 rdf:rest rdf:nil
56 Nb9a5d0504e9c4d6c831343b4b2899c20 schema:familyName Miller
57 schema:givenName Raymond E.
58 rdf:type schema:Person
59 Nb9f0eef61248489ba67e1572cf5814c4 schema:isbn 978-1-4684-2001-2
60 978-1-4684-2003-6
61 schema:name Complexity of Computer Computations
62 rdf:type schema:Book
63 Nea7c004b5e8f40ff8554b1aa40976260 schema:familyName Thatcher
64 schema:givenName James W.
65 rdf:type schema:Person
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
70 schema:name Computation Theory and Mathematics
71 rdf:type schema:DefinedTerm
72 https://www.grid.ac/institutes/grid.47840.3f schema:alternateName University of California, Berkeley
73 schema:name University of California, Berkeley, USA
74 rdf:type schema:Organization
 




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


...