A higher-order characterization of probabilistic polynomial time
We present RSLR 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 RSLR ?is an extension of Hofmann's SLR SLR ?with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLR RSLR ?is obtained by syntactical means, as opposed to the standard literature on SLR SLR -derived systems, which use semantics in an essential way.
implicit computational complexity probabilistic classes