Probabilistic Recursion Theory and Implicit Computational Complexity

DOI10.7561/SACS.2014.2.177zbMath1423.03138arXiv1406.3378MaRDI QIDQ4621181

Maurizio Gabbrielli, Ugo Dal Lago, Sara Zuppiroli

Publication date: 8 February 2019

Published in: Scientific Annals of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3378

zbMATH Keywords

implicit computational complexityprobabilistic Turing machinesprobabilistic recursion theory

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

On Equivalences, Metrics, and Polynomial Time ⋮ Unnamed Item ⋮ On measure quantifiers in first-order arithmetic

This page was built for publication: Probabilistic Recursion Theory and Implicit Computational Complexity