Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420296 | Discrete Applied Mathematics | 2010 | 10 Pages |
Abstract
We investigate the complexity of satisfiability problems for {∪,∩,−,+,×}{∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}{∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}{∪,+,×}-circuits is decidable in PSPACE.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr,