Ontology type: schema:ScholarlyArticle
2007-10-05
AUTHORSPierre 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... »
PAGES211-244
http://scigraph.springernature.com/pub.10.1007/s00037-007-0229-6
DOIhttp://dx.doi.org/10.1007/s00037-007-0229-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1001544925
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
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 |