Probabilistic recursion theory and implicit computational complexity

DOI10.1007/978-3-319-10882-7_7MaRDI QIDQ2938155zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Sara Zuppiroli

Publication date 13 January 2015

Published in Theoretical Aspects of Computing – ICTAC 2014 (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01091595/file/main.pdf

Mathematics Subject Classification ID

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)

Recommendations

• Probabilistic Recursion Theory and Implicit Computational Complexity
• A higher-order characterization of probabilistic polynomial time
• On higher-order probabilistic subrecursion
• On higher-order probabilistic subrecursion
• scientific article; zbMATH DE number 5309069

Cited in

(6)

• Space-bounded hierarchies and probabilistic computations
• On the \(\delta \to 0\) limit in probabilistic complexity
• A higher-order characterization of probabilistic polynomial time
• On higher-order probabilistic subrecursion
• Probabilistic Recursion Theory and Implicit Computational Complexity
• 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 Q2938155)