A BPP algorithm errs with probability at most 1/3 on a single run. If you run it independently k times and output the majority answer, how does the error probability change?
AIt stays the same — independent runs do not help because errors are independent
BIt decreases linearly in k, reaching zero after 3 runs
CIt decreases exponentially in k, becoming negligibly small for large k
DIt increases, because more runs create more opportunities for error
By the Chernoff bound, the probability that a strict majority of k independent runs gives the wrong answer decreases exponentially in k. With k = 100 runs, the error is astronomically small even though each individual run still errs with probability 1/3. This error amplification is why the specific threshold of 1/3 in BPP's definition is not fundamental — any constant below 1/2 yields the same complexity class.
Question 2 True / False
A BPP algorithm's error probability applies to adversarially chosen inputs: on 'hard' inputs, the algorithm may typically fail.
TTrue
FFalse
Answer: False
The error in BPP is over the algorithm's internal random coin flips, not over the choice of input. For every fixed input x — including the hardest possible — the algorithm is correct with probability at least 2/3. There is no 'adversarial input' that exploits the randomness; the guarantee holds for all inputs simultaneously.
Question 3 Short Answer
Why does the specific error bound of 1/3 in the definition of BPP not fundamentally determine which problems are in the class?
Think about your answer, then reveal below.
Model answer: Any constant error bound strictly below 1/2 defines the same class, because error amplification via repeated independent trials can reduce error exponentially. An algorithm with error 1/3 can be boosted to error 2^{-100} using polynomially many trials. So 1/3, 0.4, or even 0.499 all capture the same set of languages — as long as the error is bounded away from 1/2.
The bound 1/2 is the real threshold: at exactly 1/2, the algorithm is no better than random guessing and amplification fails. Any constant below 1/2 allows amplification. The choice of 1/3 in the standard definition is a convenient convention, not a mathematical necessity.