The Miller-Rabin primality test has the property: if it declares a number composite, it is definitely composite; if it declares a number prime, there is a small chance it is actually composite. Which complexity class does this algorithm belong to?
ARP — the algorithm allows false positives (claiming prime when composite) but never false negatives
BcoRP — the algorithm has no false negatives (composite → always says composite) but allows false positives
CBPP — the algorithm has two-sided error with error probability below 1/2
DP — primality testing is known to run in deterministic polynomial time
The Miller-Rabin test is a coRP algorithm. coRP requires: if the true answer is 'yes' (the number is prime), always output 'yes' — no false negatives. But if the true answer is 'no' (the number is composite), you might incorrectly output 'yes' — false positives allowed. Miller-Rabin satisfies exactly this: it never calls a composite number prime (no false negatives), but it might rarely call a composite number prime (false positives possible). This makes it coRP, not RP (which is the mirror: no false positives, possible false negatives).
Question 2 Multiple Choice
An RP algorithm runs on input x and outputs 'yes'. What can you conclude with certainty?
Ax is definitely in the language — RP never produces false positives
Bx is probably in the language — there is at most a 1/2 chance of a false positive
CNothing conclusive — RP allows both false positives and false negatives
Dx might not be in the language — you should run the algorithm again to confirm
RP has one-sided error: if x ∉ L (x is not in the language), the algorithm always rejects — never producing a false positive. Therefore, if the algorithm says 'yes,' x must be in the language. This is the key practical value of RP: a 'yes' answer is unconditionally trustworthy, while a 'no' might be a false negative (the algorithm might have missed a real 'yes' with probability ≤ 1/2). This asymmetry — trust the positive but not the negative — is precisely what distinguishes RP from BPP, where neither answer can be trusted unconditionally.
Question 3 True / False
Running an RP algorithm k times and accepting if any single run returns 'yes' reduces the probability of a false negative to at most (1/2)^k.
TTrue
FFalse
Answer: True
This amplification works because RP has one-sided error: the only errors are false negatives (rejecting a true 'yes' instance). For a true 'yes' instance, each run independently accepts with probability ≥ 1/2, so the probability of k consecutive rejections is at most (1/2)^k. After 100 runs, this is less than 10^-30 — effectively zero. And false positives never occur, so accepting as soon as any run says 'yes' is always correct. This amplification argument doesn't work for BPP's two-sided error without more care.
Question 4 True / False
RP and coRP are the same complexity class, since both allow one-sided error and both are contained in BPP.
TTrue
FFalse
Answer: False
RP and coRP are defined as complements, not equals. RP allows false negatives (might miss true 'yes' instances) but never false positives. coRP allows false positives (might incorrectly accept 'no' instances) but never false negatives. A language is in RP if there is an algorithm with no false positives; the same language is in coRP if there is an algorithm with no false negatives — these are different properties. It is not known whether RP = coRP. Their intersection RP ∩ coRP is particularly useful: an algorithm in this intersection would have no error at all in at least one direction for each answer.
Question 5 Short Answer
Explain why one-sided error in RP is more practically useful than two-sided error in BPP, even though BPP contains RP.
Think about your answer, then reveal below.
Model answer: With RP, a 'yes' answer is unconditionally correct — you never need to worry that an acceptance was a false positive. This lets you trust positive results immediately without repetition. With BPP's two-sided error, neither answer can be trusted unconditionally without running the algorithm multiple times to amplify confidence. In settings where you need an unconditionally reliable positive answer (e.g., confirming a witness, verifying a solution), RP gives you this for free; BPP requires extra repetition and probabilistic confidence intervals.
The practical asymmetry matters in many real applications. If you're testing whether a number is prime, an unconditional 'yes' is more useful than 'probably yes with error < 2^-100' — the former admits no doubt. RP algorithms also compose more naturally with other deterministic checks: if an RP algorithm says 'yes' and a subsequent deterministic verifier confirms it, you know the answer is correct without tracking error probabilities. BPP requires careful error bookkeeping throughout. This is why RP/coRP algorithms are often described as 'more trustworthy' despite having higher error probability than amplified BPP.