A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A probabilistic Turing machine has access to random coin flips at each step. BPP (bounded-error probabilistic polynomial time) is the class of problems solvable by a polynomial-time PTM that errs with probability at most 1/3 on every input — either direction. Error amplification by repeated independent trials shows the specific threshold 1/3 is arbitrary; any constant less than 1/2 defines the same class. Most researchers believe BPP = P (randomness does not help asymptotically), supported by hardness-vs-randomness connections in derandomization theory, though this is unproven.
Study concrete randomized algorithms first: Miller-Rabin primality testing and Schwartz-Zippel polynomial identity testing. Understand the error-amplification argument (majority vote over independent trials) to see why the error bound is flexible. Then compare BPP to NP: in NP, a single witness suffices for acceptance; in BPP, a majority of random paths must accept.
Randomness is a computational resource, just like time and space. A probabilistic Turing machine (PTM) is like an ordinary Turing machine except that at each step it can flip a fair coin and branch on the result. This introduces a new question: when we say a PTM 'solves' a problem, what do we mean? Because of randomness, the machine might give different answers on the same input at different times. BPP formalizes the most practical answer: a PTM solves a problem in BPP if it runs in polynomial time and gives the correct answer with probability at least 2/3 on every input — meaning the error probability is at most 1/3.
The error bound of 1/3 is a convention, not a fundamental constant. The key insight is error amplification: run the algorithm independently k times and output the majority vote. By the Chernoff bound — a powerful concentration inequality from probability theory — the probability that a majority of k independent runs are wrong decreases exponentially in k. With only a few dozen extra runs, you can reduce the error from 1/3 to 2-100. This shows that any constant error bound strictly below 1/2 defines the same class BPP, because any such algorithm can be amplified to meet any stricter error requirement while still running in polynomial time.
A critical distinction is between BPP and NP. In NP, existence of a single witness (a short certificate) is enough for acceptance — you only need one good path. In BPP, a strict majority of computation paths must be correct: on a yes-instance, at least 2/3 of random choices lead to acceptance, and on a no-instance, at least 2/3 lead to rejection. BPP is symmetric about errors in both directions; NP is not. It is unknown whether NP ⊆ BPP, though most complexity theorists believe they are incomparable.
The error probability in BPP is always over the algorithm's own random choices — not over inputs. For every fixed input, the algorithm is correct with high probability. This means there is no 'worst case' input that the randomness fails to handle; the guarantee is uniform across all inputs. Contrast this with average-case analysis, where an algorithm might succeed on most inputs but fail badly on a few.
Most researchers conjecture that BPP = P — that randomness provides no asymptotic advantage over determinism. This conjecture is supported by hardness-vs-randomness tradeoffs: if certain circuit lower bounds hold, then any BPP algorithm can be derandomized into a deterministic polynomial-time algorithm. Practical randomized algorithms like Miller-Rabin primality testing (which tests primality probabilistically in polynomial time) were historically important because no deterministic polynomial-time algorithm was known — though AKS (2002) eventually provided one, consistent with the BPP = P belief.