Bounded-error probabilistic polynomial time, the complexity class of decision problems solvable by a randomized algorithm running in polynomial time that answers correctly with probability strictly greater than one half on every input, and whose error can be reduced arbitrarily by repeated trials.
Facts
Core PrincipleThe class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. 1 Connections
Sources
1. BPP (complexity), Wikipedia
Lead section, first sentence
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
In Group: Space, Exponential Time and Probabilistic Classes, Lead
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.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.