A Recursion-Theoretic Characterization of the Probabilistic Class PP

Dal Lago, Ugo; Kahle, Reinhard; Oitavem, Isabel

http://hdl.handle.net/10362/132224

Utilize este identificador para referenciar este registo.

Nome:	Descrição:	Tamanho:	Formato:
LIPIcs_MFCS_2021_35.pdf		704.28 KB	Adobe PDF	Ver/Abrir

Contacte-nos

Autores

Dal Lago, Ugo

Kahle, Reinhard

Oitavem, Isabel

Resumo(s)

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.