A Higher-Order Characterization of Probabilistic Polynomial Time

DOI10.1007/978-3-642-32495-6_1zbMath1367.68103arXiv1202.3317MaRDI QIDQ3167522

Ugo Dal Lago, Paolo Parisen Toldin

Publication date: 2 November 2012

Published in: Foundational and Practical Aspects of Resource Analysis (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68N18: Functional programming and lambda calculus

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)