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

https://hal.inria.fr/hal-00909316
Contributor : Davide Sangiogi <>
Submitted on : Tuesday, December 17, 2013 - 4:48:14 PM
Last modification on : Saturday, January 27, 2018 - 1:32:19 AM
Long-term archiving on : Monday, March 17, 2014 - 10:07:08 PM

File

ic2013.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00909316, version 1

Collections

Citation

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

Share

Metrics

Record views

178

Files downloads

262