Probabilistic recursion theory and implicit computational complexity. (English) Zbl 1423.03138
Summary: 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.
MSC:
03D10 | Turing machines and related notions |
68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
03D15 | Complexity of computation (including implicit computational complexity) |
68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |