An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version)

Details An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version) An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version)

2012-02-15

arxiv.org/abs/1202.3317v1

Computer Science

Logic in Computer Science

32 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-557888