Questions: BPP: Bounded Error Probabilistic Polynomial Time

Question 1

A randomized algorithm for polynomial identity testing has error probability 1/4 on any single run. A colleague claims this algorithm cannot be in BPP because 1/4 > 1/3. Who is correct?

• A. The colleague is correct — BPP requires error probability at most exactly 1/3, and 1/4 is strictly greater than 1/3
• B. Neither is correct — BPP only applies to zero-error (Las Vegas) algorithms
• C. The algorithm's designer is correct — any error bound strictly less than 1/2 defines the same BPP class via error amplification, so 1/4 is acceptable
• D. Both are partially correct — the algorithm is in a class between BPP and RP

Answer: (C)

The colleague has the inequality backwards (1/4 < 1/3, not greater), but more fundamentally, the specific error threshold doesn't matter. BPP error amplification shows that *any* constant error probability strictly less than 1/2 defines the same class: by running the algorithm k times and taking the majority vote, the error probability drops exponentially in k. An algorithm with error 1/4 is easily amplified to error 1/100 or 2^(-n) while remaining polynomial time. The 1/3 in the definition is conventional, not special.

Question 2

Most complexity theorists believe BPP = P. What is the strongest evidence supporting this conjecture?

• A. Every known BPP algorithm has eventually been converted to an equivalent deterministic polynomial algorithm
• B. Under plausible circuit complexity assumptions (specifically, that strong one-way functions exist), pseudorandom generators can simulate BPP algorithms deterministically in polynomial time
• C. The polynomial hierarchy would collapse if BPP ≠ P, which is a known impossibility
• D. No problem has ever been proven to require randomness — all BPP algorithms are already deterministic in disguise

Answer: (B)

The derandomization agenda is the main theoretical evidence: complexity theorists have shown that if sufficiently hard functions exist (which circuit lower bound assumptions assert), then pseudorandom generators can be built that fool BPP algorithms, enabling deterministic polynomial simulation. The AKS primality algorithm is a concrete example — Miller-Rabin was in BPP for decades before AKS proved primality is in P. Option C is wrong because BPP ≠ P is not known to be impossible; option A is an overstatement (not *every* BPP algorithm has a known deterministic counterpart).

Question 3

Running a BPP algorithm 100 times and taking the majority vote increases the total error probability because there are 100 independent opportunities to make a mistake.

• T. True
• F. False

Answer: False

This is exactly backwards. For error amplification to fail, a majority of the 100 runs must give the wrong answer — but each run independently errs with probability at most 1/3 < 1/2. By the Chernoff bound, the probability that more than 50 of 100 independent runs err falls exponentially with the number of runs. The result is an error probability far smaller than the original 1/3 — not larger. This exponential decrease is the mathematical content of BPP's error amplification property.

Question 4

Every problem in P is also in BPP because a deterministic algorithm is a special case of a probabilistic algorithm with error probability zero.

• T. True
• F. False

Answer: True

P ⊆ BPP is trivially true: a deterministic polynomial algorithm never flips coins and always produces the correct answer, achieving error probability exactly 0. Since 0 ≤ 1/3, it meets the BPP definition. The interesting and open question is the reverse direction — whether BPP ⊆ P (i.e., whether randomness ever provides a genuine advantage for decision problems).

Question 5

Why doesn't the specific choice of 1/3 as the error bound in BPP's definition matter for which problems belong to the class?

Model answer: The 1/3 threshold is conventional, not fundamental. What matters is that the error is strictly less than 1/2 — there is a gap between the success probability and random guessing. Any constant error bound ε with 0 < ε < 1/2 defines the same class because of error amplification: run the algorithm k times independently and take the majority vote. By the Chernoff bound, the probability that a majority of runs errs decreases exponentially in k. So an algorithm with error 1/4 can be amplified to error 1/100 or 2^(-n) using polynomially many (O(n) for any polynomial error target) repetitions, which keeps the total runtime polynomial. Since any threshold below 1/2 can be amplified to any other threshold below 1/2, all such thresholds characterize the same set of languages.

This amplification argument is what separates BPP from RP (one-sided error < 1/2) and ZPP (zero error, expected polynomial time). The two-sided error in BPP can be amplified just like one-sided error, making the specific threshold irrelevant as long as it's bounded away from 1/2.