Publikation:

Emptiness problems for integer circuits

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2020

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)
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

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

Theoretical Computer Science. Elsevier. 2020, 824-825, pp. 11-35. ISSN 0304-3975. eISSN 1879-2294. Available under: doi: 10.1016/j.tcs.2020.03.023

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).

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Computational complexity; Integer expressions; Integer circuits; Polynomial identity testing

Konferenz

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, 2020. Emptiness problems for integer circuits. In: Theoretical Computer Science. Elsevier. 2020, 824-825, pp. 11-35. ISSN 0304-3975. eISSN 1879-2294. Available under: doi: 10.1016/j.tcs.2020.03.023
BibTex
@article{Barth2020-07Empti-49826,
  year={2020},
  doi={10.1016/j.tcs.2020.03.023},
  title={Emptiness problems for integer circuits},
  volume={824-825},
  issn={0304-3975},
  journal={Theoretical Computer Science},
  pages={11--35},
  author={Barth, Dominik and Beck, Moritz and Dose, Titus and Glaßer, Christian and Michler, Larissa and Technau, Marc}
}
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/49826">
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dc:contributor>Michler, Larissa</dc:contributor>
    <dc:creator>Glaßer, Christian</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Barth, Dominik</dc:contributor>
    <dc:contributor>Glaßer, Christian</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-06-10T13:18:38Z</dc:date>
    <dcterms:title>Emptiness problems for integer circuits</dcterms:title>
    <dc:creator>Dose, Titus</dc:creator>
    <dc:contributor>Technau, Marc</dc:contributor>
    <dc:creator>Michler, Larissa</dc:creator>
    <dc:creator>Technau, Marc</dc:creator>
    <dc:creator>Barth, Dominik</dc:creator>
    <dc:contributor>Dose, Titus</dc:contributor>
    <dc:creator>Beck, Moritz</dc:creator>
    <dcterms:issued>2020-07</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/49826"/>
    <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).</dcterms:abstract>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-06-10T13:18:38Z</dcterms:available>
  </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
Ja
Begutachtet
Ja
Diese Publikation teilen