Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INTEGER EXPRESSIONS:
Reports tagged with Integer expressions:
TR17-012 | 17th January 2017
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

Emptiness Problems for Integer Circuits

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, ... more >>>




ISSN 1433-8092 | Imprint