# Semi-bounded probabilistic polynomial-time, is it equal to BPP?

The complexity class $$\mathsf{BPP}$$ is typically defined as the class of all problems for which:

1. Running an algorithm once takes polynomial time at most.
2. The answer is correct with the probability at least $$2/3$$.

The complexity class $$\mathsf{PP}$$, on the other hand, has $$1/2$$ instead of $$2/3$$ in the second constraint. Now, we can create a class that lies between them:

1. Running an algorithm once takes polynomial time at most.
2. The answer "YES" is correct with the probability at least $$2/3$$.
3. The answer "NO" is correct with the probability at least $$1/2$$.

Is this complexity class equivalent to $$\mathsf{BPP}$$? If this is not known, is it in $$\mathsf P/poly$$ at least?

Your class is the same as BPP. If you run your algorithm $$n$$ times, then in the YES case, the expected number of YES answers is at least $$(2/3)n$$, while in the NO case, the expected number of YES answers is at most $$(1/2)n$$. Moreover, both of these values are concentrated by Chernoff bounds. Therefore if you answer YES if you see at least $$0.6n$$ many YES answers, then you get the correct answer with exponentially small error probability.