Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the size complexity of monotone formulas

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1980)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 85))

Included in the following conference series:

Abstract

"Monotone" formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.

    Google Scholar 

  2. A. Ehrenfeucht and P. Zeiger. Complexity measures for regular expressions. Proc. 6th ACM Symposium on Theory of Computing (1974) 75–79.

    Google Scholar 

  3. M. Jerrum and M. Snir. Some exact complexity results for straight line computations over semirings. University of Edinburgh Technical Report CSR-58-80 (1980).

    Google Scholar 

  4. W. Miller. Computational complexity and numerical stability. SIAM J. Computing, 4 (1975) 97–107.

    Google Scholar 

  5. H.J. Ryser. Combinatorial Mathematics. The Carus Mathematical Monographs 14, 1963.

    Google Scholar 

  6. C.P. Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science, 2 (1976) 305–315.

    Google Scholar 

  7. E. Shamir and M. Snir. On the depth complexity of formulas. Mathematical System Theory (to appear).

    Google Scholar 

  8. L.G. Valiant. Negation can be exponentially powerfu. Proc. 11th ACM Symposium on Theory of Computing (1979) 189–196.

    Google Scholar 

  9. L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science (to appear).

    Google Scholar 

  10. L.G. Valiant. Completeness classes in algebra. Proc. 11th ACM Symposium on Theory of Computing (1979) 249–261.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Edinburgh University, Edinburgh, Scotland

    Marc Snir

Authors
  1. Marc Snir
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jaco de Bakker Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 1980 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Snir, M. (1980). On the size complexity of monotone formulas. In: de Bakker, J., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science, vol 85. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10003-2_103

Download citation

  • DOI: https://doi.org/10.1007/3-540-10003-2_103

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10003-4

  • Online ISBN: 978-3-540-39346-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation