Computational complexity theory is concerned with the intrinsic complexity of computational tasks, asking what can be achieved with limited computational resources? This course provides an introduction to complexity theory, emphasizing the implications of theoretic results for applications in computer science. In doing so, it comes to grips with questions such as the following: Is it easier to verify a proposed solution to a problem, than it is to find a solution? Is it easier to find an approximate solution than an exact solution? Are randomized algorithms more powerful than deterministic algorithms? Are quantum computers more powerful than classical computers? In studying the progress that has been made on questions such as these, we will develop insights into the nature of computation and the implications of complexity theory for the practical development of algorithms. Specific topics include the P vs. NP problem (why is this problem so fundamental, and why is it so hard to solve?); approximation algorithms for NP-hard optimization problems; the limits of approximability; randomized algorithms, interactive proofs, and pseudorandomness; complexity and cryptography; and quantum complexity. All background in theoretical computer science is developed as needed in the course.
605.421 Foundations of Algorithms or equivalent.