A higher-order characterization of probabilistic polynomial time

DOI10.1007/978-3-642-32495-6_1MaRDI QIDQ3167522zbMATH OpenOpenAlexFDO

Authors 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

Complexity of computation (including implicit computational complexity) (03D15) Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We present RSLR, an implicit higher-order characterization of the class PP of those problems which can be decided in probabilistic polynomial time with error probability smaller than 1/2. Analogously, a (less implicit) characterization of the class BPP can be obtained. RSLR is an extension of Hofmann's SLR with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLR is obtained by syntactical means, as opposed to the standard literature on SLR-derived systems, which use semantics in an essential way.

Recommendations

• A higher-order characterization of probabilistic polynomial time
• A decisive characterization of BPP
• scientific article; zbMATH DE number 3880118
• Restricted relativizations of probabilistic polynomial time
• On the termination problem for probabilistic higher-order recursive programs

Cited in

(5)

• Combining linear logic and size types for implicit complexity
• Probabilistic parameterized polynomial time
• A higher-order characterization of probabilistic polynomial time
• On equivalences, metrics, and polynomial time
• Combining linear logic and size types for implicit complexity

This page was built for publication: A higher-order characterization of probabilistic polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167522)