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.