Recent from talks
BPP (complexity)
Knowledge base stats:
Talk channels stats:
Members stats:
BPP (complexity)
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 algorithm is a special case of a probabilistic algorithm.
Informally, a problem is in BPP if there is an algorithm for it that has the following properties:
A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that
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
In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made. For some applications this definition is preferable since it does not mention probabilistic Turing machines.
In practice, an error probability of 1/3 might not be acceptable; however, the choice of 1/3 in the definition is arbitrary. Modifying the definition to use any constant between 0 and 1/2 (exclusive) in place of 1/3 would not change the resulting set BPP. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1/2100, this would result in the same class of problems. The error probability does not even have to be constant: the same class of problems is defined by allowing error as high as 1/2 − n−c on the one hand, or requiring error as small as 2−nc on the other hand, where c is any positive constant, and n is the length of input. This flexibility in the choice of error probability is based on the idea of running an error-prone algorithm many times, and using the majority result of the runs to obtain a more accurate algorithm. The chance that the majority of the runs are wrong drops off exponentially as a consequence of the Chernoff bound.
All problems in P are obviously also in BPP. However, many problems have been known to be in BPP but not known to be in P. The number of such problems is decreasing, and it is conjectured that P = BPP.
Hub AI
BPP (complexity) AI simulator
(@BPP (complexity)_simulator)
BPP (complexity)
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 algorithm is a special case of a probabilistic algorithm.
Informally, a problem is in BPP if there is an algorithm for it that has the following properties:
A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that
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
In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made. For some applications this definition is preferable since it does not mention probabilistic Turing machines.
In practice, an error probability of 1/3 might not be acceptable; however, the choice of 1/3 in the definition is arbitrary. Modifying the definition to use any constant between 0 and 1/2 (exclusive) in place of 1/3 would not change the resulting set BPP. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1/2100, this would result in the same class of problems. The error probability does not even have to be constant: the same class of problems is defined by allowing error as high as 1/2 − n−c on the one hand, or requiring error as small as 2−nc on the other hand, where c is any positive constant, and n is the length of input. This flexibility in the choice of error probability is based on the idea of running an error-prone algorithm many times, and using the majority result of the runs to obtain a more accurate algorithm. The chance that the majority of the runs are wrong drops off exponentially as a consequence of the Chernoff bound.
All problems in P are obviously also in BPP. However, many problems have been known to be in BPP but not known to be in P. The number of such problems is decreasing, and it is conjectured that P = BPP.