A probabilistic algorithm for a decision problem runs in polynomial time and achieves at least 2/3 correct answers on every input. A researcher argues that changing the success threshold to 51% would define a strictly weaker complexity class. Is she correct?
AYes — a 51% success rate gives far less confidence than 2/3 and therefore captures a smaller set of problems
BNo — any constant success probability greater than 1/2 defines the same class BPP, because error can be driven exponentially small by independent repetition and majority voting
CNo — 51% success defines PP, a strictly larger class than BPP, so 51% is a weaker requirement
DYes — BPP is specifically defined by the 2/3 threshold and changing it alters the class by definition
The 1/3 error threshold (equivalently, 2/3 success) in BPP's definition is completely arbitrary. By the Chernoff bound, running the algorithm k times independently and taking majority vote drives the error probability exponentially to zero: if the per-run success probability is 1/2 + ε for any ε > 0, then k = O(1/ε²) repetitions suffice to achieve any target confidence. Since k can grow polynomially in 1/ε, the repetitions stay within polynomial time. The result: any constant error strictly below 1/2 gives exactly the class BPP. The threshold 1/2 is the critical boundary — algorithms with exactly 50% success (PP) define a genuinely larger and harder class.
Question 2 Multiple Choice
BPP is widely conjectured to equal P. Which observation provides the most direct computational evidence for this conjecture?
ABPP ⊆ PSPACE, which shows randomness cannot help beyond polynomial space
BThe Miller-Rabin primality test (a canonical BPP algorithm) was superseded by AKS, a deterministic polynomial-time algorithm — consistent with the pattern that BPP algorithms can be derandomized
CBPP ⊇ P, which means all deterministic algorithms are already BPP algorithms
DNP is not believed to be in BPP, confirming that randomness doesn't solve hard problems
The AKS algorithm (2002) showed that primality testing — the canonical motivating example for BPP — is in fact solvable in deterministic polynomial time. Miller-Rabin gave a fast, practical BPP algorithm; AKS showed randomness was not actually needed. This is exactly the pattern the BPP = P conjecture predicts: randomness sometimes provides a shortcut, but a deterministic equivalent always exists. The formal evidence comes from Adleman's theorem (BPP ⊆ P/poly) and conditional derandomization results linking BPP = P to the existence of hard functions for circuit lower bounds, but the Miller-Rabin → AKS trajectory is the cleanest concrete illustration.
Question 3 True / False
A BPP algorithm's error guarantee must hold on every individual input — not just on most inputs or on average over a distribution of inputs.
TTrue
FFalse
Answer: True
This is a crucial and often underappreciated distinction. BPP requires that for EVERY input x, the algorithm outputs the correct answer with probability at least 2/3. An algorithm that is correct on 99.9% of inputs but fails catastrophically on a small adversarially chosen set is NOT a BPP algorithm. This is a worst-case guarantee over inputs, not an average-case guarantee. The distinction matters practically: an adversary who knows which inputs fool your algorithm can break average-case guarantees; the worst-case per-input guarantee of BPP provides a much stronger security-style assurance.
Question 4 True / False
BPP ⊇ NP — that is, nearly every NP problem can be solved in polynomial time by a probabilistic algorithm that randomly guesses and checks certificates.
TTrue
FFalse
Answer: False
This is a common misconception. Randomly guessing a certificate and checking it only works efficiently when a large fraction of all possible certificate strings are valid. For NP problems in general, valid certificates can be exponentially rare among all strings of the right length — a random guess finds one only with negligible probability. The canonical hardness conjecture is NP ⊄ BPP (and in particular P ≠ NP), meaning there are NP problems that cannot be solved by any polynomial-time probabilistic algorithm with bounded error. BPP captures problems where randomness provides efficiency without exponential search; NP captures problems requiring a correct certificate that cannot be found without exhaustive search in the worst case.
Question 5 Short Answer
The error bound in BPP is 'at most 1/3.' Explain why this threshold is considered arbitrary, and identify what would happen to the class if the threshold were set to exactly 1/2.
Think about your answer, then reveal below.
Model answer: The threshold is arbitrary because error amplification works for any constant strictly below 1/2: run the algorithm k times, take majority vote, and the Chernoff bound guarantees the error falls exponentially in k. So a 49% error bound, a 33% error bound, and a 1% error bound all define the same class via repetition within polynomial time. Setting the threshold to exactly 1/2 changes everything: an algorithm that is correct with probability exactly 1/2 on every input is no better than a random coin flip. Majority voting over such an algorithm is useless — the expected number of correct and wrong answers are equal. The class PP (Probabilistic Polynomial time) uses a threshold of > 1/2 (strictly), which is a much larger and less useful class; it contains NP and is believed to be much harder than BPP.
The 1/2 boundary is fundamental because it is where amplification breaks down. Any algorithm with success probability 1/2 + ε (for fixed ε > 0 bounded away from 0) can be amplified; any algorithm with success probability approaching 1/2 as the input grows would require super-polynomially many repetitions to amplify. BPP's definition asks for a constant bounded away from 1/2, ensuring amplification works in polynomial time. This is the same mathematical intuition behind Chernoff-Hoeffding concentration inequalities for random variables bounded strictly away from their mean.