Questions: Randomized Algorithms and Probabilistic Complexity Classes

Question 1

A randomized algorithm for graph isomorphism always correctly rejects non-isomorphic graphs, but may incorrectly reject isomorphic graphs with probability 1/4. This algorithm belongs to:

• A. BPP, because the error probability is bounded below 1/2
• B. RP, because it rejects all non-isomorphic graphs with probability 1
• C. co-RP, because it never produces a false YES — it only possibly produces a false NO on YES instances
• D. ZPP, because the expected running time is polynomial

Answer: (C)

co-RP has no false positives (no false YES answers) but allows false negatives (false NO answers). This algorithm always correctly rejects NO instances (non-isomorphic graphs) — so it never says 'isomorphic' when the graphs are not. But on YES instances (isomorphic graphs), it may incorrectly reject with probability 1/4. This is exactly the co-RP error profile: possible false NO, never false YES. RP is the mirror image: never false NO, possible false YES. BPP would allow both types of error.

Question 2

If BPP = P were proven, the most direct implication would be:

• A. Randomized algorithms provide no speedup of any kind — they solve exactly the same problems in exactly the same time as deterministic algorithms
• B. Every problem solvable by a bounded-error randomized algorithm in polynomial time can also be solved by a deterministic algorithm in polynomial time
• C. The P vs NP question would be resolved, since BPP ⊆ NP implies P = NP
• D. Pseudorandom number generators cannot exist, since deterministic machines cannot simulate true randomness

Answer: (B)

BPP = P would mean that for every language in BPP, a deterministic polynomial-time algorithm exists. It would not eliminate the practical advantages of randomized algorithms (simplicity, smaller constants, ease of design), only the asymptotic class separation. It does not resolve P vs NP — BPP ⊆ PSPACE but BPP's relationship to NP is unclear. The result is believed to hold because pseudorandom generators can derandomize BPP algorithms, making explicit randomness computationally unnecessary.

Question 3

BPP's error threshold of 2/3 is fundamental: changing it to 0.51 would strictly enlarge the class, admitting problems not in BPP with the 2/3 threshold.

• T. True
• F. False

Answer: False

BPP is robust to the exact error threshold via error amplification. Running a BPP algorithm k times independently and taking the majority vote reduces the error to at most 2^(−Ω(k)) while only multiplying running time by k (a polynomial factor). Any constant error probability strictly below 1/2 defines the same class BPP, regardless of whether the threshold is 0.51, 2/3, or 0.99. The only requirement is that the correct answer is more likely than not — any such threshold is equivalent under amplification.

Question 4

RP is contained in NP because a randomizing polynomial-time machine that accepts YES instances with probability ≥ 1/2 can be viewed as a nondeterministic machine where each nondeterministic choice corresponds to a coin flip.

• T. True
• F. False

Answer: True

An NTM accepts if *any* computation path accepts. An RP machine accepts a YES instance on at least half its coin-flip sequences. If we treat each coin-flip sequence as a nondeterministic branch, then on YES instances at least one branch accepts — so the NTM accepts. On NO instances, the RP machine always rejects on every branch, so the NTM also rejects. This argument shows RP ⊆ NP. The inclusion is strict unless RP = NP, which would imply a dramatic collapse of the complexity hierarchy.

Question 5

Explain the error amplification technique for BPP, and why it implies that the exact value of the error bound (as long as it's a constant below 1/2) does not affect what problems are in BPP.

Model answer: Error amplification works by running the BPP algorithm k independent times on the same input and taking the majority vote. If the algorithm has error probability ε < 1/2 on each run, then by the Chernoff bound the probability that the majority vote is wrong decreases exponentially in k — specifically to at most exp(−2k(1/2 − ε)²). Choosing k = O(n) gives error at most 2^(−Ω(n)) at only a polynomial cost. Since any constant ε < 1/2 can be amplified to negligible error in polynomial time, the class BPP is the same whether defined with error 1/3, 0.49, or 0.001 — all these thresholds define identical sets of languages.

The amplification argument also explains why BPP is considered a 'robust' class: unlike RP (which has asymmetric error) or ZPP (which must always be correct), BPP's two-sided error can always be driven to negligible levels by repetition. This robustness is why BPP, not RP, is the main model for practical randomized algorithms.