Computational Complexity

Course offered in the second semester of M1.

Overview of the course:

Computational complexity aims to classify computational problems depending on the resources they need. One
studies various modes of computation such as deterministic, randomized, nondeterministic or quantum and compares
resources such as time or space needed to solve algorithmic problems. The objective of this course is to give a
broad understanding of the notions used to classify computational problems. About half of the course is dedicated
to studying basic complexity classes defined using Turing machines. We introduce (or study deeper) notions that are
central in complexity theory: nondeterministic computation (e.g., the class NP), reductions between computational
problems (e.g., NP-completeness) and the technique of diagonalization (e.g., hierarchy theorems). We also study
randomized computation and computation using boolean circuits as well as their relation to basic complexity classes.
We conclude the course by studying the complexity of communication, i.e., trying to evaluate communication
bottlenecks to perform a given computational task between different parties.
Teaching in 2014: Omar Fawzi (lectures) and S ́ebastien Maulat (exercise classes)

Course objectives:

One can summarize the most important objectives of the course as follows.

  1. Understand the formal definitions for the basic complexity classes like L, NL, P, NP, coNP, PSPACE.
    Be familiar with nondeterministic computation and the polynomial hierarchy. Know about the inclusions and separations between these classes.
  2. Understand the notion of reduction between computational problems, and the notion of complete problem, e.g., SAT is NP-complete, PATH is NL-complete, TQBF is PSPACE-complete.
  3. Understand complexity classes defined using boolean circuits, and the notion of uniformity in computation. Know the relation to basic complexity classes.
  4. Understand complexity classes using randomized computations. Know the relation to basic complexity classes.
  5. Get a flavour for the power of interactive proofs.
  6. Be familiar with an important tool in theoretical computer science: communication complexity. Be able to reduce various problems to a communication complexity problem.