1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.