Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

An open problem in computational complexity theory is the P = BPP conjecture. This conjecture asserts that polynomial time algorithms with access to randomness can be efficiently translated into standard polynomial time algorithms. In the 1970s efficient probabilistic algorithms placed Primality in BPP, leading to the conjecture that Primality is in fact in P. For a number of years, Primality was the key example of a problem in BPP but not known to be in P. Finally, in 2002, Agrawal, Kayal and Saxena proved that Primality is in P, using only basic algebraic and number theoretic structures. In this talk, I show the basic ideas behind the AKS algorithm after introducing the concepts needed to discuss computational complexity.