A Recursion-Theoretic Characterization of the Probabilistic Class PP

Ugo Dal Lago (1) , Reinhard Kahle (2, 3) , Isabel Oitavem (2)

1 FOCUS - Foundations of Component-based Ubiquitous Systems
2 NOVA - Universidade Nova de Lisboa = NOVA University Lisbon
3 Mathematisches Institut [Tübingen]

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.

Mots clés: tree-recursion; probabilistic classes; polynomial time; PP

Domaines: Logique en informatique [cs.LO]

Ugo Dal Lago, Reinhard Kahle, Isabel Oitavem. A Recursion-Theoretic Characterization of the Probabilistic Class PP. MFCS 2021 - 46th International Symposium on Mathematical Foundations of Computer Science, Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.35⟩. ⟨hal-03346791⟩