Probabilistic Recursion Theory and Implicit Computational Complexity
From MaRDI portal
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Abstract: We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of polytime sampleable distributions, a key concept in average-case complexity and cryptography.
Recommendations
- Probabilistic recursion theory and implicit computational complexity
- scientific article; zbMATH DE number 7701424
- The Probabilistic Theory of Linear Complexity
- scientific article; zbMATH DE number 3870594
- Probabilistic complexity classes and lowness
- Probabilistic Turing machines and recursively enumerable Dedekind cuts
- Parameterized analogues of probabilistic computation
- Probabilistic computability and choice
- Probability metrics and recursive algorithms
Cited in
(8)- Probabilistic recursion theory and implicit computational complexity
- On higher-order probabilistic subrecursion
- On higher-order probabilistic subrecursion
- On measure quantifiers in first-order arithmetic
- On equivalences, metrics, and polynomial time
- Space-bounded hierarchies and probabilistic computations
- A higher-order characterization of probabilistic polynomial time
- On the \(\delta \to 0\) limit in probabilistic complexity
This page was built for publication: Probabilistic Recursion Theory and Implicit Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621181)
