TFNP: An Update View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-04-14

AUTHORS

Paul W. Goldberg , Christos H. Papadimitriou

ABSTRACT

The class TFNP was introduced a quarter of a century ago to capture problems in NP that have a witness for all inputs. A decade ago, this line of research culminated in the proof that the Nash equilibrium problem is complete for the subclass PPAD. Here we review some interesting developments since. More... »

PAGES

3-9

Book

TITLE

Algorithms and Complexity

ISBN

978-3-319-57585-8
978-3-319-57586-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-57586-5_1

DOI

http://dx.doi.org/10.1007/978-3-319-57586-5_1

DIMENSIONS

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


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": "University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goldberg", 
        "givenName": "Paul W.", 
        "id": "sg:person.011515430057.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011515430057.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California at Berkeley, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California at Berkeley, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-04-14", 
    "datePublishedReg": "2017-04-14", 
    "description": "The class TFNP was introduced a quarter of a century ago to capture problems in NP that have a witness for all inputs. A decade ago, this line of research culminated in the proof that the Nash equilibrium problem is complete for the subclass PPAD. Here we review some interesting developments since.", 
    "editor": [
      {
        "familyName": "Fotakis", 
        "givenName": "Dimitris", 
        "type": "Person"
      }, 
      {
        "familyName": "Pagourtzis", 
        "givenName": "Aris", 
        "type": "Person"
      }, 
      {
        "familyName": "Paschos", 
        "givenName": "Vangelis Th.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-57586-5_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-57585-8", 
        "978-3-319-57586-5"
      ], 
      "name": "Algorithms and Complexity", 
      "type": "Book"
    }, 
    "keywords": [
      "century", 
      "witness", 
      "line of research", 
      "interesting developments", 
      "quarter", 
      "decades", 
      "research", 
      "development", 
      "problem", 
      "input", 
      "lines", 
      "class TFNP", 
      "TFNP", 
      "NP", 
      "proof", 
      "Nash equilibrium problem", 
      "equilibrium problems", 
      "PPAD", 
      "update", 
      "subclass PPAD"
    ], 
    "name": "TFNP: An Update", 
    "pagination": "3-9", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084843533"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-57586-5_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-57586-5_1", 
      "https://app.dimensions.ai/details/publication/pub.1084843533"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_121.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-57586-5_1"
  }
]
 

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-3-319-57586-5_1'

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-3-319-57586-5_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-57586-5_1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-57586-5_1'


 

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

100 TRIPLES      23 PREDICATES      45 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-57586-5_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc28c5d457fd14bd7b9372cbfcff31c1d
4 schema:datePublished 2017-04-14
5 schema:datePublishedReg 2017-04-14
6 schema:description The class TFNP was introduced a quarter of a century ago to capture problems in NP that have a witness for all inputs. A decade ago, this line of research culminated in the proof that the Nash equilibrium problem is complete for the subclass PPAD. Here we review some interesting developments since.
7 schema:editor N12711bb30e3043de95306c4eab548272
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2829e0535462469b96020f5f83ba7af4
12 schema:keywords NP
13 Nash equilibrium problem
14 PPAD
15 TFNP
16 century
17 class TFNP
18 decades
19 development
20 equilibrium problems
21 input
22 interesting developments
23 line of research
24 lines
25 problem
26 proof
27 quarter
28 research
29 subclass PPAD
30 update
31 witness
32 schema:name TFNP: An Update
33 schema:pagination 3-9
34 schema:productId Nb6f8e4312d0a4809bdc4cc4515a93308
35 Nc18451f51406470abfa174bee35e5cf7
36 schema:publisher N17cc9d0f1b8f427caaabecbc8adb9cba
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084843533
38 https://doi.org/10.1007/978-3-319-57586-5_1
39 schema:sdDatePublished 2021-12-01T19:56
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N3669eab5e75b4db4878f49a18bf7c935
42 schema:url https://doi.org/10.1007/978-3-319-57586-5_1
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N12711bb30e3043de95306c4eab548272 rdf:first N8fdf6f367fec423ca5067a69cdbece8e
47 rdf:rest N5c86b09dcf564735af55af59ed2d7268
48 N17cc9d0f1b8f427caaabecbc8adb9cba schema:name Springer Nature
49 rdf:type schema:Organisation
50 N1f205954ed014a9abeeb79b45faebf54 rdf:first N3fb5043215a245b1942b0e5f1493037c
51 rdf:rest rdf:nil
52 N2829e0535462469b96020f5f83ba7af4 schema:isbn 978-3-319-57585-8
53 978-3-319-57586-5
54 schema:name Algorithms and Complexity
55 rdf:type schema:Book
56 N3669eab5e75b4db4878f49a18bf7c935 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N3fb5043215a245b1942b0e5f1493037c schema:familyName Paschos
59 schema:givenName Vangelis Th.
60 rdf:type schema:Person
61 N5c86b09dcf564735af55af59ed2d7268 rdf:first Ne69b1f0fcf1b4ddfbc3cd3b3ff00e528
62 rdf:rest N1f205954ed014a9abeeb79b45faebf54
63 N8fdf6f367fec423ca5067a69cdbece8e schema:familyName Fotakis
64 schema:givenName Dimitris
65 rdf:type schema:Person
66 Nb6f8e4312d0a4809bdc4cc4515a93308 schema:name doi
67 schema:value 10.1007/978-3-319-57586-5_1
68 rdf:type schema:PropertyValue
69 Nc18451f51406470abfa174bee35e5cf7 schema:name dimensions_id
70 schema:value pub.1084843533
71 rdf:type schema:PropertyValue
72 Nc28c5d457fd14bd7b9372cbfcff31c1d rdf:first sg:person.011515430057.75
73 rdf:rest Ndca74df04bf54554b09c9e8148ec2f27
74 Ndca74df04bf54554b09c9e8148ec2f27 rdf:first sg:person.013233165465.63
75 rdf:rest rdf:nil
76 Ne69b1f0fcf1b4ddfbc3cd3b3ff00e528 schema:familyName Pagourtzis
77 schema:givenName Aris
78 rdf:type schema:Person
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.011515430057.75 schema:affiliation grid-institutes:grid.4991.5
86 schema:familyName Goldberg
87 schema:givenName Paul W.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011515430057.75
89 rdf:type schema:Person
90 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
91 schema:familyName Papadimitriou
92 schema:givenName Christos H.
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
94 rdf:type schema:Person
95 grid-institutes:grid.47840.3f schema:alternateName University of California at Berkeley, Berkeley, USA
96 schema:name University of California at Berkeley, Berkeley, USA
97 rdf:type schema:Organization
98 grid-institutes:grid.4991.5 schema:alternateName University of Oxford, Oxford, UK
99 schema:name University of Oxford, Oxford, UK
100 rdf:type schema:Organization
 




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


...