Course Overview
This is a graduate course on the theory of computational complexity. Complexity theory is the study of how much of a resource (such as time, space, parallelism, or randomness) is required to perform some of the computations that interest us the most. In a standard algorithms course, one concentrates on giving resource efficient methods to solve interesting problems. In this course, we concentrate on techniques that prove or suggest that there are no efficient methods to solve many important problems.
We will develop the theory of various complexity classes, such as P, NP, co-NP, PH, #P, PSPACE, NC, AC, L, NL, UP, RP, BPP, IP, and PCP. We will study techniques to classify problems according to our available taxonomy. By developing a subtle pattern of reductions between classes we will suggest an (as yet unproven!) picture of how by using limited amounts of various resources, we limit our computational power.
It has become increasingly obvious that proving even a small part of this world picture true (or false) would be a major mathematical achievement. For example, one part of this picture is that P does not equal NP. The question of the equality of these two classes was originally posed in a letter from Kurt Gödel to J. Von Neumann; it is one of the most important problem in all of mathematics. We will study some of the remarkable lower bounds which have been proved in the hopes of making progress on these central issues. We will see that the solution to these questions will require techniques unlike any that are currently known.
One especially interesting aspect of our study will be the variety of roles played by randomness. It helps in all aspects of complexity theory: finding efficient algorithms, finding reductions between problems, and proving that certain problems have no efficient algorithms in restricted models. Another point worth mentioning is that this seemingly pessimistic theory of what is impossible is what makes two highly practical fields of computer science possible at all: pseudorandom number generation and cryptography. These fields return the favor by suggesting what is true and what is provable in complexity theory.