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 sentenceQuote, 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
Reader 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.