Emptiness Problems for Integer Circuits

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
Autor:innen
Barth, Dominik
Dose, Titus
Glaßer, Christian
Michler, Larissa
Technau, Marc
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Electronic Colloquium on Computational Complexity. 2017(12), TR17-012. ISSN 1433-8092
Zusammenfassung

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(∪;∩;‾;+;x) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(∪;∩;‾;+;x) studied by Gla_er et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a well-studied, major open problem in algebraic computing complexity:
- membership problem MC(∩;+;x) studied by McKenzie and Wagner 2007
- integer membership problems MC (+;x), MC (∩;+;x) studied by Travers 2006
- equivalence problem EQ(+;x) studied by Glaßer et al. 2010

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
computational complexity, integer circuits, Integer expressions, polynomial identity testing
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BARTH, Dominik, Moritz BECK, Titus DOSE, Christian GLASSER, Larissa MICHLER, Marc TECHNAU, 2017. Emptiness Problems for Integer Circuits. In: Electronic Colloquium on Computational Complexity. 2017(12), TR17-012. ISSN 1433-8092
BibTex
@article{Barth2017Empti-44630,
  year={2017},
  title={Emptiness Problems for Integer Circuits},
  url={https://eccc.weizmann.ac.il/report/2017/012/},
  number={12},
  issn={1433-8092},
  journal={Electronic Colloquium on Computational Complexity},
  author={Barth, Dominik and Beck, Moritz and Dose, Titus and Glaßer, Christian and Michler, Larissa and Technau, Marc},
  note={Article Number: TR17-012}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44630">
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dc:contributor>Barth, Dominik</dc:contributor>
    <dc:language>eng</dc:language>
    <dcterms:title>Emptiness Problems for Integer Circuits</dcterms:title>
    <dc:contributor>Dose, Titus</dc:contributor>
    <dc:creator>Barth, Dominik</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Technau, Marc</dc:contributor>
    <dc:contributor>Glaßer, Christian</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-21T10:40:42Z</dc:date>
    <dc:creator>Beck, Moritz</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44630"/>
    <dc:creator>Dose, Titus</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-21T10:40:42Z</dcterms:available>
    <dc:contributor>Michler, Larissa</dc:contributor>
    <dc:creator>Michler, Larissa</dc:creator>
    <dcterms:issued>2017</dcterms:issued>
    <dcterms:abstract xml:lang="eng">We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(∪;∩;‾;+;x) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(∪;∩;‾;+;x) studied by Gla_er et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a well-studied, major open problem in algebraic computing complexity:&lt;br /&gt;- membership problem MC(∩;+;x) studied by McKenzie and Wagner 2007&lt;br /&gt;- integer membership problems MC&lt;sub&gt;ℤ&lt;/sub&gt; (+;x), MC&lt;sub&gt;ℤ&lt;/sub&gt; (∩;+;x) studied by Travers 2006&lt;br /&gt;- equivalence problem EQ(+;x) studied by Glaßer et al. 2010</dcterms:abstract>
    <dc:creator>Glaßer, Christian</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Technau, Marc</dc:creator>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
Prüfdatum der URL
2019-01-11
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen