Département Lettres et Arts

Overview of the course:

Computational complexity aims to classify computational problems depending on the resources they need. One studies various modes of computation (deterministic, randomized, nondeterministic, interactive) 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. An important par 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.   

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.