Skip to Main content Skip to Navigation
New interface
Conference papers

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
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03346791
Contributor : Ugo Dal Lago Connect in order to contact the contributor
Submitted on : Thursday, September 16, 2021 - 4:04:41 PM
Last modification on : Thursday, January 20, 2022 - 4:15:28 PM
Long-term archiving on: : Friday, December 17, 2021 - 7:19:30 PM

File

mfcs2021.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

20

Files downloads

39