A Recursion-Theoretic Characterization of the Probabilistic Class PP

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
EditorsFilippo Bonchi, Simon J. Puglisi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772013
DOIs
Publication statusPublished - 1 Aug 2021
Event46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 - Tallinn, Estonia
Duration: 23 Aug 202127 Aug 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume202
ISSN (Print)1868-8969

Conference

Conference46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
Country/TerritoryEstonia
CityTallinn
Period23/08/2127/08/21

Keywords

  • Implicit complexity
  • Polynomial time
  • Pp
  • Probabilistic classes
  • Tree-recursion

Fingerprint

Dive into the research topics of 'A Recursion-Theoretic Characterization of the Probabilistic Class PP'. Together they form a unique fingerprint.

Cite this