Probabilistic Recursion Theory and Implicit Computational Complexity
From MaRDI portal
Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
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)- Space-bounded hierarchies and probabilistic computations
- On the \(\delta \to 0\) limit in probabilistic complexity
- On measure quantifiers in first-order arithmetic
- A higher-order characterization of probabilistic polynomial time
- Probabilistic recursion theory and implicit computational complexity
- On equivalences, metrics, and polynomial time
- On higher-order probabilistic subrecursion
- On higher-order probabilistic subrecursion
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)
