Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
BPP (complexity)
Summary
In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances.
BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.
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.
A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that
M runs for polynomial time on all inputs
For all x in L, M outputs 1 with probability greater than or equal to 2/3
For all x not in L, M outputs 1 with probability less than or equal to 1/3
Unlike the complexity class ZPP, the machine M is required to run for polynomial time on all inputs, regardless of the outcome of the random coin flips.
Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic Turing machine M, such that
M runs for polynomial time on all inputs
For all x in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is greater than or equal to 2/3
For all x not in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is less than or equal to 1/3
In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.