3
$\begingroup$

BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.

But why was 1/3 chosen? If we have an algorithm with some error probability less than 1/2, then we can run it several times, taking the most common result, to obtain an error probability of less than 1/3 while still staying in the same complexity class.

So why isn't BPP instead defined as the algorithms which have an error probability of less than 1/2? Is there something special about 1/3?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It even says in the article that In practice, an error probability of ​1⁄3 might not be acceptable, however, the choice of ​1⁄3 in the definition is arbitrary. It can be any constant between 0 and ​1⁄2 (exclusive) and the set BPP will be unchanged. See also Prove or refute: BPP(0.90,0.95) = BPP and Can BPP be bounded around any constant other than 1/2?. $\endgroup$
    – John K.
    Commented Sep 1, 2019 at 17:48
  • 1
    $\begingroup$ Possible duplicate of Prove or refute: BPP(0.90,0.95) = BPP $\endgroup$
    – John K.
    Commented Sep 1, 2019 at 17:50
  • $\begingroup$ It's not a duplicate of the other question. I understand that the classes are equivalent. I am simply trying to understand why the common definition uses 1/3, rather than 1/4, 1/5, or just "some probability less than 1/2". I guess there just isn't a reason and it was the first number the author thought of? $\endgroup$
    – user97294
    Commented Sep 1, 2019 at 18:09

1 Answer 1

Reset to default
2
$\begingroup$

The constant $1/3$ is completely arbitrary. Let's say that $\mathsf{BPP}_p$ is the class of problems solvable in polytime with error at most $p$. Then $\mathsf{BPP}_p = \mathsf{BPP}_q$ for any $0 < p,q < 1/2$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you can boost the success probability by running the algorithm several times and take a majority vote (details left to you).

Why do we like $1/3$, then? It's the "simplest" rational number in $(0,1/2)$: for example, it is the rational number in $(0,1/2)$ with the minimal possible denominator, and with the minimal sum of numerator and denominator.

Improve this answer
$\endgroup$

Your Answer

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