A # P-complete problem over arithmetical trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

A # P-complete problem over arithmetical trees

  • Contributed Papers
  • Conference paper
  • First Online:
CAAP '81 (CAAP 1981)

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

Included in the following conference series:

  • 149 Accesses

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.

References

  1. Aho, A.V., Ullman, J.E., Hopcroft, J.D., The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, Mass., 1974

    Google Scholar 

  2. Bertoni,A., Mauri,G., Sabadini,N., A characterization of the class of functions computable in polynomial time on RAM's, Proc. ACM STOC 81, to appear, 1981

    Google Scholar 

  3. Garey, M.R., Johnson, D.S., Computers and Intractability, W.H. Freeman and Co., San Francisco, 1979

    Google Scholar 

  4. Hartmanis,J., Simon,J., On the power of multiplication in Random Access Machines, IEEE Conf. Rec. 15th Symp. on Switching Automata Theory, 1974, 13–23

    Google Scholar 

  5. Percus, J.K., Combinatorial Methods, Springer, Berlin, 1971

    Google Scholar 

  6. Riordan, J., An introduction to combinatorial analysis, Wiley, New York, 1958

    Google Scholar 

  7. Schönhage, A., On the power of Random Access Machines, Proc. 6th ICALP, Lect. Not. in Comp. Sci. 71, Springer, Berlin, 1979, 520–529

    Google Scholar 

  8. Simon, J., On the difference between the one and the many, in Lect. Not. in Comp. Sci. 52, Springer, Berlin, 1977, 480–491

    Google Scholar 

  9. Simon,J., Division is good, Comp. Sci. Dept., Pennsylvania State University, 1979

    Google Scholar 

  10. Valiant, L.G., The complexity of computing the permanent, Theoretical Computer Science 8, 1979, 189–202

    Google Scholar 

  11. Valiant,L.G., The complexity of enumeration and reliability problems, Res. Rep. CSR-15 77, Dept. of Comp. Sci., Univ. of Edinburgh, 1977

    Google Scholar 

  12. Valiant,L.G., Completeness classes in algebra, 11th ACM STOC, 1979, 249–261

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Istituto di Cibernetica, Università di Milano, Italy

    Giancarlo Mauri & Nicoletta Sabadini

  2. Istituto di Matematica, Informatica e Sistemistica, Università di Udine, Italy

    Giancarlo Mauri

Authors
  1. Giancarlo Mauri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicoletta Sabadini
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Egidio Astesiano Corrado Böhm

Rights and permissions

Reprints and permissions

Copyright information

© 1981 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mauri, G., Sabadini, N. (1981). A # P-complete problem over arithmetical trees. In: Astesiano, E., Böhm, C. (eds) CAAP '81. CAAP 1981. Lecture Notes in Computer Science, vol 112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10828-9_71

Download citation

  • DOI: https://doi.org/10.1007/3-540-10828-9_71

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10828-3

  • Online ISBN: 978-3-540-38716-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation