×

Equivalence problems for circuits over sets of natural numbers. (English) Zbl 1183.68308

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.

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)
PDFBibTeX XMLCite
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.