Engineering / Mathematics — Probabilistic Algorithms
Language Recognition and Complexity Classes
Randomised complexity classes RP, co-RP, BPP and ZPP, and where primality testing sits among them.
Executive summary
Randomised complexity classes formalise the guarantees offered by probabilistic algorithms. The distinctions track exactly the one-sided and two-sided error cases.
Primality testing has moved through several of these classes historically, ending in P with the AKS algorithm.
Learning objectives
- Define RP, co-RP, BPP and ZPP.
- State the relationships between them.
- Place primality testing in this landscape.
01The classes
| Class | Yes instances | No instances |
|---|---|---|
| RP | Accepted with probability ≥ 1/2 | Always rejected |
| co-RP | Always accepted | Rejected with probability ≥ 1/2 |
| BPP | Accepted with probability ≥ 2/3 | Rejected with probability ≥ 2/3 |
| ZPP | Always correct, expected polynomial time | Always correct |
The specific constants are immaterial. Amplification shows that any advantage bounded away from the threshold by an inverse polynomial can be boosted to exponentially close to certainty, so the classes are robust to the choice.
02Relationships
P ⊆ ZPP = RP ∩ co-RP ⊆ RP ∪ co-RP ⊆ BPPThe identity ZPP = RP ∩ co-RP is the useful one. An algorithm with one-sided error in each direction can be run alternately until one gives a conclusive answer, yielding zero error in expected polynomial time.
03Primality testing through the classes
co-RP via Miller-Rabin
Composites are detected with probability at least 3/4; primes are never rejected. Compositeness is in RP, primality in co-RP.
ZPP via elliptic curve certificates
Primality proving methods produce verifiable certificates, placing primality in ZPP once combined with the co-RP test.
P via AKS
The 2002 AKS algorithm decides primality deterministically in polynomial time, settling the classification.
The practical situation is unchanged by the theoretical resolution. AKS is polynomial but with an exponent and constants far too large to compete, so every deployed system uses Miller–Rabin. The classification is of theoretical interest; the engineering choice was settled long before and has not moved.
04Frequently asked questions
Why is the RP threshold one half rather than something larger?
Because any inverse-polynomial advantage amplifies to arbitrarily close to one, so the threshold is a convention. One half is chosen for readability.
What does factoring being in NP and co-NP suggest?
That it is unlikely to be NP-complete, since an NP-complete problem in co-NP would collapse NP and co-NP, which is widely believed false. This is why factoring is regarded as intermediate in difficulty.
If BPP probably equals P, is randomness pointless?
Not at all. Derandomisation is about existence of deterministic algorithms, not their efficiency. The randomised algorithms remain dramatically faster in practice, and randomness is genuinely necessary in cryptography, where it provides unpredictability rather than speed.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 157-158.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.