This page provides all possible meanings and translations of the word BPP
FreebaseRate this definition:(0.00 / 0 votes)
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.
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.
Find a translation for the BPP definition in other languages: