Questions: Randomized Complexity: RP, co-RP, and ZPP

Question 1

An RP algorithm is run 20 times on an input x, and all 20 runs output NO. What can we conclude?

• A. The answer is definitely NO — RP algorithms are always correct on NO instances
• B. The answer is probably NO, with error probability at most (1/2)^20, but we cannot be certain
• C. The answer is definitely YES — if the algorithm said NO 20 times, it must have been on a YES instance and kept making mistakes
• D. We cannot conclude anything, because RP algorithms have two-sided error like BPP

Answer: (B)

RP has ONE-SIDED error: on NO instances, the algorithm ALWAYS says NO (no false positives). So if the true answer is NO, every run correctly outputs NO. If the true answer is YES, each run says YES with probability ≥ 1/2 and NO with probability ≤ 1/2. After 20 independent NO outputs, the probability that the true answer is YES is at most (1/2)^20 ≈ 10^{-6}. We are extremely confident the answer is NO, but not with absolute certainty — the true answer could be YES and we just got unlucky 20 times. This is why we say 'with high probability' rather than 'certainly.'

Question 2

An RP algorithm for problem L is run on input x and outputs YES. What can we conclude?

• A. The answer is probably YES, with error probability at most 1/2, but not definite
• B. The answer is definitely YES — RP has no false positives, so a YES output is always correct
• C. We need to run the algorithm more times to reduce the error probability below 1/2
• D. The algorithm may have made an error; we should switch to a co-RP algorithm for confirmation

Answer: (B)

RP is defined so that NO instances always output NO (no false positives). Equivalently, a YES output is never wrong — if the algorithm says YES, the answer is definitely YES. The one-sided error is on YES instances: the algorithm might say NO when the answer is YES (a false negative), but never says YES when the answer is NO (no false positives). This asymmetry is the whole point: a single YES output from an RP algorithm is a definitive witness to membership, while repeated NO outputs give exponentially increasing confidence.

Question 3

A problem in ZPP has a randomized algorithm that always outputs the correct answer, but may run for a very long time on some random coin sequences — ZPP does not require polynomial time on every execution, only in expectation.

• T. True
• F. False

Answer: True

ZPP = RP ∩ co-RP, and can be characterized by Las Vegas algorithms: always correct, with expected polynomial running time. On some coin sequences, a ZPP algorithm may run for much longer than polynomial time; what is bounded is the EXPECTED runtime over the random choices. This contrasts with deterministic polynomial time (P), where every execution must halt in polynomial time, and with Monte Carlo algorithms (BPP/RP), which halt quickly but may be wrong.

Question 4

The most efficient strategy to reduce the error probability of an RP algorithm is to run it multiple times and take the majority vote, just as with BPP algorithms.

• T. True
• F. False

Answer: False

For RP, majority vote is both unnecessary and suboptimal. Because RP has no false positives, a single YES output is definitive — you do not need to confirm it with more runs. The right strategy for RP is: run k times, and if ANY run outputs YES, answer YES. If ALL runs output NO, answer NO. This achieves error probability (1/2)^k with k runs. Majority vote would be wasteful (it discards the definitive YES information) and would actually weaken the conclusion on some inputs. Majority vote is appropriate for BPP because two-sided error requires averaging out both types of mistakes.

Question 5

Why is one-sided error more exploitable than two-sided error? Explain using the structure of RP algorithms.

Model answer: With one-sided error, one answer type is always reliable. In RP, NO outputs are always correct — there are no false positives. This means a single YES output is a conclusive proof of YES-membership. Repeated runs amplify confidence exponentially: if all k runs say NO, the probability of a missed YES is at most (1/2)^k, which shrinks exponentially fast. With two-sided error (BPP), neither YES nor NO is conclusive on any single run — you can only accumulate probabilistic evidence, requiring majority vote over many runs. One-sided error gives you a 'definitive witness' property that two-sided error lacks.

This structure explains why RP is the natural complexity class for many algebraic and combinatorial decision problems: often there is an efficient way to CHECK a certificate (if a polynomial is non-zero, a random evaluation witnesses it), but no efficient way to prove non-membership. Problems in RP tend to have efficient randomized witnesses for the YES case, which is exactly the one-sided-error structure. Co-RP has the same advantage for the NO case.