Emptiness problems for integer circuits

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BARTH, Dominik, Moritz BECK, Titus DOSE, Christian GLASSER, Larissa MICHLER, Marc TECHNAU, 2020. Emptiness problems for integer circuits. In: Theoretical Computer Science. Elsevier. 824-825, pp. 11-35. ISSN 0304-3975. eISSN 1879-2294. Available under: doi: 10.1016/j.tcs.2020.03.023

@article{Barth2020-07Empti-49826, title={Emptiness problems for integer circuits}, year={2020}, doi={10.1016/j.tcs.2020.03.023}, 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 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/rdf/resource/123456789/49826"> <dc:language>eng</dc:language> <dc:creator>Beck, Moritz</dc:creator> <dc:creator>Michler, Larissa</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <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> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Barth, Dominik</dc:creator> <dc:contributor>Technau, Marc</dc:contributor> <dc:contributor>Glaßer, Christian</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-06-10T13:18:38Z</dcterms:available> <dc:contributor>Barth, Dominik</dc:contributor> <dc:creator>Technau, Marc</dc:creator> <dcterms:issued>2020-07</dcterms:issued> <dcterms:title>Emptiness problems for integer circuits</dcterms:title> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-06-10T13:18:38Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Beck, Moritz</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/49826"/> <dc:contributor>Dose, Titus</dc:contributor> <dc:creator>Dose, Titus</dc:creator> <dc:contributor>Michler, Larissa</dc:contributor> <dc:creator>Glaßer, Christian</dc:creator> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account