Publikation: Emptiness problems for integer circuits
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2020
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
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
Zitieren
ISO 690
BARTH, 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.023BibTex
@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
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Ja