BPP, RP, ZPP: Randomized Algorithms

1977. Michael Rabin publishes a primality test. The randomized algorithm checks a 1024-bit RSA number in 10 milliseconds with error probability below $2^{-128}$. A deterministic algorithm with the same guarantee would take longer than the age of the universe. Every time a browser opens an HTTPS connection - somewhere this test runs. Randomization is not a hack. It is a separate computational class with its own theory.

• Miller-Rabin in OpenSSL and BoringSSL: RSA key generation at every TLS handshake
• Randomized quicksort in C++ STL, Python, Java - expected O(n log n) with no sorted-input degradation
• Monte Carlo Tree Search in AlphaGo/AlphaZero: random rollouts evaluating millions of positions
• Randomized SVD in scikit-learn: PCA on 10^6 x 10^4 matrices in seconds instead of hours
• Bloom filter in Redis, Cassandra, Chrome Safe Browsing: probabilistic structure in the RP spirit

Monte Carlo vs Las Vegas: two different trade-offs

1977. Gary Miller proposes a primality test based on the Riemann hypothesis. Michael Rabin removes the hypothesis and makes it randomized. Result: a 1024-bit RSA number checked in 10 milliseconds with error probability below $2^{-128}$. A deterministic algorithm with the same guarantee would require time comparable to the age of the universe. Every HTTPS handshake on the internet runs on this trade-off.

Randomized algorithms flip coins during execution. This is not an optimization - it is a different computational model. A Turing machine receives an extra tape of random bits it can read at any point. Two fundamentally different approaches to error split the domain of randomized algorithms.

Randomized quicksort is the canonical Las Vegas algorithm. The pivot is chosen randomly, but the sort is always correct. Expected time $O(n \log n)$; worst case $O(n^2)$ occurs with probability $2^{-n}$ under random pivot selection. The standard library in C++, Python, and Java uses exactly this variant.

Monte Carlo Tree Search in AlphaGo is a different archetype. Random rollouts evaluate positions: the algorithm looks at thousands of random game endings and averages. No optimality guarantee per move, but the statistics converge. This is how AlphaGo beat Lee Sedol in 2016 - deterministic minimax cannot cope with the branching factor of Go.

**Amplification:** the 1/3 error threshold in BPP is an arbitrary constant. Running the algorithm $k$ times and taking a majority vote drives the error down to $2^{-\Omega(k)}$. After 100 runs the error is roughly $2^{-100}$. This is free in terms of asymptotic complexity.

BPP, RP, coRP, ZPP: taxonomy of probabilistic classes

Four main probabilistic classes are ordered by the type of error they permit. The tightest is **ZPP** (Zero-error Probabilistic Polynomial time): always correct, expected polynomial time. ZPP = RP $\cap$ coRP - a beautiful fact provable in three lines.

**RP** (Randomized Polynomial time) permits one-sided error: if $x \in L$ - the algorithm says YES with probability $\geq 1/2$; if $x \notin L$ - it says NO with certainty. No false positives on the NO side.

**coRP** is symmetric: YES-inputs are identified exactly, NO-inputs with probability $\geq 1/2$. Miller-Rabin sits in coRP: prime numbers are always called prime, composite numbers are exposed with probability $\geq 3/4$. **BPP** is the most permissive: two-sided error $\leq 1/3$ on any input.

**ZPP = RP ∩ coRP:** given an RP algorithm for L and a coRP algorithm for the complement of L, run them alternately. When one gives a definitive answer - stop. Expected time is polynomial, errors are zero. That is ZPP.

RP $\subseteq$ NP is direct: a nondeterministic machine guesses the random bits that led to YES. The converse is unknown. P $\subseteq$ ZPP $\subseteq$ RP $\subseteq$ BPP - a chain of inclusions, none of which is known to be strict. This is the central open question of derandomization.

Derandomization: can the coin be removed?

The central conjecture: **BPP = P**. If true, randomness provides no advantage - every randomized algorithm can be simulated deterministically in polynomial time. If false, there exist problems where a coin flip genuinely speeds up computation. No answer exists in either direction.

Adleman's theorem (1978): BPP $\subseteq$ P/poly. For each input length $n$, there exists a polynomial-size 'advice' string with which the problem is solvable deterministically. The catch: the advice depends on $n$ and cannot be computed efficiently. P/poly contains undecidable problems - this is not polynomial time in the usual sense.

**Pseudorandom Generators (PRGs)** - the main tool for derandomization. A PRG stretches a short seed of length $O(\log n)$ into a string of length $n$ that is computationally indistinguishable from truly random for any bounded-size algorithm. Enumerating all $2^{O(\log n)} = \text{poly}(n)$ seeds deterministically runs in polynomial time.

Impagliazzo-Wigderson theorem (1997): if functions exist that are computable in $2^{O(n)}$ time but require circuits of size $2^{\Omega(n)}$ - then BPP = P. In other words: if 'hard' functions exist, PRGs can be built from them and derandomization follows. This reduces BPP = P to a circuit lower bound question - equally open.

In ML, randomness is everywhere - and it gets derandomized too. Dropout at inference is replaced by weight scaling (a deterministic approximation of the Monte Carlo expectation). Randomized SVD in scikit-learn uses a PRG with a fixed seed for reproducibility. Mini-batch SGD is randomized, but batch order is fixed via `torch.manual_seed` - partial derandomization for experiment reproducibility.

The AKS algorithm (Agrawal-Kayal-Saxena, 2002) is a landmark: PRIMES $\in$ P. The first deterministic polynomial-time primality test. It derandomized Miller-Rabin in theory. In practice, AKS is slower than the randomized version - polynomial time does not imply fast constants. Miller-Rabin with 128 iterations remains the standard in OpenSSL, BoringSSL, and LibreSSL.

**Cryptographic counterpoint:** if BPP = P and PRGs exist, one-way functions must exist - and public-key cryptography rests on those. Complexity theory and cryptography are entangled more deeply than it seems: the open question about BPP is simultaneously a question about RSA security.

Connected topics

Probabilistic complexity classes intersect with probability theory, cryptography, and automata

• P vs NP — BPP and RP are intermediate classes between P and NP; derandomization conjecture BPP=P
• Bayes' Theorem — Error probability amplification mirrors iterative Bayesian updating
• Circuit Complexity — BPP ⊆ P/poly - connection to non-randomized polynomial-size circuits
• Cryptography — PRG <-> one-way functions: BPP=P is equivalent to the existence of OWFs

Итоги

• BPP - problems with two-sided error <= 1/3; amplification drives error to 2^{-k} in k runs
• RP - one-sided error (YES-inputs only); coRP - symmetric; ZPP = RP ∩ coRP (Las Vegas)
• P ⊆ ZPP ⊆ RP ⊆ BPP; RP ⊆ NP; no inclusion is known to be strict
• Derandomization conjecture BPP=P - equivalent to PRGs from functions with exponential circuit complexity
• AKS 2002: PRIMES ∈ P - theoretical derandomization of Miller-Rabin; slower in practice

Вопросы для размышления

• If BPP = P is proved, what does that mean for public-key cryptography? Must one-way functions exist in that world, and where does the boundary between 'random' and 'pseudorandom' lie from a computational standpoint?

Связанные уроки

• cplx-05 — L/NL as foundation for understanding computational resources
• cplx-01 — P and NP - base classes from which BPP and RP are defined
• prob-04-bayes — Bayesian update - iterative uncertainty reduction, same spirit as amplification
• alg-01-big-o — Probabilistic complexity analysis builds on top of O-notation
• fl-05-regex — Nondeterminism in automata - structural predecessor of randomization