Class Description

PostBPP: BPP With Postselection

Alias for BPP_path.

Linked From

PostBPP^cc: Communication Complexity PostBPP

The corresponding model consists of randomized protocols that may output 0, 1, or "abort", such that on every input, the non-abort probability is at least some α>0 (which is to be thought of as a function of n), and conditioned on not aborting, the output is correct with probability at least 2/3. The cost of a protocol is defined to be its communication cost plus log(1/α).

Contained in, but does not equal, PP^cc [Kla03].

Contained in PH^cc.

The complexity measure corresponding to PostBPP^cc is equivalent to the "extended discrepancy bound" [GL14].

More about...