We investigate the problems of testing membership in the subset of the positive numbers produced at the output of combinational circuits. These problems are a natural modification of those studied by McKenzie and Wagner (2003), where circuits computed sets of natural numbers. It turns out that the missing 0 has strong implications, not only because 0 can be used to test for emptiness. We show that the membership problem for the general case and for is PSPACE-complete, whereas it is NEXPTIME-hard if one allows 0. Furthermore, testing membership for is NL-complete (as opposed to -hard), and several other cases are resolved.
展开▼
