Skip to Main content Skip to Navigation
Journal articles

A Higher-Order Characterization of Probabilistic Polynomial Time

Ugo Dal Lago 1, 2 Paolo Parisen 1, 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 : We present RSLR, an implicit higher-order characterization of the class PP of those problems which can be decided in probabilistic polynomial time with error probability smaller than 1 /2. Analogously, a (less implicit) characterization of the class BPP can be obtained. RSLR is an extension of Hofmann's SLR with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLR is obtained by syntactical means, as opposed to the standard literature on SLR-derived systems, which use semantics in an essential way.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Ugo Dal Lago Connect in order to contact the contributor
Submitted on : Friday, November 20, 2015 - 4:16:35 PM
Last modification on : Thursday, January 20, 2022 - 5:28:44 PM
Long-term archiving on: : Friday, April 28, 2017 - 3:47:53 PM


Files produced by the author(s)




Ugo Dal Lago, Paolo Parisen. A Higher-Order Characterization of Probabilistic Polynomial Time. Information and Computation, Elsevier, 2015, 241, pp.114-141. ⟨10.1016/j.ic.2014.10.009⟩. ⟨hal-01231752v2⟩



Record views


Files downloads