Glaßer, Christian; Herr, Katrin; Reitwießner, Christian; Travers, Stephen; Waldherr, Matthias Equivalence problems for circuits over sets of natural numbers. (English) Zbl 1183.68308 Theory Comput. Syst. 46, No. 1, 80-103 (2010). Summary: We investigate the complexity of equivalence problems for \(\{\cup ,\cap ,{}^{-},+,\times \}\)-circuits computing sets of natural numbers. These problems were first introduced by L. J. Stockmeyer and A. R. Meyer [Proc. 5th ann. ACM Symp. Theor. Comput., Austin 1973, 1–9 (1973; Zbl 0359.68050)]. We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C\(_{=}\)L, P, \(\Pi^{\text P}_2\), PSPACE, NEXP, and beyond. P. McKenzie and K. W. Wagner [Comput. Complexity 16, No. 3, 211–244 (2007; Zbl 1133.68028)] studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of \(\{\cup ,\cap ,{}^{-},+,\times \}\)-circuits. Cited in 4 ReviewsCited in 7 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 03D15 Complexity of computation (including implicit computational complexity) Keywords:computational complexity; combinatorial integer circuits; algorithms Citations:Zbl 0359.68050; Zbl 1133.68028 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Theory Comput. Syst. 46, No. 1, 80--103 (2010; Zbl 1183.68308) Full Text: DOI References: [1] Àlvarez, C., Balcázar, J.L., Jenner, B.: Adaptive logspace reducibility and parallel time. Math. Syst. Theory 28(2), 117–140 (1995) · Zbl 0815.68054 · doi:10.1007/BF01191473 [2] Allender, E.: Making computation count: Arithmetic circuits in the nineties. SIGACT News 28(4), 2–15 (1997) · doi:10.1145/270563.270564 [3] Allender, E., Ogihara, M.: Relationships among PL, #L, and the determinant. RAIRO Theor. Inform. Appl. 30, 1–21 (1996) · Zbl 0851.68033 [4] Breunig, H.: The complexity of membership problems for circuits over sets of positive numbers. In: Proceedings International Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 4639, pp. 125–136. Springer, Berlin (2007) · Zbl 1135.68435 [5] Bach, E., Shallit, J.: Algorithmic Number Theory. Efficient Algorithms of Foundations of Computing, vol. I. MIT Press, Cambridge (1996) · Zbl 0873.11070 [6] Ko, K.: Some observations on the probabilistic algorithms and NP-hard problems. Inf. Process. Lett. 14(1), 39–43 (1982) · Zbl 0483.68045 · doi:10.1016/0020-0190(82)90139-9 [7] Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Proceedings 13th Symposium on Switching and Automata Theory, pp. 125–129. IEEE Computer Society, Los Alamitos (1972) [8] Mckenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Comput. Complex. 16(3), 211–244 (2007) · Zbl 1133.68028 · doi:10.1007/s00037-007-0229-6 [9] Schönhage, A.: On the power of random access machines. In: ICALP, pp. 520–529 (1979) · Zbl 0409.68030 [10] Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings 5th ACM Symposium on the Theory of Computing, pp. 1–9. ACM, New York (1973) · Zbl 0359.68050 [11] Travers, S.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1), 211–229 (2006) · Zbl 1110.68048 · doi:10.1016/j.tcs.2006.08.017 [12] Wagner, K.: The complexity of problems concerning graphs with regularities. In: Proceedings Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 176, pp. 544–552. Springer, Berlin (1984) · Zbl 0548.68040 [13] Wagner, K.W., Wechsung, G.: On the boolean closure of NP. In: Proceedings International Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 199, pp. 485–493. Springer, Berlin (1985) [14] Yang, K.: Integer circuit evaluation is PSPACE-complete. In: IEEE Conference on Computational Complexity, pp. 204–213 (2000) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.