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 Ne0808cf2845f404abcf881bc748d0385
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 N8fffac07c8794aa984427e31a3204771
11 Naf59ec9e0cbf4653af2c3481a5e1bfd0
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 N030163abb3bf4840937dac622cf73199
50 N4cacdf6072474e2d8b7bcd4f9e5801cd
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 N028c01841ab84c2c97f2b2aeced5a666
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 N028c01841ab84c2c97f2b2aeced5a666 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N030163abb3bf4840937dac622cf73199 schema:name doi
63 schema:value 10.1007/s00037-007-0229-6
64 rdf:type schema:PropertyValue
65 N4cacdf6072474e2d8b7bcd4f9e5801cd schema:name dimensions_id
66 schema:value pub.1001544925
67 rdf:type schema:PropertyValue
68 N8fffac07c8794aa984427e31a3204771 schema:volumeNumber 16
69 rdf:type schema:PublicationVolume
70 N97eb01171d1d4e1baffc3a0364ea62de rdf:first sg:person.014450347631.05
71 rdf:rest rdf:nil
72 Naf59ec9e0cbf4653af2c3481a5e1bfd0 schema:issueNumber 3
73 rdf:type schema:PublicationIssue
74 Ne0808cf2845f404abcf881bc748d0385 rdf:first sg:person.07654632337.54
75 rdf:rest N97eb01171d1d4e1baffc3a0364ea62de
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)


...