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.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2015, 241, pp.114-141. 〈10.1016/j.ic.2014.10.009〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01231752
Contributeur : Ugo Dal Lago <>
Soumis le : vendredi 20 novembre 2015 - 16:16:35
Dernière modification le : samedi 27 janvier 2018 - 01:30:41
Document(s) archivé(s) le : vendredi 28 avril 2017 - 15:47:53

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

65