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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01231752
Contributor : Ugo Dal Lago <>
Submitted on : Friday, November 20, 2015 - 4:16:35 PM
Last modification on : Wednesday, October 10, 2018 - 10:10:14 AM
Long-term archiving on : Friday, April 28, 2017 - 3:47:53 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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-01231752⟩

Share

Metrics

Record views

155

Files downloads

176