Abstract
We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems before. We also study these questions for circuits computing multilinear polynomials and for univariate multiplicatively disjoint circuits.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Allender (2004).Arithmetic circuits and counting complexity classes. In Complexity of computations and proofs, volume 13 of Quad. Mat., 33–72. Dept. Math., Seconda Univ. Napoli, Caserta.
Allender E., Beals R., Ogihara M. (1999) The complexity of matrix rank and feasible systems of linear equations. Computational Complexity 8(2): 99–126
Allender E., Bürgisser P., Kjeldgaard-Pedersen J., Miltersen P. B. (2009) On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5): 1987–2006
E. Allender & K. W. Wagner (1993). Counting hierarchies: polynomial time and constant depth circuits. Current trends in theoretical computer science: essays and Tutorials 40, 469.
S. Arora & B. Barak (2009). Computational complexity: a modern approach. Cambridge University Press.
P. Bürgisser (2000). Completeness and reduction in algebraic complexity theory, volume 7. Springer Verlag.
P. Bürgisser (2009). On defining integers and proving arithmetic circuit lower bounds. Computational Complexity 18(1), 81–103.
Zhixiang Chen & Bin Fu (2010). Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials. In COCOA (1), 309–323.
Zhixiang Chen & Bin Fu (2011). The Complexity of Testing Monomials in Multivariate Polynomials. In COCOA, 1–15.
Richard A. DeMillo & Richard J. Lipton (1978). A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4), 193–195. URL http://dblp.uni-trier.de/db/journals/ipl/ipl7.html#DemilloL78.
H. Fournier, G. Malod & S. Mengel (2012). Monomials in arithmetic circuits: Complete problems in the counting hierarchy. In STACS, 362–373.
S. Garg & E. Schost (2009). Interpolation of polynomials given by straight-line programs. Theor. Comput. Sci. 410(27-29), 2659–2662.
J. von zur Gathen (1987). Feasible arithmetic computations: Valiant’s hypothesis. Journal of Symbolic Computation 4(2), 137–172.
F. Green (1993). On the Power of Deterministic Reductions to C = P. Theory of Computing Systems 26(2), 215–233.
J. Hammond (1879). Question 6001. Educ. Times 32, 179.
J. Heintz & C. P. Schnorr (1980). Testing polynomials which are easy to compute (Extended Abstract). In Proceedings of the twelfth annual ACM symposium on Theory of computing, STOC ’80, 262–272. ACM, New York, NY, USA. ISBN 0-89791-017-6. http://doi.acm.org/10.1145/800141.804674.
L. A. Hemaspaandra & M. Ogihara (2002). The complexity theory companion. Springer Verlag.
M. Jansen & R. Santhanam (2011). Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. In ICALP, 724–735.
V. Kabanets & R. Impagliazzo (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13, 1–46. ISSN 1016-3328. http://dx.doi.org/10.1007/s00037-004-0182-6.
N. Kayal & C. Saha (2011). On the Sum of Square Roots of Polynomials and related problems. In IEEE Conference on Computational Complexity, 292–299.
Adam R. Klivans & Daniel Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, STOC ’01, 216–223. ACM, New York, NY, USA. ISBN 1-58113-349-9. http://doi.acm.org/10.1145/380752.380801.
P. Koiran & S. Perifel (2007). The complexity of two problems on arithmetic circuits. Theor. Comput. Sci. 389(1-2), 172–181.
P. Koiran & S. Perifel (2011). Interpolation in Valiant’s theory. Computational Complexity 1–20.
I. Koutis (2008). Faster Algebraic Algorithms for Path and Packing Problems. In ICALP, 575–586.
J. Kwisthout, H. L. Bodlaender & L. C. van der Gaag (2011). The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks. In SOFSEM, 356–367.
M. Mahajan, B. V. Raghavendra Rao & K. Sreenivasaiah (2012). Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. In MFCS, 655–667.
M. Mahajan & V. Vinay (1997). A combinatorial algorithm for the determinant. In Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 730–738. Society for Industrial and Applied Mathematics.
G. Malod & N. Portier (2008). Characterizing Valiant’s algebraic complexity classes. J. Complexity 24(1), 16–38.
P. McKenzie & K. W. Wagner (2007). The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity 16(3), 211–244.
J. Mittmann, N. Saxena & P. Scheiblechner (2012). Algebraic Independence in Positive Characteristic – A p-Adic Calculus.ArXiv e-prints.
M. Mundhenk, J. Goldsmith, C. Lusena & E. Allender (2000). Complexity of Finite-Horizon Markov Decision Process Problems. Journal of the ACM (JACM) 47(4), 681–720.
A. Schönhage (1979). On the Power of Random Access Machines. In ICALP, 520–529.
J. T. Schwartz (1980). Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27(4), 701–717. ISSN 0004-5411. http://doi.acm.org/10.1145/322217.322225.
Yann Strozecki (2013). On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation. Theory Comput. Syst. 53(4), 532–568.
J. Torán (1988). Succinct Representations of Counting Problems. In AAECC, 415–426.
J. Torán (1991). Complexity Classes Defined by Counting Quantifiers. J. ACM 38(3), 753–774.
L.G. Valiant (1979). Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on Theory of computing, 249–261. ACM.
H. Venkateswaran (1991). Properties that Characterize LOGCFL. J. Comput. Syst. Sci. 43(2), 380–404.
H. Venkateswaran & M. Tompa (1989). A New Pebble Game that Characterizes Parallel Complexity Classes. SIAM J. Comput. 18(3), 533–549.
K. W. Wagner (1986). The Complexity of Combinatorial Problems with Succinct Input Representation. Acta Informatica 23(3), 325–356.
R. Williams (2009). Finding paths of length k in O *(2k) time. Information Processing Letters 109(6), 315–318.
Richard Zippel (1979). Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM ’79, 216–226. Springer-Verlag, London, UK, UK. ISBN 3-540-09519-5. http://dl.acm.org/citation.cfm?id=646670.698972.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fournier, H., Malod, G. & Mengel, S. Monomials in Arithmetic Circuits: Complete Problems in the Counting Hierarchy. comput. complex. 24, 1–30 (2015). https://doi.org/10.1007/s00037-013-0079-3
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-013-0079-3