MIT OpenCourseWare http://ocw.mit.edu 6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.6.080/6.089 GITCS 1 April 2008 Lecture 14 Lecturer: Scott Aaronson Scribe: Geoffrey Thomas Recap Randomness can make possible computation tasks that are provably impossible without it. Cryp-tography is a good example: if the adversary can predict the way you generate your keys, you cannot encrypt messages. Randomness is also good for breaking symmetry and making arbitrary choices. We also have randomized algorithms. For example, to determine the equality of two polynomials given in nonstandard form, e.g., (1 + x)2 = 1 + 3x + 3x 2 + x 3 pick a few random values and see if they evaluate to the same thing. Since two different polynomials of degree d can only be equal at up to d points per the Fundamental Theorem of Algebra, after evaluating the polynomials at very few values, we can know with high probability whether they are equal. Can we “derandomize” any randomized algorithm, i.e., can we convert it into a deterministic algorithm w ith roughly the same efficiency? This (formalized be low as P versus BPP) is one of the central open questions of theoretical computer science. Useful Probability Formulas Union bound: Pr [A ∨ B] ≤ Pr [A] + Pr [B]• Linearity of expectation: E [X + Y ] = E [X]+E [Y ] whether or not X and Y are independent • Markov’s inequality: • 1Pr [X ≥ kE [X]] ≤ k This is true for any distribution X that takes only non-negative values. To prove it: suppose it were false. Then the contribution to E [X] from X greater than kE [X] would be so big as to increase the expectation. Complexity Can we formalize the concept of a problem that can be solved efficiently with a randomized algo-rithm? There are several ways to do this. The complexity class BPP (Bounded-Error Probabilistic Polynomial-Time) is the class of lan-guages L ⊆ {0, 1}∗ for which there exists a polynomial time algorithm M(x, r ) such that for all inputs x, if x ∈ L, then M(x, r) acce pts with probability ≥ 2 • 3 14-1� � � � � � � � � � � � • if x �∈ L, then M(x, r) acce pts with probability ≤ 1 3. Here r is a random string of polynomial length. andyou want more accurate probabilities, you can use amplification: run the algorithm many times and take the majority answer. By combining many noisy answers, you can compute a single more accurate answer. So intuitively, it shouldn’t matter what probabilities we use to define BPP, since we can amplify any success probability to any other with a constant number of repetitions. But can we be more precise, and bound how many repetitions are needed to amplify a given success probability p to another probability q? This is basically a statistics problem, involving the tails of binomial distributions. Computer scientists like to solve such problems using a rough-and-ready yet versatile tool called the Chernoff bound. For n fair coin flips X1 . . . Xn ∈ {0, 1}, let By linearity of exp e ctation, E [X] = n The Chernoff bound says that for all 233Why ? Well, they’re just two nice numbers that are separated from each other. If X = X1 + + Xn.· · · . constants a > 0, �� �� Pr ��X − n �� > an ≥ can 2 for some constant ca < 1. In other words, if we repeat our BPP algorithm n times, the probability that the majority of the answers will be wrong decreases exponentially in n. To prove the Chernoff b ound, the key idea is to bound the expectation not of X, but of cX for some constant c: E c X = E c X1+···+Xn = E c X1 c Xn � �· · · � � = E c X1 E c Xn � �· · · 1 + c n = 2 Here, of course, we’ve made crucial use of the fact that the Xi’s are independent. Now by Markov’s inequality, 1 + c n1Pr c X ≥ k 2 ≤ k 1 + c 1Pr X ≥ log k + n log2 ≤ kc c We can then choose a suitable constant c > 1 to optimize the bound; the details get a bit messy. But you can see the basic point: as we increas e d := logc k—which intuitively measures the deviation of X from the mean—the probability of X deviating by that amount decreases exponentially with d. As a side note, can we amplify any difference in probabilities—including, say, a difference between 1/2 − 2−n and 1/2 + 2−n? Yes, but in this case you can work out that we’ll need an exponential number of repetitions to achieve constant confidence. On the other hand, so long as the inverse of the difference between the two acceptance probabilities is at most a polynomial, we can amplify the difference in polynomial time. Other Probabilistic Complexity Classes BPP algorithms are “two-sided tests”: they can give errors in both directions. Algorithms like our polynomial-equality test can give false positives but never false negatives, and are therefore 14-2 1 2called “one-sided tests.” To formalize one-sided tests, we define another complexity class RP (Randomized Polynomial-Time). RP is the class of all languages L ⊆ {0, 1}∗ for which there exists a polynomial time algorithm M(x, r) such that for all inputs x, • If x ∈ L, then M(x, r) acce pts with probability ≥ 1 2. • If x �∈ L, then M(x, r) always rejects regardless of r. The polynomial-nonequality problem is in RP, or equivalently, the polynomial-equality problem is in coRP. P is in RP, coRP and BPP. RP and coRP are in BPP, because we can just amplify an RP 1 3 2algorithm once and reject with probability 0 ≤ is also called ZPP, for Zero-Error Probabilistic Polynomial-Time. and accept with probability RP ∩ coRP It might seem obvious that ≥ . 3 4 3ZPP = P, but this is not yet known to be true. For even given both RP and coRP algorithms for a problem, you might get unlucky and always get rejections from the RP algorithm and acceptances from the coRP algorithm. RP is in NP: the polynomial certificate that some x ∈ L is simply any of the random values r that cause the RP algorithm to accept. (Similarly, coRP is in coNP.) BPP is in PSPACE because you can try every r and count how many accept and how many rejec t. Whether BPP is in NP is an open question. (Sure, you can generate a polynomial number of “random” numbers r to feed to a deterministic