The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-10-05

AUTHORS

Pierre McKenzie, Klaus W. Wagner

ABSTRACT

.The problem of testing membership in the subset of the natural numbers produced at the output gate of a {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, ^-, +, \times$$\end{document}} combinational circuit is shown to capture a wide range of complexity classes. Although the general problem remains open, the case {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, +, \times$$\end{document}} is shown NEXPTIME-complete, the cases {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, ^-, \times$$\end{document} }, {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, \times$$\end{document}}, {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, +$$\end{document}} are shown PSPACE-complete, the case {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, +$$\end{document} } is shown NP-complete, the case {∩, +} is shown C=L-complete, and several other cases are resolved. Interesting auxiliary problems are used, such as testing nonemptyness for union-intersection-concatenation circuits, and expressing each integer, drawn from a set given as input, as powers of relatively prime integers of one’s choosing. Our results extend in nontrivial ways past work by Stockmeyer and Meyer (1973), Wagner (1984) and Yang (2000). More... »

PAGES

211-244

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00037-007-0229-6

DOI

http://dx.doi.org/10.1007/s00037-007-0229-6

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Informatique et recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, C.P. 6128, H3C 3J7, Succ. Centre-Ville Montr\u00e9al, Qu\u00e9bec, Canada", 
          "id": "http://www.grid.ac/institutes/grid.14848.31", 
          "name": [
            "Informatique et recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, C.P. 6128, H3C 3J7, Succ. Centre-Ville Montr\u00e9al, Qu\u00e9bec, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "McKenzie", 
        "givenName": "Pierre", 
        "id": "sg:person.07654632337.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07654632337.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Theoretische Informatik, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, D-97074, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Theoretische Informatik, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, D-97074, W\u00fcrzburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wagner", 
        "givenName": "Klaus W.", 
        "id": "sg:person.014450347631.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014450347631.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-10-05", 
    "datePublishedReg": "2007-10-05", 
    "description": "Abstract.The problem of testing membership in the subset of the natural numbers produced at the output gate of a {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, \\bigcap, ^-, +, \\times$$\\end{document}} combinational circuit is shown to capture a wide range of complexity classes. Although the general problem remains open, the case {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, \\bigcap, +, \\times$$\\end{document}} is shown NEXPTIME-complete, the cases {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, \\bigcap, ^-, \\times$$\\end{document}\u00a0}, {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, \\bigcap, \\times$$\\end{document}}, {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, \\bigcap, +$$\\end{document}} are shown PSPACE-complete, the case {\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\bigcup, +$$\\end{document}\u00a0} is shown NP-complete, the case {\u2229,\u00a0+} is shown C=L-complete, and several other cases are resolved. Interesting auxiliary problems are used, such as testing nonemptyness for union-intersection-concatenation circuits, and expressing each integer, drawn from a set given as input, as powers of relatively prime integers of one\u2019s choosing. Our results extend in nontrivial ways past work by Stockmeyer and Meyer (1973), Wagner (1984) and Yang (2000).", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00037-007-0229-6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "16"
      }
    ], 
    "keywords": [
      "circuit", 
      "combinational circuits", 
      "NPs", 
      "output gate", 
      "gate", 
      "wide range", 
      "natural numbers", 
      "range", 
      "power", 
      "auxiliary problem", 
      "work", 
      "complexity", 
      "problem", 
      "complexity classes", 
      "general problem", 
      "prime integers", 
      "nontrivial way", 
      "membership problem", 
      "number", 
      "nonemptyness", 
      "integers", 
      "results", 
      "way", 
      "set", 
      "Stockmeyer", 
      "class", 
      "cases", 
      "Yang", 
      "subset", 
      "input", 
      "choosing", 
      "Wagner", 
      "Meyer", 
      "membership"
    ], 
    "name": "The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers", 
    "pagination": "211-244", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001544925"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00037-007-0229-6"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00037-007-0229-6", 
      "https://app.dimensions.ai/details/publication/pub.1001544925"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-06-01T22:07", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_455.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00037-007-0229-6"
  }
]
 

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/s00037-007-0229-6'

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/s00037-007-0229-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00037-007-0229-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00037-007-0229-6'


 

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

102 TRIPLES      21 PREDICATES      59 URIs      51 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00037-007-0229-6 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Nb2d50429b532400188b51133efdad0e9
4 schema:datePublished 2007-10-05
5 schema:datePublishedReg 2007-10-05
6 schema:description Abstract.The problem of testing membership in the subset of the natural numbers produced at the output gate of a {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, ^-, +, \times$$\end{document}} combinational circuit is shown to capture a wide range of complexity classes. Although the general problem remains open, the case {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, +, \times$$\end{document}} is shown NEXPTIME-complete, the cases {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, ^-, \times$$\end{document} }, {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, \times$$\end{document}}, {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, \bigcap, +$$\end{document}} are shown PSPACE-complete, the case {\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup, +$$\end{document} } is shown NP-complete, the case {∩, +} is shown C=L-complete, and several other cases are resolved. Interesting auxiliary problems are used, such as testing nonemptyness for union-intersection-concatenation circuits, and expressing each integer, drawn from a set given as input, as powers of relatively prime integers of one’s choosing. Our results extend in nontrivial ways past work by Stockmeyer and Meyer (1973), Wagner (1984) and Yang (2000).
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N51210e3c741b46409d6795961e150d13
11 N73b98fe7f0da4cf08b846183a6a04856
12 sg:journal.1136224
13 schema:keywords Meyer
14 NPs
15 Stockmeyer
16 Wagner
17 Yang
18 auxiliary problem
19 cases
20 choosing
21 circuit
22 class
23 combinational circuits
24 complexity
25 complexity classes
26 gate
27 general problem
28 input
29 integers
30 membership
31 membership problem
32 natural numbers
33 nonemptyness
34 nontrivial way
35 number
36 output gate
37 power
38 prime integers
39 problem
40 range
41 results
42 set
43 subset
44 way
45 wide range
46 work
47 schema:name The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers
48 schema:pagination 211-244
49 schema:productId N65c8eb11897c49f6b64c119cd71eaa64
50 Nb29bd270eba64b08b927b472d9d1e340
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001544925
52 https://doi.org/10.1007/s00037-007-0229-6
53 schema:sdDatePublished 2022-06-01T22:07
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Nc15b6c47a3424e4a920f2caf19fdaa86
56 schema:url https://doi.org/10.1007/s00037-007-0229-6
57 sgo:license sg:explorer/license/
58 sgo:sdDataset articles
59 rdf:type schema:ScholarlyArticle
60 N51210e3c741b46409d6795961e150d13 schema:volumeNumber 16
61 rdf:type schema:PublicationVolume
62 N65c8eb11897c49f6b64c119cd71eaa64 schema:name doi
63 schema:value 10.1007/s00037-007-0229-6
64 rdf:type schema:PropertyValue
65 N73b98fe7f0da4cf08b846183a6a04856 schema:issueNumber 3
66 rdf:type schema:PublicationIssue
67 N91a5cb4a758242d2aa297c13ba01e579 rdf:first sg:person.014450347631.05
68 rdf:rest rdf:nil
69 Nb29bd270eba64b08b927b472d9d1e340 schema:name dimensions_id
70 schema:value pub.1001544925
71 rdf:type schema:PropertyValue
72 Nb2d50429b532400188b51133efdad0e9 rdf:first sg:person.07654632337.54
73 rdf:rest N91a5cb4a758242d2aa297c13ba01e579
74 Nc15b6c47a3424e4a920f2caf19fdaa86 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
77 schema:name Psychology and Cognitive Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
80 schema:name Psychology
81 rdf:type schema:DefinedTerm
82 sg:journal.1136224 schema:issn 1016-3328
83 1420-8954
84 schema:name computational complexity
85 schema:publisher Springer Nature
86 rdf:type schema:Periodical
87 sg:person.014450347631.05 schema:affiliation grid-institutes:grid.8379.5
88 schema:familyName Wagner
89 schema:givenName Klaus W.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014450347631.05
91 rdf:type schema:Person
92 sg:person.07654632337.54 schema:affiliation grid-institutes:grid.14848.31
93 schema:familyName McKenzie
94 schema:givenName Pierre
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07654632337.54
96 rdf:type schema:Person
97 grid-institutes:grid.14848.31 schema:alternateName Informatique et recherche opérationnelle, Université de Montréal, C.P. 6128, H3C 3J7, Succ. Centre-Ville Montréal, Québec, Canada
98 schema:name Informatique et recherche opérationnelle, Université de Montréal, C.P. 6128, H3C 3J7, Succ. Centre-Ville Montréal, Québec, Canada
99 rdf:type schema:Organization
100 grid-institutes:grid.8379.5 schema:alternateName Theoretische Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, D-97074, Würzburg, Germany
101 schema:name Theoretische Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, D-97074, Würzburg, Germany
102 rdf:type schema:Organization
 




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


...