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 Geo rey 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 3x2 x3 pick a few random values and see if they evaluate to the same thing Since two di erent 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 with roughly the same e ciency This formalized below 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 1 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 Pr X kE X Complexity Can we formalize the concept of a problem that can be solved e ciently 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 accepts with probability 14 1 2 3 if x L then M x r accepts with probability 13 Here r is a random string of polynomial length Why 13 and 32 Well they re just two nice numbers that are separated from each other If you want more accurate probabilities you can use ampli cation 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 de ne 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 roughand ready yet versatile tool called the Cherno bound For n fair coin ips X1 Xn 0 1 let X X1 Xn By linearity of expectation E X n2 The Cherno bound says that for all constants a 0 n Pr X an cna 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 Cherno bound the key idea is to bound the expectation not of X but of cX for some constant c E cX E cX1 Xn E cX1 cXn E cX1 E cXn 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 n 1 X Pr c k 2 k 1 c 1 Pr X logc k n logc 2 k 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 increase 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 di erence in probabilities including say a di erence 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 con dence On the other hand so long as the inverse of the di erence between the two acceptance probabilities is at most a polynomial we can amplify the di erence 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 called one sided tests To formalize one sided tests we de ne 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 accepts with probability 12 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 algorithm once and reject with probability 0 13 and accept with probability 43 23 RP coRP is also called ZPP for Zero Error Probabilistic Polynomial Time It might seem obvious that ZPP 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 certi cate 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 reject 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 veri er but how do you convince the veri er that these numbers are in fact random rather than cherry picked to give the answer you want Sipser Ga cs and Lautemann found that BPP NPNP placing BPP in the so called polynomial NP hierarchy NP NPNP NPNP An even more amazing possibility than BPP NP would be BPP P that is that every randomized algorithm could be derandomized Nevertheless the consensus on this question has changed over time and today most theoretical computer scientists believe that BPP P even though we seem far from being able …