BPP (complexity)
In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances.
| BPP algorithm (1 run) | ||
|---|---|---|
| Answer produced | ||
| Correct answer |
YES | NO |
| YES | ≥ 2/3 | ≤ 1/3 |
| NO | ≤ 1/3 | ≥ 2/3 |
| BPP algorithm (k runs) | ||
| Answer produced | ||
| Correct answer |
YES | NO |
| YES | > 1 − 2−ck | < 2−ck |
| NO | < 2−ck | > 1 − 2−ck |
| for some constant c > 0 | ||
Informally, a problem is in BPP if there is an algorithm for it that has the following properties:
- It is allowed to flip coins and make random decisions
- It is guaranteed to run in polynomial time
- On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer, whether the answer is YES or NO.
Read more about BPP (complexity): Introduction, Definition, Problems, Related Classes, Complexity-theoretic Properties, Derandomization