Publication . Dal Lago, Ugo; Kahle, Reinhard; Oitavem, Isabel; CMA - Centro de Matemática e Aplicações; DM - Departamento de Matemática
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.
