The Complexity of Membership Problems for Circuits over Sets of Integers

摘要

We investigate the complexity of membership problems for {U, ∩, ~ , +, 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 (2003). 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 {U, +, 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 work by McKenzie and Wagner (2003) in nontrivial ways. Furthermore, evaluating {x }-circuits is shown to be NL ∧ ⊕L-complete, and several other cases are resolved.