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 a polytime sampleable distribution, a key concept in average-case complexity and cryptography.
Probabilistic recursion theory and implicit computational complexity / Dal Lago, Ugo; Zuppiroli, Sara; Gabbrielli, Maurizio. - In: SCIENTIFIC ANNALS OF COMPUTER SCIENCE. - ISSN 1843-8121. - STAMPA. - 24:2(2014), pp. 177-216. [10.7561/SACS.2014.2.177]
Probabilistic recursion theory and implicit computational complexity
DAL LAGO, UGO;ZUPPIROLI, SARA;GABBRIELLI, MAURIZIO
2014
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 a polytime sampleable distribution, a key concept in average-case complexity and cryptography.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.