A topological view of some problems in complexity theory View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1984

AUTHORS

Michael Sipser

ABSTRACT

We present a new, combinatorial proof of the classical theorem that the analytic sets are not closed under complement. Possible connections with questions in complexity theory are discussed.

PAGES

567-572

Book

TITLE

Mathematical Foundations of Computer Science 1984

ISBN

3-540-13372-0

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Mathematics Department, Massachusetts Institute of Technology, 02139\u00a0Cambridge, Massachusetts"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sipser", 
        "givenName": "Michael", 
        "id": "sg:person.01352114470.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352114470.64"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1984", 
    "datePublishedReg": "1984-01-01", 
    "description": "We present a new, combinatorial proof of the classical theorem that the analytic sets are not closed under complement. Possible connections with questions in complexity theory are discussed.", 
    "editor": [
      {
        "familyName": "Chytil", 
        "givenName": "M. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Koubek", 
        "givenName": "V.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0030341", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "3-540-13372-0"
      ], 
      "name": "Mathematical Foundations of Computer Science 1984", 
      "type": "Book"
    }, 
    "name": "A topological view of some problems in complexity theory", 
    "pagination": "567-572", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0030341"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "83538713b1cdbe1bbec5248d7beaa3b5960a52b253ae9039724dfbbe5628daae"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027568061"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin/Heidelberg", 
      "name": "Springer-Verlag", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0030341", 
      "https://app.dimensions.ai/details/publication/pub.1027568061"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T10:20", 
    "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_8659_00000047.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0030341"
  }
]
 

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/bfb0030341'

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/bfb0030341'

Turtle is a human-readable linked data format.

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

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

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


 

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

61 TRIPLES      21 PREDICATES      25 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0030341 schema:author N35ececd3bb074eee807e3d1c16c9bc59
2 schema:datePublished 1984
3 schema:datePublishedReg 1984-01-01
4 schema:description We present a new, combinatorial proof of the classical theorem that the analytic sets are not closed under complement. Possible connections with questions in complexity theory are discussed.
5 schema:editor N9d3ba8dcd9094f648a8f63fc512ea354
6 schema:genre chapter
7 schema:inLanguage en
8 schema:isAccessibleForFree false
9 schema:isPartOf N0f47170baa744f56b1b9f5a54bcc6e25
10 schema:name A topological view of some problems in complexity theory
11 schema:pagination 567-572
12 schema:productId N059715b8aa6f4ca3877ff7c3c74f095c
13 N38cd3a6c6d6e4463856841384d852ca7
14 Nfe8c3d6dfa9e472cba78ace3c67eff7a
15 schema:publisher Nb71292a18eff427bb954a9d603c7fc77
16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027568061
17 https://doi.org/10.1007/bfb0030341
18 schema:sdDatePublished 2019-04-15T10:20
19 schema:sdLicense https://scigraph.springernature.com/explorer/license/
20 schema:sdPublisher N2498dd1121974e4db0736cff68e2fc18
21 schema:url http://link.springer.com/10.1007/BFb0030341
22 sgo:license sg:explorer/license/
23 sgo:sdDataset chapters
24 rdf:type schema:Chapter
25 N059715b8aa6f4ca3877ff7c3c74f095c schema:name dimensions_id
26 schema:value pub.1027568061
27 rdf:type schema:PropertyValue
28 N0f47170baa744f56b1b9f5a54bcc6e25 schema:isbn 3-540-13372-0
29 schema:name Mathematical Foundations of Computer Science 1984
30 rdf:type schema:Book
31 N2498dd1121974e4db0736cff68e2fc18 schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 N35ececd3bb074eee807e3d1c16c9bc59 rdf:first sg:person.01352114470.64
34 rdf:rest rdf:nil
35 N38cd3a6c6d6e4463856841384d852ca7 schema:name readcube_id
36 schema:value 83538713b1cdbe1bbec5248d7beaa3b5960a52b253ae9039724dfbbe5628daae
37 rdf:type schema:PropertyValue
38 N69268c9a41e24071ae39ace0d8f7fbe4 schema:familyName Chytil
39 schema:givenName M. P.
40 rdf:type schema:Person
41 N88d28dcfd9ae404ea333db491ce87680 rdf:first Nae891256541b49d8a4651d277b28168f
42 rdf:rest rdf:nil
43 N9d3ba8dcd9094f648a8f63fc512ea354 rdf:first N69268c9a41e24071ae39ace0d8f7fbe4
44 rdf:rest N88d28dcfd9ae404ea333db491ce87680
45 Nae891256541b49d8a4651d277b28168f schema:familyName Koubek
46 schema:givenName V.
47 rdf:type schema:Person
48 Nb71292a18eff427bb954a9d603c7fc77 schema:location Berlin/Heidelberg
49 schema:name Springer-Verlag
50 rdf:type schema:Organisation
51 Nfe8c3d6dfa9e472cba78ace3c67eff7a schema:name doi
52 schema:value 10.1007/bfb0030341
53 rdf:type schema:PropertyValue
54 sg:person.01352114470.64 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
55 schema:familyName Sipser
56 schema:givenName Michael
57 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352114470.64
58 rdf:type schema:Person
59 https://www.grid.ac/institutes/grid.116068.8 schema:alternateName Massachusetts Institute of Technology
60 schema:name Mathematics Department, Massachusetts Institute of Technology, 02139 Cambridge, Massachusetts
61 rdf:type schema:Organization
 




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


...