zbMATH — the first resource for mathematics

A higher-order characterization of probabilistic polynomial time. (English) Zbl 1367.68103
Peña, Ricardo (ed.) et al., Foundational and practical aspects of resource analysis. Second international workshop, FOPARA 2011, Madrid, Spain, May 19, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-32494-9/pbk). Lecture Notes in Computer Science 7177, 1-18 (2012).
Summary: 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 \(\frac{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.
For the entire collection see [Zbl 1250.68046].

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
68N18 Functional programming and lambda calculus
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDF BibTeX Cite
Full Text: DOI