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.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2013
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-00909316
Contributeur : Davide Sangiogi <>
Soumis le : mardi 17 décembre 2013 - 16:48:14
Dernière modification le : vendredi 12 janvier 2018 - 11:01:56
Document(s) archivé(s) le : lundi 17 mars 2014 - 22:07:08

Fichier

ic2013.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

103

Téléchargements de fichiers

121