Abstract
In the uniform circuit model of computation, the width of a boolean circuit exactly characterizes the “space” complexity of the computed function. Looking for a similar relationship in Valiant’s algebraic model of computation, we propose width of an arithmetic circuit as a possible measure of space. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. We introduce the class VL as an algebraic variant of deterministic log-space L; VL is a subclass of VP.
Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of “read-once” certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs (an algebraic analog of NL) can be expressed as read-once exponential sums over polynomials in \({{\sf VL}, {\it i.e.}\quad{\sf VBP} \in \Sigma^R \cdot {\sf VL}}\) . Thus, read-once exponential sums can be viewed as a reasonable way of capturing space-bounded non-determinism. We also show that ΣR ·VBP = VBP, i.e. VBPs are stable under read-once exponential sums. Though the best upper bound we have for ΣR ·VL itself is VNP, we can obtain better upper bounds for width-bounded multiplicatively disjoint (md-) circuits. Without the width restriction, md- arithmetic circuits are known to capture all of VP. We show that read-once exponential sums over md- constant-width arithmetic circuits are within VP and that read-once exponential sums over md- polylog-width arithmetic circuits are within VQP.
We also show that exponential sums of a skew formula cannot represent the determinant polynomial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Sanjeev Arora , Boaz Barak (2009) Computational Complexity: A Modern Approach. Cambridge University Press, New York, USA ISBN 0521424267, 9780521424264
Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan (2010).On Lower Bounds for Constant Width Arithmetic Circuits. In: ISAAC, Yingfei Dong, Ding-Zhu Du, Oscar Ibarra editors, Lecture Notes in Computer Science, 637–646. Springer Berlin/Heidelberg
David A. Mix Barrington (1989) Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. Journal of Computer and System Sciences 38(1): 150–164
Lenore Blum, Felipe Cucker, Mike Shub & Steve Smale (1997). Complexity and Real Computation. Springer.
Allan Borodin (1977) On Relating Time and Space to Size and Depth. SIAM J. Comput. 6(4): 733–744
P. Bürgisser, M. Clausen & M. A. Shokrollahi (1997). Algebraic Complexity Theory. Springer-Verlag.
Peter Bürgisser (2000). Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics. Springer-Verlag.
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer (1998) Nondeterministic NC1 Computation. Journal of Computer and System Sciences 57: 200–212
Chiu A., G. Davida, B. Litow (2001) Division in Logspace-Uniform NC1. RAIRO Theoretical Informatics and Applications 35: 259–276
Cook S. (1971) Characterizations of pushdown machines in terms of time-bounded computers. Journal of Association for Computing Machinery 18: 4–18
Stephen A. Cook (1979). Deterministic CFL’s Are Accepted Simultaneously in Polynomial Time and Log Squared Space. In Proceedings of the ACM Symposium on Theory of Computing STOC, 338–345.
Uffe Flarup, Laurent Lyaudet (2010) On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth. Theory Comput. Syst. 46(4): 761–791
Raymond Greenlaw, James Hoover & Walter Ruzzo (1995). Limits To Parallel computation: P-Completeness Theory. Oxford University Press.
Maurice Jansen & Jayalal M. N. Sarma (2010). Balancing Bounded Treewidth Circuits. In CSR, volume 6072 of Lecture Notes in Computer Science, 228–239.
Maurice J. Jansen (2008). Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. In MFCS, 407–418.
Maurice J. Jansen & B. V. Raghavendra Rao (2009). Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity. In CSR, 179–190.
David S. Johnson (1990). A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), Jan van Leeuwen, editor, 67–161. Elsevier and MIT Press.
Erich Kaltofen & Pascal Koiran (2008). Expressing a fraction of two determinants as a determinant. In ISSAC, 141–146.
Pascal Koiran, Sylvain Perifel (2009) VPSPACE and a transfer theorem over the complex field. Theor. Comput. Sci. 410(50): 5244–5251
Pascal Koiran, Sylvain Perifel (2009) VPSPACE and a Transfer Theorem over the Reals. Computational Complexity 18(4): 551–575
Nutan Limaye, Meena Mahajan & B. V. Raghavendra Rao (2010). Arithmetizing Classes Around NC1 and L. Theory of Computing Systems 46(3), 499–522. Preliminary version in STACS 2007, LNCS vol. 4393 pp. 477–488.
Meena Mahajan & B. V. Raghavendra Rao (2009). Small-Space Analogues of Valiant’s Classes. In 17th International Symposium on Fundamentals of Computation Theory, FCT, 250–261.
Guillaume Malod (2007). The Complexity of Polynomials and Their Coefficient Functions. In IEEE Conference on Computational Complexity, 193–204.
Guillaume Malod, Natacha Portier (2008) Characterizing Valiant’s algebraic complexity classes. J. Complexity 24(1): 16–38
Christian Michaux (1989) Une remarque à propos des machines sur \({\mathbb{R}}\) introduites par Blum, Shub et Smale. Comptes Rendus de l’Académie des Sciences de Paris 309(7): 435–437
Paulin Jacobé de Naurois (2006). A Measure of Space for Computing over the Reals. In CiE, 231–240.
Noam Nisan & Avi Wigderson (1995). On the complexity of bilinear forms. In STOC ’95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 723–732. ACM, New York, NY, USA.
Nicholas Pippenger (1979). On Simultaneous Resource Bounds. In 20th Annual Symposium on Foundations of Computer Science FOCS, 307–311.
Amir Shpilka, Avi Wigderson (2002) Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10: 1–27 ISSN 1016-3328
Seinosuke Toda (1991). Counting problems computationally equivalent to the determinant. Technical Report CSIM 91-07, Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo.
Seinosuke Toda (1992) Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Informations and Systems E75-D: 116–124
Iddo Tzamaret (2008). Studies in Algebraic and Propositional Proof Complexity. Ph.D. thesis, Tel Aviv University.
L. G. Valiant (1979). Completeness classes in algebra. In STOC ’79: Proceedings of the eleventh annual ACM symposium on Theory of computing, 249–261. ACM, New York, NY, USA.
Leslie G. Valiant (1976) Graph-theoretic properties in Computational Complexity. Journal of Computer and System Sciences 13: 278–285
Leslie G. Valiant (1979) The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189–201
Leslie G. Valiant (1982) Reducibility by algebraic projections. Logic and Algorithmic: an International Symposium held in honour of Ernst Specker 30: 30, 365–380
Venkateswaran H. (1992) Circuit Definitions of Nondeterministic Complexity Classes. SIAM Journal on Computing 21: 655–670
V Vinay (1991). Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of 6th Structure in Complexity Theory Conference, 270–284.
H. Vollmer (1999). Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mahajan, M., Raghavendra Rao, B.V. Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas. comput. complex. 22, 1–38 (2013). https://doi.org/10.1007/s00037-011-0024-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-011-0024-2