The complexity of membership problems for circuits over sets of integers

We investigate the complexity of membership problems for {boolean OR, boolean AND, (-), +, X}-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 {boolean OR, +, X}-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 {X}-circuits is shown to be NL boolean OR circle plus L-complete, and several other cases are resolved. (c) 2006 Elsevier B.V. All rights reserved.