Skip to Main content Skip to Navigation
Journal articles

An Higher-Order Characterization of Probabilistic Polynomial Time

Ugo Dal Lago 1 Paolo Parisen Toldin 2, 1
2 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 one half. 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 metadatas

Cited literature [16 references]  Display  Hide  Download
Contributor : Davide Sangiogi <>
Submitted on : Tuesday, December 17, 2013 - 4:48:14 PM
Last modification on : Thursday, March 5, 2020 - 4:51:47 PM
Long-term archiving on: : Monday, March 17, 2014 - 10:07:08 PM


Publisher files allowed on an open archive


  • HAL Id : hal-00909316, version 1



Ugo Dal Lago, Paolo Parisen Toldin. An Higher-Order Characterization of Probabilistic Polynomial Time. Information and Computation, Elsevier, 2013. ⟨hal-00909316⟩



Record views


Files downloads