Undergraduate Complexity Theory

Course ID 15455

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.

Key Topics
Time complexity. Space complexity. Probabilistic computation. Nondeterministic computation. Polynomial-time hierarchy. Reductions, hardness, and completeness. Boolean circuit complexity. Communication complexity. Interactive proofs. Probabilistically checkable proofs.

Required Background Knowledge
Mathematical maturity, some probability and linear algebra background.

Course Relevance
Any undergraduate or graduate student with the prerequisite background can take the course.

Course Goals
- Explain the central goals of computational complexity theory: how computational problems are modeled, and how the resources needed to solve them are measured.
- Work fluently with major models of computation used in complexity theory.
- Analyze the time and space complexity of algorithms in the deterministic, probabilistic, and nondeterministic models.
- Use reductions to relate problems to one another. Explain the notions of hardness and completeness.
- Reason about Boolean circuit model and understand its connections to the Turing machine model.
- Understand the role of interaction and randomness in proof systems.
- Explain the significance of probabilistically checkable proofs and their connection to hardness of approximation.
- Prove rigorous lower and upper bounds on the complexity of problems using a variety of techniques.
- Read, write, and evaluate rigorous mathematical proofs.

Learning Resources
Lecture videos, lecture notes, online discussions, office hours.

Assessment Structure
25% Homework, 20% Midterm 1, 20% Midterm 2, 35% Final