／var／logmarcus chiu

BPP (Bounded-Error Probabilistic Polynomial Time)

Created on

BPP (Bounded-Error Probabilistic Polynomial Time)
  • BPP is a type of complexity 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

Resources