The complexity of membership problems for circuits over sets of integers

We investigate the complexity of membership problems for -circuits computing sets of integers. These problems are a natural modification of the membership problems for circuits computing sets of natural numbers studied by McKenzie and Wagner [The complexity of membership problems for circuits over sets of natural numbers, Lecture Notes in Computer Science, Vol. 2607, 2003, pp. 571–582]. We show that there are several membership problems for which the complexity in the case of integers differs significantly from the case of the natural numbers: testing membership in the subset of integers produced at the output of a {∪,+,×}-circuit is NEXPTIME-complete, whereas it is PSPACE-complete for the natural numbers. As another result, evaluating {-,+}-circuits is shown to be P-complete for the integers and PSPACE-complete for the natural numbers. The latter result extends McKenzie and Wagner's work in nontrivial ways. Furthermore, evaluating {×}-circuits is shown to be NL∧⊕L-complete, and several other cases are resolved.