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 April 8, 2008 Lecture 15 Lecturer: Scott Aaronson Scribe: Tiffany Wang 1 Administrivia Midterms have been graded and the class average was 67. Grades will be normalized so that the average roughly corresponds to a B. The solutions will be posted on the website soon. Pset4 will be handed out on Thursday. 2 Recap 2.1 Probabilistic Computation We previously examined probabilistic computation methods and the different probabilistic com-plexity classes, as seen in Figure 1. Figure 1. Probabilistic Complexity Classes P: Polynomial time - Problems that can be solved deterministically in polynomial time. ZPP: Zero-error Probabilistic Polynomial (Expected Polynomial) time - Problems that can be solved efficiently but with 50% chance that the algorithm does not produce an answer and must be run again. If the algorithm does produce an answer it is guaranteed to be correct. RP: Randomized Polynomial time - Problems for which if the answer is NO, the algorithm always outputs NO. Otherwise, if the answer is YES, the algorithm outputs YES at least 50% of the time. Hence there is an asymmetry between YES and NO outputs. coRP: Complement of RP - These are problems for which there’s a polynomial-time algorithm that always outputs YES if the answer is YES and outputs NO at least 50% of the time if the answer 15-1 BPPRP coRPZPPPFigure by MIT OpenCourseWare.is NO. BPP: Bounded-error Probabilistic Polynomial time - Problems where if the answer is YES, the algorithm accepts with probability ≥ability ≤1 2 3, and if the answer is NO, the algorithm accepts with prob- 3. 2.2 Amplification and Chernoff Bound The question that arises is whether the boundary values 1 3and 2 3have any particular significance. One of the nice things about using a probabilistic algorithm is that as long as there is a noticeable gap between the probability of accepting if the answer is YES and the probability of accepting if the answer is NO, that gap can be amplified by repeatedly running the algorithm. For example, if you have an algorithm that outputs a wrong answer with Pr ≤can repeat the algorithm hundreds of times and just take the majority answer. The probability 1 3, then you of obtaining a wrong answer becomes astronomically small (there’s a much greater chance of an asteroid destroying your computer). This notion of amplification can be proven using a tool known as the Chernoff Bound. The Chernoff Bound states that given a set of independent events, the number of events that will hap-pen is heavily concentrated about the expected value of the number of occurring events. So given an algorithm that outputs a wrong answer with Pr = 1 3, repeating the algorithm 10,000 times would produce an expected number of 3333.3 . . . wrong answers. The number of wrong an-swers will not be exactly the expected value, but the probability of getting a number far from the expected value (say 5,000) is very small. 2.3 P vs. BPP There exists a fundamental question as to whether every probabilistic algorithm can be replaced by a deterministic one, or derandomized. In terms of complexity, the question is whether P=BPP, which is almost as deep a question as P=NP. There is currently a very strong belief that derandomization is possible in general, but no one yet knows how to prove it. 3 Derandomization Although derandomization has yet to be proven in the general case, it has been proven for some spectacular special cases: cases where for decades, the only known efficient solutions came from randomized algorithms. Indeed, this has been one of the big success stories in theoretical computer science in the last 10 years. 15-23.1 AKS Primality Test In 2002, Agrawal, Kayal, and Saxena of the Indian Institute of Technology Kanpur developed a deterministic polynomial-time algorithm for testing whether an integer is prime or composite, also known as the AKS primality test. For several decades prior, there existed good algorithms to test primality, but all were proba-bilistic. The problem was first known to be in the class RP, and then later shown to be in the class ZPP. It was also shown that the problem was in the class P, but only assuming that the General-ized Riemann Hypothesis was true. The problem was also known to be solvable deterministically in nO(logloglogn) time (which is slightly more than polynomial). Ultimately, it was nice to have the final answer and the discovery was an exciting thing to be alive for in the world of theoretical computer science. The basic idea behind AKS is related to Pascal’s Triangle. As seen in Figure 2, in every prime-numbered row, the numbers in Pascal’s Triangle are all a multiple of the row number. On the other hand, in every composite-numbered row, the numbers are not all multiples of the row number. Figure 2. Pascal’s Triangle and Prime Numbers So to test the primality of an integer N, can we just check whether or not all the numbers in the Nth row of Pascal’s Triangle are multiples of N ? The problem is that there are exponentially many numbers to check, and checking all of them would be no more efficient than trial division. Looking at the expression (x+a)N , which has coefficients determined by the Nth row of Pascal’s Triangle, AKS noticed that the relationship (x + a)N = xN + aN mod N holds if and only if N is prime. This is because if N is prime, then all the “middle” coefficients will be divisible by N (and therefore disappear when we reduce mod N ), while if N is composite then some middle coefficients will not be divisible by N. What this means is that the primality testing problem can be mapped to an instance of the polynomial identity testing problem: given two algebraic formulas, decide whether or not they represent the same polynomial. In order to determine whether (x + a)N = xN + aN mod N , one approach would be to plug in many random values of a and see if we get the same result each time. However, since the number of terms would still be exponential, we need to evaluate the expression not only mod N , but also mod a random polynomial: (x + a)N = x N + a N mod N, xr − 1. 15-3It turns out that this solution method works; on the other