Bounded-Error Probabilistic Polynomial-Time (BPP)

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

1. If the answer is ‘yes’ then at least 2/3 of the computation paths accept.
2. If the answer is ‘no’ then at most 1/3 of the computation paths accept. (Here all computation paths have the same length.)

Known relationships

• BPP is in the intersection of AM and coAM — TODO citaion