@inproceedings{b5fd28057ca848a283c3acbd0642ed5a,
title = "A Recursion-Theoretic Characterization of the Probabilistic Class PP",
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. ",
keywords = "Implicit complexity, Polynomial time, Pp, Probabilistic classes, Tree-recursion",
author = "{Dal Lago}, Ugo and Reinhard Kahle and Isabel Oitavem",
note = "info:eu-repo/grantAgreement/EC/H2020/818616/EU# info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00297%2F2020/PT# ANR Project PPS 19CE480014 ; 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 ; Conference date: 23-08-2021 Through 27-08-2021",
year = "2021",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.MFCS.2021.35",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Filippo Bonchi and Puglisi, {Simon J.}",
booktitle = "46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021",
}