Difficulty: Intermediate to Advanced | Prerequisites: P, NP, basic probability, randomised algorithms
RP and BPP are complexity classes that capture what can be solved efficiently with randomised algorithms. RP allows one-sided error (the algorithm can say "no" when it should say "yes", but never the reverse), while BPP allows two-sided error (small probability of being wrong in either direction). Proving these classes are closed under basic operations (union, intersection, complement) shows that combining randomised algorithms in natural ways still yields valid randomised algorithms. This matters because closure properties let you build complex randomised procedures from simpler ones without leaving the class.
RP captures problems solvable by efficient randomised algorithms with one-sided error; BPP allows two-sided error. Both are closed under union and intersection, and BPP is also closed under complement. The proofs rely on running independent copies of the underlying algorithms and combining their answers with AND/OR logic, then using probability amplification.
RP (Randomised Polynomial time)
The class of decision problems for which there exists a polynomial-time randomised algorithm that: (1) if x is a YES instance, accepts with probability at least 1/2; (2) if x is a NO instance, always rejects. Think of it as: the algorithm might miss a yes, but it never gives a false positive.
coRP
The complement of RP. A polynomial-time randomised algorithm that: (1) if x is a YES instance, always accepts; (2) if x is a NO instance, rejects with probability at least 1/2. The mirror image: no false negatives, but possible false positives.
BPP (Bounded-error Probabilistic Polynomial time)
The class of decision problems for which there exists a polynomial-time randomised algorithm that answers correctly with probability at least 2/3 on every input (both YES and NO instances). Think of it as: the algorithm is usually right, and you can make it almost certainly right by repeating and taking a majority vote.
One-sided error
The type of error in RP: the algorithm can err in only one direction (false negatives in RP, false positives in coRP).
Two-sided error
The type of error in BPP: the algorithm can err on both YES and NO instances, but with bounded probability.
Closure under an operation
A complexity class C is closed under an operation (union, intersection, complement) if applying that operation to languages in C always produces another language in C. In simple terms, combining problems from the class using that operation keeps you inside the class.
Probability amplification
The technique of running a randomised algorithm multiple independent times and combining the results (majority vote, AND, OR) to reduce the error probability. This is the core tool for all the closure proofs.
RP is closed under union
Let L_1, L_2 be in RP with algorithms A_1, A_2. To decide L_1 union L_2:
Run A_1(x) and A_2(x).
Accept if either accepts; reject if both reject.
Correctness:
If x is in L_1 union L_2, then x is in at least one of L_1, L_2. The corresponding algorithm accepts with probability at least 1/2, so the combined algorithm accepts with probability at least 1/2.
If x is not in L_1 union L_2, then x is in neither, so both A_1 and A_2 always reject. The combined algorithm always rejects.
This preserves the one-sided error property.
RP is closed under intersection
To decide L_1 intersect L_2:
Run A_1(x) and A_2(x).
Accept if both accept; reject if either rejects.
Correctness:
If x is in L_1 intersect L_2, both A_1 and A_2 accept with probability at least 1/2 each. Since they use independent randomness, both accept with probability at least 1/4. (To boost this to 1/2, run each algorithm twice and accept if it ever accepts, then AND the results.)
If x is not in L_1 intersect L_2, then x is not in at least one of L_1, L_2. That algorithm always rejects, so the combined algorithm always rejects.
BPP is closed under union
First amplify: run each BPP algorithm O(k) times and take a majority vote to reduce error to 2^(-k). Then:
Run amplified A_1(x) and amplified A_2(x).
Accept if either accepts.
With error amplified to, say, 1/6 each, the probability both are wrong simultaneously is at most 1/6 + 1/6 = 1/3 by the union bound, keeping overall error at most 1/3.
BPP is closed under intersection
Same amplification strategy, then accept only if both accept. Union bound on the error probabilities keeps the total under 1/3.
BPP is closed under complement
If A is a BPP algorithm for L (correct with probability at least 2/3), then flipping A's output gives a BPP algorithm for the complement of L. If A accepts, reject; if A rejects, accept. The error probability stays exactly the same.
This is the key difference from RP: flipping an RP algorithm's output does not give an RP algorithm (it gives a coRP algorithm instead), so RP is not known to be closed under complement.
Bonus: if NP is a subset of BPP, then NP = RP
The argument sketch: if NP is in BPP, then for any NP language L with verifier V, you can use the BPP algorithm to derandomise the search for a witness. The BPP algorithm tells you (with high probability) whether a witness exists, and you can then use it bit-by-bit to construct the witness, building an RP algorithm. The formal proof uses the self-reducibility of NP-complete problems and probability amplification.
Students often assume RP is closed under complement. It is not (or at least, this is not known). Flipping an RP algorithm's answer gives coRP, not RP, because the error direction reverses.
Students confuse the error bounds for RP and BPP. In RP, the 1/2 bound is on false negatives only (no false positives). In BPP, the 2/3 bound applies to all inputs.
When proving closure under intersection for RP, students sometimes claim the combined acceptance probability is (1/2)(1/2) = 1/4 and stop there. This is below the required 1/2 threshold. You need to amplify first (run each algorithm a constant number of times) or note that 1/4 can be boosted.
For BPP closure proofs, students forget to amplify before combining. If you OR two BPP algorithms with error 1/3 each, the union bound gives error up to 2/3, which is too high. Amplify to error 1/6 first.
Closure proofs for RP and BPP are a staple exam topic. Know the proof structure: amplify if needed, combine with AND/OR, check error bounds.
The asymmetry between RP and BPP regarding complement closure is a common short-answer or true/false question.
Understanding why you need independent randomness for each algorithm call is important. If they share randomness, the analysis breaks.
The relationship P is a subset of RP is a subset of BPP is commonly tested. Know where each class sits and why.
True or False: RP is closed under complement. (False, or at least not known to be.)
True or False: BPP is closed under complement. (True.)
Fill in the blank: To prove RP closure under union, accept if ____ of the sub-algorithms accepts. (either / at least one)
True or False: P is a subset of RP is a subset of BPP. (True.)
Fill in the blank: Before combining two BPP algorithms with OR, you should first ____ to reduce each algorithm's error. (amplify / run multiple times and take majority vote)
Q: Prove that RP is closed under union.
A: Given RP algorithms A_1 for L_1 and A_2 for L_2, define algorithm A that runs both and accepts if either accepts. If x is in L_1 union L_2, at least one algorithm accepts with probability >= 1/2, so A accepts with probability >= 1/2. If x is in neither, both always reject, so A always rejects. A runs in polynomial time since both sub-algorithms do.
Q: Prove that BPP is closed under complement.
A: Given a BPP algorithm A for L that is correct with probability >= 2/3, define A' that runs A and flips the output. On YES instances of the complement (i.e. NO instances of L), A rejects with probability >= 2/3, so A' accepts with probability >= 2/3. On NO instances of the complement (i.e. YES instances of L), A accepts with probability >= 2/3, so A' rejects with probability >= 2/3. A' is a valid BPP algorithm for the complement of L.
Q: Why is the RP intersection proof trickier than the union proof?
A: For intersection, you AND the two algorithms. If x is in L_1 intersect L_2, each accepts with probability >= 1/2 independently, so both accept with probability >= 1/4. This is below the 1/2 threshold required by RP. You need to amplify each algorithm first (run each k times, accept if any run accepts) to get acceptance probability close to 1, then AND the amplified versions. The no-instance case is clean: if x is missing from either language, that algorithm always rejects, so the AND always rejects.
Q: Why can you not just flip an RP algorithm to get closure under complement?
A: An RP algorithm for L has the property: never accepts a NO instance, but may reject a YES instance with probability up to 1/2. Flipping the output gives: never rejects a YES instance, but may accept a NO instance with probability up to 1/2. This is coRP, not RP. The error has moved from false negatives to false positives, which violates the RP definition.
RP and BPP sit between P and NP in the complexity hierarchy. The Chernoff bound material from this same homework is the engine behind probability amplification, which powers all of these closure proofs. The random graph problems also use randomised estimation, illustrating how these theoretical classes connect to practical algorithm design.
BPP's closure under complement is sometimes contrasted with the open question of whether NP is closed under complement (which would imply NP = coNP).
RP, coRP, BPP, ZPP, PP, randomised polynomial time, bounded-error probabilistic polynomial, one-sided error, two-sided error, closure properties, probability amplification, majority vote, union bound, complexity classes, EECS 376, Foundations of Computer Science, University of Michigan