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 N4f49e9b9f6614a2399a1620fe4cbe4d0
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 N3500bd9c371e4eb8b56a903f07ae5297
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N24a4593d3c774a3e936264fca56665f4
12 schema:name Reducibility among Combinatorial Problems
13 schema:pagination 85-103
14 schema:productId N19d4a6be43054d6aaef2933dabdaf3b2
15 N5ba4ddc5112d4c76aa3f6922faab5b6f
16 Nf8b2415c7bed41ca975070b69bf33348
17 schema:publisher N4ea501af0a564248a1124045e555d494
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 N384001505055468d8ad6fc061e1485e1
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 N19d4a6be43054d6aaef2933dabdaf3b2 schema:name dimensions_id
28 schema:value pub.1007977430
29 rdf:type schema:PropertyValue
30 N24a4593d3c774a3e936264fca56665f4 schema:isbn 978-1-4684-2001-2
31 978-1-4684-2003-6
32 schema:name Complexity of Computer Computations
33 rdf:type schema:Book
34 N3500bd9c371e4eb8b56a903f07ae5297 rdf:first Nf839b78ee92d4f2399286d528b0fabf0
35 rdf:rest N5b41875468dc4db5a6eb89c35ce42205
36 N384001505055468d8ad6fc061e1485e1 schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 N4ea501af0a564248a1124045e555d494 schema:location Boston, MA
39 schema:name Springer US
40 rdf:type schema:Organisation
41 N4f49e9b9f6614a2399a1620fe4cbe4d0 rdf:first Nf1fd8673ddde4fb1a5fd850ca0fbe527
42 rdf:rest rdf:nil
43 N5b41875468dc4db5a6eb89c35ce42205 rdf:first N7f5dcab609c84d73bf70cda773895e3a
44 rdf:rest Nad0b4baaa8354251acee11581776c048
45 N5ba4ddc5112d4c76aa3f6922faab5b6f schema:name readcube_id
46 schema:value 2600fbc8aaac025c6b86b351713e5b2b3df653787935a52e0f860632b63b1e18
47 rdf:type schema:PropertyValue
48 N7f5dcab609c84d73bf70cda773895e3a schema:familyName Thatcher
49 schema:givenName James W.
50 rdf:type schema:Person
51 Na2e855d7455a40c6ab9a0abf099eed56 schema:familyName Bohlinger
52 schema:givenName Jean D.
53 rdf:type schema:Person
54 Nad0b4baaa8354251acee11581776c048 rdf:first Na2e855d7455a40c6ab9a0abf099eed56
55 rdf:rest rdf:nil
56 Nf1fd8673ddde4fb1a5fd850ca0fbe527 schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
57 schema:familyName Karp
58 schema:givenName Richard M.
59 rdf:type schema:Person
60 Nf839b78ee92d4f2399286d528b0fabf0 schema:familyName Miller
61 schema:givenName Raymond E.
62 rdf:type schema:Person
63 Nf8b2415c7bed41ca975070b69bf33348 schema:name doi
64 schema:value 10.1007/978-1-4684-2001-2_9
65 rdf:type schema:PropertyValue
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)


...