Document Open Access Logo

A Recursion-Theoretic Characterization of the Probabilistic Class PP

Authors Ugo Dal Lago, Reinhard Kahle, Isabel Oitavem

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.35.pdf
  • Filesize: 0.68 MB
  • 12 pages

Document Identifiers

Author Details

Ugo Dal Lago
  • University of Bologna, Italy
  • INRIA Sophia Antipolis, France
Reinhard Kahle
  • Carl Friedrich von Weizsäcker Center, Universität Tübingen, Germany
  • Center for Mathematics and Applications (CMA), FCT, Nova University Lisbon, Caparica, Portugal
Isabel Oitavem
  • Center for Mathematics and Applications (CMA), FCT, Nova University Lisbon, Caparica, Portugal
  • Department of Mathematics, FCT, Nova University Lisbon, Caparica, Portugal

Funding

  • Dal Lago, Ugo: Research supported by the ERC CoG DIAPASoN, GA 818616, and by the ANR Project PPS 19CE480014.
  • Kahle, Reinhard: Research supported by the Udo Keller Foundation and as for Isabel Oitavem.
  • Oitavem, Isabel: National funds throught the FCT - Fundação para a Ciência e Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications).

Cite As Get BibTex

Ugo Dal Lago, Reinhard Kahle, and Isabel Oitavem. A Recursion-Theoretic Characterization of the Probabilistic Class PP. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 35:1-35:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.35

Abstract

Probabilistic complexity classes, despite capturing the notion of feasibility, have escaped any treatment by the tools of so-called implicit-complexity. Their inherently semantic nature is of course a barrier to the characterization of classes like BPP or ZPP, but not all classes are semantic. In this paper, we introduce a recursion-theoretic characterization of the probabilistic class PP, using recursion schemata with pointers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Recursive functions
Keywords
  • Implicit complexity
  • tree-recursion
  • probabilistic classes
  • polynomial time
  • PP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. José L. Balcázar, Josep Díaz, and Joaquim Gabarró. Structural Complexity I. Springer Publishing Company, Incorporated, 2nd edition, 2012. Google Scholar
  2. Stephen Bellantoni and Stephen A. Cook. A new recursion-theoretic characterization of the polytime functions. Comput. Complex., 2:97-110, 1992. Google Scholar
  3. Stephen Bellantoni and Isabel Oitavem. Separating NC along the delta axis. Theor. Comput. Sci., 318(1-2):57-78, 2004. Google Scholar
  4. Alan Cobham. The intrinsic computational difficulty of functions. In Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress (Studies in Logic and the Foundations of Mathematics), pages 24-30. North-Holland Publishing, 1965. Google Scholar
  5. Kord Eickmeyer and Martin Grohe. Randomisation and derandomisation in descriptive complexity theory. Log. Methods Comput. Sci., 7(3), 2011. Google Scholar
  6. John Gill. Computational complexity of probabilistic turing machines. SIAM J. Comput., 6(4):675-695, 1977. Google Scholar
  7. Emil Jerábek. Approximate counting in bounded arithmetic. J. Symb. Log., 72(3):959-993, 2007. Google Scholar
  8. Reinhard Kahle and Isabel Oitavem. Applicative theories for the polynomial hierarchy of time and its levels. Annals of Pure and Applied Logic, 164(6):663-675, 2013. Google Scholar
  9. Daniel Leivant. Ramified recurrence and computational complexity I: word recurrence and polytime. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 320-343. Birkhäuser, 1995. Google Scholar
  10. Daniel Leivant and Jean-Yves Marion. Ramified recurrence and computational complexity II: substitution and poly-space. In Computer Science Logic, 8th International Workshop, CSL '94, Kazimierz, Poland, September 25-30, 1994, Selected Papers, volume 933 of LNCS, pages 486-500. Springer, 1994. Google Scholar
  11. Peter Møller Neergaard. A functional language for logarithmic space. In Wei-Ngan Chin, editor, Programming Languages and Systems: Second Asian Symposium, APLAS 2004, Taipei, Taiwan, November 4-6, 2004. Proceedings, volume 3302 of LNCS, pages 311-326. Springer, 2004. Google Scholar
  12. Isabel Oitavem. Characterizing NC with tier 0 pointers. Math. Log. Q., 50(1):9-17, 2004. Google Scholar
  13. Isabel Oitavem. Characterizing PSPACE with pointers. Math. Log. Q., 54(3):323-329, 2008. Google Scholar
  14. Isabel Oitavem. A recursion-theoretic approach to NP. Ann. Pure Appl. Log., 162(8):661-666, 2011. Google Scholar
  15. Thomas Strahm. Theories with self-application and computational complexity. Information and Computation, 185:263-297, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact