Abstract
The problem of testing membership in the subset of the natural numbers produced at the output gate of a ∪, ∩,- ,+, * combinational circuit is shown to capture a wide range of complexity classes. Although the general problem remains open, the case ∪, ∩,+, * is shown NEXPTIME-complete, the cases ∪, ∩,- , *, ∪, ∩, *, ∪, ∩,+ are shown PSPACE-complete, the case ∪,+ is shown NP-complete, the case ∩,+ is shown C=L-complete, and several other cases are resolved. Interesting auxiliary problems are used, such as testing nonemptyness for union-intersection-concatenation circuits, and expressing each integer, drawn from a set given as input, as powers of relatively prime integers of one’s choosing. Our results extend in nontrivial ways past work by Stockmeyer and Meyer (1973), Wagner (1984) and Yang (2000).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Agrawal, E. Allender, and S. Datta, On TC0, AC0, and arithmetic circuits, J. Computer and System Sciences 60 (2000), pp. 395–421.
E. Allender, Making computation count: Arithmetic circuits in the Nineties, in the Complexity Theory Column, SIGACT NEWS 28 (4) (1997) pp. 2–15.
E. Allender, K. Reinhardt, S. Zhou, Isolation, matching, and counting: Uniform and nonuniform upper bounds, J. Computer and System Sciences 59(1999), pp. 164–181.
E. Allender, D. Barrington, and W. Hesse, Uniform constant-depth threshold circuits for division and iterated multiplication, Proceedings 16th Conference on Computational Complexity, 2001, pp. 150–159.
E. Allender, J. Jiao, M. Mahajan and V. Vinay, Non-commutative arithmetic circuits: depth-reduction and depth lower bounds, Theoretical Computer Science Vol. 209 (1/2,2) (1998), pp. 47–86.
E. Bach, J. Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press 1996.
M. Beaudry and P. McKenzie, Circuits, matrices and nonassociative computation, J. Computer and System Sciences 50 (1995), pp. 441–455.
M. Beaudry, P. McKenzie, P. Péladeau, D. Thérien, Finite monoids: from word to circuit evaluation, SIAM J. Computing 26 (1997), pp. 138–152.
S. Buss, S. Cook, A. Gupta, V. Ramachandran, An optimal parallel algorithm for formula evaluation, SIAM J. Computing 21 (1992), pp. 755–780.
S. R. Buss, The boolean formula value problemis in ALOGTIME, Proceedings 19th ACM Symp, on the Theory of Computing, 1987, pp. 123–131.
H. Caussinus, P. McKenzie, D. Thérien, H. Vollmer, Nondeterministic NC1 computation, J. Computer and System Sciences, 57 (2), 1998, pp. 200–212.
A. K. Chandra, L. Stockmeyer, U. Vishkin, Constant depth reducibility, SIAM Journal on Computing, 13, 1984, pp. 423–439.
A. Chiu, G. Davida, and B. Litow, NC 1 division, available at http://www.cs.jcu.edu.au/ bruce/papers/cr00 3.ps.gz
L. M. Goldschlager, The monotone and planar circuit value problems are logspace complete for P, SIGACT News, 9, 1977, pp. 25–29.
W. Hesse, Division in uniform TC0, Proceedings of the 28th International Colloquium on Automata, Languages, and Programming 2001, Lecture Notes in Computer Science 2076, pp. 104–114
J. von zur Gathen, Parallel algorithms for algebraic problems, SIAM J. on Computing 13(4), (1984), pp. 802–824.
R. Greenlaw, J. Hoover and L. Ruzzo, Limits to parallel computation, P-completeness theory, Oxford University Press, 1995, 311 pages.
M. Ogihara, The PL hierarchy collapses, SIAM Journal of Computing, 27, 1998, pp. 1430–1437.
L. J. Stockmeyer, A. R. Meyer, Word Problems Requiring Exponential Time, Proceedings 5th ACM Symposium on the Theory of Computing, 1973, pp. 1–9.
H. Vollmer, Circuit complexity, Springer, 2000.
K. W. Wagner, The complexity of problems concerning graphs with regularities, Proceedings 11th Mathematical Foundations of Computer Science 1984, Lecture Notes in Computer Science 176, pp. 544–552. Full version as TR N/84/52, Friedrich-Schiller-Universität Jena, 1984.
K. Yang, Integer circuit evaluation is PSPACE-complete, Proceedings 15th Conference on Computational Complexity, 2000, pp. 204–211.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
McKenzie, P., Wagner, K.W. (2003). The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_50
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive