47.03.01 · theoretical-cs / advanced-complexity

Randomized Complexity: BPP, RP, ZPP, and the Schwartz-Zippel Lemma

shipped3 tiersLean: none

Anchor (Master): Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §7.1-7.6 (BPP ⊆ P/poly, Sipser-Gacs-Lautemann theorem BPP ⊆ Σ₂ᵖ ∩ Π₂ᵖ, derandomisation conjectures)

Intuition Beginner

Sometimes flipping a coin helps. Imagine you are at a fork in a maze and do not know which way to go. If you choose randomly, you will eventually find the exit, even though any single guess might be wrong. Randomised algorithms work the same way: they make random choices during execution and have a small probability of giving the wrong answer, but by repeating the computation a few times, the error probability drops to nearly zero.

The class BPP (Bounded-error Probabilistic Polynomial time) contains every problem that can be solved by a randomised algorithm in polynomial time with error probability at most one third. Why one third? Because the exact constant does not matter: by running the algorithm a few dozen times and taking a majority vote, you can drive the error probability down to less than one in a billion.

Some problems have an even stronger guarantee. RP (Randomised Polynomial time) is the class of problems where the algorithm never says "yes" when the answer is "no" (no false positives), but it might say "no" when the answer is "yes" (a false negative) with probability at most one half. If the algorithm says "yes," you know the answer is correct. If it says "no," run it again.

The Schwartz-Zippel lemma is the workhorse of randomised algebra. It says: if you have two different multivariate polynomials, the chance that they agree at a random point is small. This lets you test whether two polynomials are identical by plugging in random values — a simple, fast, and highly effective strategy.

Visual Beginner

The relationships between randomised complexity classes:

P ⊆ ZPP ⊆ RP ⊆ BPP
              ⊆ coRP ⊆ BPP

ZPP = RP ∩ coRP  (zero-error, expected polynomial time)
RP:  one-sided error (no false positives)
coRP: one-sided error (no false negatives)
BPP: two-sided error (bounded in both directions)

Class	Error type	Guarantee	Example
ZPP	Zero error	Always correct, expected poly-time	Las Vegas algorithms
RP	One-sided	If yes, always correct; if no, may be wrong	Polynomial identity testing
BPP	Two-sided	Correct with probability $\geq 2/3$	Majority vote after repetition
P	No error	Always correct, worst-case poly-time	Deterministic algorithms

Worked example Beginner

You have two polynomials over the integers: $P (x, y) = (x + y)^{3}$ and $Q (x, y) = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}$ . Are they the same polynomial?

Expanding $P$ gives $x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}$ , which matches $Q$ . But what if $P$ and $Q$ had thousands of terms and expanding was impractical?

The Schwartz-Zippel lemma gives a shortcut. Pick random values for $x$ and $y$ , say $x = 7$ and $y = 3$ . Compute $P (7, 3) = 1000$ and $Q (7, 3) = 1000$ . They agree. But this could happen by coincidence even if $P \neq = Q$ .

The lemma says: if $P \neq = Q$ , then the probability that $P$ and $Q$ agree at a random point chosen from a set $S$ is at most $d /∣ S ∣$ , where $d$ is the degree. Here $d = 3$ . If we pick $x, y$ from ${1, 2, \dots, 100}$ , the error probability is at most $3/100 = 3%$ .

Repeat with new random values. After $k$ independent tests, the error drops to at most $(3/100)^{k}$ . After 5 tests, the error is less than one in two million. This is polynomial identity testing — a fast, practical randomised algorithm for a fundamental algebraic question.

Check your understanding Beginner

Formal definition Intermediate+

A probabilistic Turing machine (PTM) is a Turing machine with access to a coin-flip tape: at each step, the machine can read the next bit from a tape initialised with independent uniform random bits. The output of a PTM on input $x$ is a random variable.

Definition (BPP). A language $L \in BPP$ if there exists a polynomial-time PTM $M$ such that for all $x$ :

Pr [M (x) = L (x)] \geq \frac{2}{3},

where $L (x) = 1$ if $x \in L$ and $L (x) = 0$ otherwise. The probability is over the random bits of $M$ .

Definition (RP). A language $L \in RP$ if there exists a polynomial-time PTM $M$ such that for all $x$ :

If $x \in L$ : $Pr [M (x) = 1] \geq \frac{1}{2}$ .
If $x \in / L$ : $Pr [M (x) = 1] = 0$ .

Definition (coRP). $L \in coRP$ iff $\overline{L} \in RP$ .

Definition (ZPP). $ZPP = RP \cap coRP$ . Equivalently, $L \in ZPP$ iff there exists an expected-polynomial-time PTM $M$ that never errs: $M$ either outputs the correct answer or outputs a special "don't know" symbol $⊥$ , and the probability of $⊥$ is at most $1/2$ .

Lemma (Schwartz-Zippel). Let $P \in F [x_{1}, \dots, x_{n}]$ be a nonzero polynomial of total degree $d$ over a field $F$ . Let $S \subseteq F$ be a finite subset. Then:

r_{1}, \dots, r_{n} \in S Pr [P (r_{1}, \dots, r_{n}) = 0] \leq \frac{d}{∣ S ∣} .

Each $r_{i}$ is chosen independently and uniformly from $S$ ^{[Arora & Barak §7.3]}.

Counterexamples to common slips

"BPP means the algorithm is correct with probability at least 2/3, which is too weak for practice." Error reduction by repetition drives the error probability to $2^{- k}$ with $O (k)$ repetitions. Any desired confidence level is achievable with modest overhead.
"RP algorithms have 50 percent error rate." The error is one-sided and only on "yes" instances. On "no" instances the algorithm is always correct. By repetition, the false-negative rate drops to $2^{- k}$ .
"Schwartz-Zippel requires the field to be finite." The lemma works over any field. The random evaluation points must come from a finite subset $S$ , but the polynomial itself can live over $Q$ , $R$ , or any field.

Key theorem with proof Intermediate+

Theorem (Schwartz-Zippel lemma). Let $P \in F [x_{1}, \dots, x_{n}]$ be nonzero of total degree $d$ . Then for $r_{1}, \dots, r_{n}$ chosen independently and uniformly from $S \subseteq F$ : $Pr [P (r_{1}, \dots, r_{n}) = 0] \leq d /∣ S ∣$ .

Proof. By induction on $n$ . Base case $n = 1$ : a nonzero univariate polynomial of degree $d$ has at most $d$ roots, so $Pr [P (r_{1}) = 0] \leq d /∣ S ∣$ .

Inductive step: write $P = \sum_{i = 0}^{k} x_{1}^{i} \cdot Q_{i} (x_{2}, \dots, x_{n})$ where $Q_{k} \neq = 0$ and $k \leq d$ . Then:

Pr [P (r_{1}, \dots, r_{n}) = 0] \leq Pr [Q_{k} (r_{2}, \dots, r_{n}) = 0] + Pr [P (r_{1}, \dots, r_{n}) = 0 ∣ Q_{k} (r_{2}, \dots, r_{n}) \neq = 0] .

By the inductive hypothesis, $Pr [Q_{k} = 0] \leq (d - k) /∣ S ∣$ . Conditioned on $Q_{k} \neq = 0$ , the polynomial $P (r_{1}, \dots)$ is a nonzero polynomial in $x_{1}$ of degree $k$ , so $Pr [P = 0 ∣ Q_{k} \neq = 0] \leq k /∣ S ∣$ . Adding: $(d - k) /∣ S ∣ + k /∣ S ∣ = d /∣ S ∣$ . $□$

Bridge. The Schwartz-Zippel lemma is the foundational reason polynomial identity testing (PIT) is in coRP: two distinct polynomials can agree at a random point only with low probability, so disagreement at a random point is a reliable certificate of difference. This builds toward the derandomisation programme in 47.05.01, where universal hash families use a similar probabilistic argument for load balancing, and it appears again in 47.05.03 where Miller-Rabin primality testing applies the same error-reduction-by-repetition strategy. The central insight is that random evaluation converts an algebraic identity question into a numeric computation, and putting these together with Chernoff-bound amplification gives a practical, highly reliable randomised algorithm.

Exercises Intermediate+

Exercise 6 (medium, short answer).

Prove that $ZPP = RP \cap coRP$ .

Hint

$ZPP \subseteq RP$ : run the ZPP machine and treat $⊥$ as "no." $RP \cap coRP \subseteq ZPP$ : run both the RP and coRP machines.

Answer

$ZPP \subseteq RP$ : Given a ZPP machine $M$ for $L$ , define an RP machine $M^{'}$ that runs $M$ and outputs "yes" if $M$ outputs "yes," outputs "no" if $M$ outputs "no" or $⊥$ . Then $x \in / L \Rightarrow M^{'}$ never outputs "yes" (since $M$ never errs), and $x \in L \Rightarrow M^{'}$ outputs "yes" with probability $\geq 1/2$ (since $Pr [M = ⊥] \leq 1/2$ ). Similarly $ZPP \subseteq coRP$ .

$RP \cap coRP \subseteq ZPP$ : Given $M_{RP}$ for $L$ and $M_{coRP}$ for $\overline{L}$ , run both. If $M_{RP}$ says "yes," output "yes" (correct by RP guarantee). If $M_{coRP}$ says "yes" (meaning $x \in / L$ ), output "no" (correct by coRP guarantee). If both say "no," output $⊥$ . The probability of $⊥$ is at most $1/4$ (both fail to recognise their side) by the union bound, so the expected running time is polynomial.

Exercise 7 (hard, short answer).

Prove the error-reduction theorem for BPP: if $L \in BPP$ , then for every polynomial $p$ , there exists a BPP machine for $L$ with error at most $2^{- p (n)}$ .

Hint

Run the original BPP machine $k = O (p (n))$ times and take the majority vote. Apply the Chernoff bound.

Answer

Let $M$ be a BPP machine for $L$ with error $1/3$ . Run $M$ independently $k$ times on input $x$ , producing outputs $Y_{1}, \dots, Y_{k} \in {0, 1}$ . Let $Y = \sum Y_{i}$ and output the majority (1 if $Y > k /2$ , else 0). If the correct answer is 1, each $Y_{i} = 1$ with probability $\geq 2/3$ , so $E [Y] \geq 2 k /3$ . The error (outputting 0) requires $Y \leq k /2$ , a deviation of $\geq k /6$ from the mean. By the Chernoff bound: $Pr [Y \leq k /2] \leq e^{- 2 k (1/6)^{2}} = e^{- k /18}$ . Setting $k = 18 p (n) ln 2$ gives error $\leq 2^{- p (n)}$ . The running time is $O (k \cdot T_{M} (n))$ , polynomial. Rubric: full credit for the Chernoff-bound calculation and the choice of $k$ .

Lean formalization Intermediate+

Mathlib has basic probability infrastructure (Probability.ProbabilityMassFunction) but no probabilistic Turing machine model or complexity class definitions for BPP, RP, or ZPP. The Chernoff bound for error amplification and the Schwartz-Zippel lemma for polynomial identity testing are absent. A Codex.Complexity.BPP module defining BPP via polynomial-bounded PTM computations with error reduction would be the foundational step; this unit ships without it.

Advanced results Master

Three structural results sharpen the relationship between randomised and deterministic computation.

Theorem 1 (BPP $\subseteq$ P/poly). Every language in BPP has polynomial-size circuits ^{[Arora & Barak §7.5]}. The proof uses the probabilistic method: a BPP machine $M$ uses $m$ random bits, and there are $2^{m}$ possible random strings. By averaging, for every input $x$ of length $n$ , at most $2^{m} /3$ random strings cause $M$ to err. A counting argument shows there exists a fixed set of $O (n)$ random strings (an "advice" string) that works for all inputs of length $n$ ; this advice string defines a polynomial-size circuit.

Theorem 2 (Sipser-Gacs-Lautemann: BPP $\subseteq Σ_{2}^{p} \cap Π_{2}^{p}$ ). BPP is contained in the second level of the polynomial hierarchy ^{[Arora & Barak §7.6]}. The proof uses the pairwise independence hashing technique: the acceptance condition of a BPP machine can be expressed as a $Σ_{2}$ predicate ("there exist shifts such that for all inputs, the majority of shifted random strings give the correct answer"). This places BPP inside the polynomial hierarchy and suggests that randomisation does not add much power beyond determinism, assuming the polynomial hierarchy does not collapse.

Theorem 3 (derandomisation conjectures). Several hardness-vs-randomness tradeoffs relate derandomisation to circuit lower bounds. The Impagliazzo-Wigderson theorem (1997) shows that if there exists a language in E = DTIME( $2^{O (n)}$ ) that requires exponential-size circuits, then BPP = P. The proof constructs a pseudorandom generator from the hard language, whose output is indistinguishable from truly random bits by any polynomial-time algorithm. This is the strongest evidence that BPP = P: it reduces the question to a (plausible) circuit lower bound ^{[Arora & Barak §7.5]}.

Synthesis. The randomised complexity classes BPP, RP, and ZPP are the foundational reason randomised algorithms are practical: error reduction via repetition drives the failure probability to negligible levels, and the Schwartz-Zippel lemma provides a general-purpose randomised test for algebraic identities. The central insight is that randomness is a resource that, like time and space, can be quantified and controlled, and putting these together with the Sipser-Gacs-Lautemann theorem places BPP inside the polynomial hierarchy of 47.02.04, suggesting randomisation does not add fundamental power. This builds toward the derandomisation programme of 47.05.01, where universal hash families replace true randomness with structured pseudorandom objects, and appears again in 47.05.03 where Miller-Rabin primality testing demonstrates a natural problem in BPP (and now in P, after AKS 2002).

Full proof set Master

Proposition 1 (error reduction for BPP). If $L \in BPP$ , then for every constant $c > 0$ there is a BPP machine for $L$ with error at most $c$ .

Proof. Let $M$ have error $1/3$ . Run $M$ independently $k$ times and take the majority. Let $X_{i}$ be the indicator of correct output on run $i$ . Each $X_{i}$ has $E [X_{i}] \geq 2/3$ and the $X_{i}$ are independent. The majority errs iff $\sum X_{i} \leq k /2$ , a deviation of $\geq k /6$ below the mean $μ \geq 2 k /3$ . By the Chernoff bound: $Pr [\sum X_{i} \leq k /2] \leq e^{- 2 (k /6)^{2} / k} = e^{- k /18}$ . For $k \geq 18 ln (1/ c)$ , the error is at most $c$ . $□$

Proposition 2 (Schwartz-Zippel, full proof by induction). Let $P \neq = 0$ have total degree $d$ . Then $Pr_{r \in S^{n}} [P (r) = 0] \leq d /∣ S ∣$ .

Proof. Induction on $n$ . For $n = 1$ , a univariate polynomial of degree $d$ has at most $d$ roots, so $Pr \leq d /∣ S ∣$ . For $n > 1$ , write $P = \sum_{i = 0}^{k} x_{1}^{i} Q_{i} (x_{2}, \dots, x_{n})$ with $Q_{k} \neq = 0$ , $de g (Q_{k}) \leq d - k$ . Then:

Pr [P (r) = 0] = Pr [Q_{k} = 0] + Pr [P = 0 ∣ Q_{k} \neq = 0] \cdot Pr [Q_{k} \neq = 0] \leq \frac{d - k}{∣ S ∣} + \frac{k}{∣ S ∣} \cdot 1 = \frac{d}{∣ S ∣},

where $Pr [Q_{k} = 0] \leq (d - k) /∣ S ∣$ by induction and $Pr [P = 0 ∣ Q_{k} \neq = 0] \leq k /∣ S ∣$ by the univariate case applied to $P$ as a polynomial in $x_{1}$ with coefficients evaluated at $r_{2}, \dots, r_{n}$ . $□$

Connections Master

37.01.01 — Probability spaces and discrete distributions provide the mathematical foundation for defining the error probabilities of BPP, RP, and ZPP machines; independence of random bits is a key assumption.
47.02.01 — P and NP are the deterministic analogues against which the randomised classes are measured; the containment $P \subseteq BPP$ and the conjecture $BPP = P$ frame the role of randomisation.
47.02.04 — The polynomial hierarchy $Σ_{k}^{p}$ contains BPP by the Sipser-Gacs-Lautemann theorem, placing randomised computation within the structural framework of alternation.
47.05.01 — Universal hashing and perfect hashing use the probabilistic method to construct deterministic data structures; the underlying argument is the same "most random choices are good" principle.
47.05.03 — Miller-Rabin primality testing is a landmark RP/coRP algorithm; its error analysis relies on the same amplification techniques developed here.

Historical & philosophical context Master

Randomised algorithms entered computational complexity through the work of Michael Rabin (1976) and Robert Solovay and Volker Strassen (1977), who independently discovered randomised primality tests. Rabin's paper "Probabilistic Algorithm for Testing Primality" introduced the concept of a probabilistic algorithm with bounded one-sided error (the class RP), and the Solovay-Strassen test provided an alternative with similar guarantees ^{[Arora & Barak §7.1]}.

The class BPP was formally defined by John Gill (1977) in his paper "Computational Complexity of Probabilistic Turing Machines." The Schwartz-Zippel lemma was discovered independently by Jack Schwartz (1980) and Richard Zippel (1979). Schwartz's paper "Fast Probabilistic Algorithms for Verification of Polynomial Identities" established the lemma for multivariate polynomials over arbitrary fields and used it for polynomial identity testing.

The Sipser-Gacs-Lautemann theorem (1983) showed that BPP resides in the polynomial hierarchy, providing the first evidence that randomisation does not dramatically increase computational power. The Impagliazzo-Wigderson theorem (1997) strengthened this by showing that BPP = P under plausible hardness assumptions, essentially reducing derandomisation to circuit lower bounds.

Bibliography Master

@book{arora-barak2009,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{rabin1976probabilistic,
  author  = {Rabin, Michael O.},
  title   = {Probabilistic Algorithm for Testing Primality},
  journal = {Journal of Number Theory},
  volume  = {12},
  number  = {1},
  pages   = {128--138},
  year    = {1980},
  note    = {First presented at the 1976 Carnegie Mellon conference},
}
@article{schwartz1980fast,
  author  = {Schwartz, Jacob T.},
  title   = {Fast Probabilistic Algorithms for Verification of Polynomial Identities},
  journal = {Journal of the ACM},
  volume  = {27},
  number  = {4},
  pages   = {701--717},
  year    = {1980},
}
@article{zippel1979probabilistic,
  author  = {Zippel, Richard},
  title   = {Probabilistic Algorithms for Sparse Polynomials},
  journal = {Proceedings of the International Symposium on Symbolic and Algebraic Computation},
  pages   = {216--226},
  year    = {1979},
}
@article{gill1977computational,
  author  = {Gill, John},
  title   = {Computational Complexity of Probabilistic Turing Machines},
  journal = {SIAM Journal on Computing},
  volume  = {6},
  number  = {4},
  pages   = {675--695},
  year    = {1977},
}

Prerequisites

47.02.01
37.01.01

Tier anchors

beginner: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §7.1 (randomised algorithms as flipping coins to make decisions, polynomial identity testing)
intermediate: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §7.1-7.4 (BPP, RP, ZPP definitions, error reduction via amplification, the Schwartz-Zippel lemma for polynomial identity testing)
master: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §7.1-7.6 (BPP ⊆ P/poly, Sipser-Gacs-Lautemann theorem BPP ⊆ Σ₂ᵖ ∩ Π₂ᵖ, derandomisation conjectures)

References

Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Section 7.1 defines probabilistic Turing machines and the classes $BPP = {L : \exists poly-time PTM M, \forall x, Pr [M (x) = L (x)] \geq 2/3}$ (bounded-error probabilistic polynomial time), $RP = {L : \exists poly-time PTM M, x \in L \Rightarrow Pr [M (x) = 1] \geq 1/2, x \in / L \Rightarrow Pr [M (x) = 1] = 0}$ (one-sided error), and $ZPP = RP \cap coRP$ (zero-error, expected polynomial time). Section 7.2 proves error reduction by repetition: $k$ independent runs reduce the error from $1/3$ to $2^{- Ω (k)}$ via the Chernoff bound. Section 7.3 proves the Schwartz-Zippel lemma: for a nonzero multivariate polynomial $P \in F [x_{1}, \dots, x_{n}]$ of total degree $d$ and a finite subset $S \subseteq F$ , $Pr_{r_{1}, \dots, r_{n} \in S} [P (r_{1}, \dots, r_{n}) = 0] \leq d /∣ S ∣$ .

Estimated time

beginner: 15m
intermediate: 40m
master: 75m