Class Description

BC₌P: Bounded-Error C₌P

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then exactly 1/2 of the computation paths accept.
2. If the answer is 'no' then either at most 1/4 or at least 3/4 of the computation paths accept.

(Here all computation paths have the same length.)

Defined in [Wat15], where it was shown that BC₌P admits efficient amplification and is closed under union, intersection, disjunction, and conjunction, and that coRP ⊆ BC₌P ⊆ BPP.

Linked From

No class.