Publikation:

Emptiness Problems for Integer Circuits

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)
https://doi.org/10.4230/LIPIcs.MFCS.2017.33
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

LARSEN, Kim G., ed., Hans L. BODLAENDER, ed., Jean-François RASKIN, ed.. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Wadern: Schloss Dagstuhl-Leibniz-Zentrum für Informatik GmbH, 2017, 33. Leibniz International Proceedings in Informatics (LIPIcs). 83. ISSN 1868-8969. ISBN 978-3-95977-046-0. Available under: doi: 10.4230/LIPIcs.MFCS.2017.33

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(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) 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 major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

computational complexity, integer expressions, integer circuits, polynomial identity testing

Konferenz

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 21. Aug. 2017 - 25. Aug. 2017, Aalborg, Denmark
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BARTH, Dominik, Moritz BECK, Titus DOSE, Christian GLASSER, Larissa MICHLER, Marc TECHNAU, 2017. Emptiness Problems for Integer Circuits. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Denmark, 21. Aug. 2017 - 25. Aug. 2017. In: LARSEN, Kim G., ed., Hans L. BODLAENDER, ed., Jean-François RASKIN, ed.. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Wadern: Schloss Dagstuhl-Leibniz-Zentrum für Informatik GmbH, 2017, 33. Leibniz International Proceedings in Informatics (LIPIcs). 83. ISSN 1868-8969. ISBN 978-3-95977-046-0. Available under: doi: 10.4230/LIPIcs.MFCS.2017.33
BibTex
@inproceedings{Barth2017Empti-44551,
  year={2017},
  doi={10.4230/LIPIcs.MFCS.2017.33},
  title={Emptiness Problems for Integer Circuits},
  number={83},
  isbn={978-3-95977-046-0},
  issn={1868-8969},
  publisher={Schloss Dagstuhl-Leibniz-Zentrum für Informatik GmbH},
  address={Wadern},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  booktitle={42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  editor={Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-François},
  author={Barth, Dominik and Beck, Moritz and Dose, Titus and Glaßer, Christian and Michler, Larissa and Technau, Marc},
  note={Article Number: 33}
}
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/44551">
    <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(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) 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 major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Beck, Moritz</dc:creator>
    <dc:creator>Barth, Dominik</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-14T11:51:01Z</dc:date>
    <dcterms:title>Emptiness Problems for Integer Circuits</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Technau, Marc</dc:contributor>
    <dc:contributor>Glaßer, Christian</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-14T11:51:01Z</dcterms:available>
    <dc:creator>Dose, Titus</dc:creator>
    <dcterms:issued>2017</dcterms:issued>
    <dc:language>eng</dc:language>
    <dc:creator>Michler, Larissa</dc:creator>
    <dc:contributor>Dose, Titus</dc:contributor>
    <dc:creator>Technau, Marc</dc:creator>
    <dc:creator>Glaßer, Christian</dc:creator>
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Michler, Larissa</dc:contributor>
    <dc:contributor>Barth, Dominik</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44551"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

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