## 2015 – 2016: Computational Complexity

Lectures: By Omar Fawzi, on Thursday 10:15 — 12:15, Amphi ??
Tutorials: On Tuesday 15:45 — 17:45, Amphi B

A description of the course is available here and more extensive information is accessible here.

To sum up, this course aims at making you more familiar with the different complexity classes (i.e. a classification of the different computational problems based on their asymptotical resource consumption).

## Tutorials

• TD1: On Turing machines.
• TD2: On Turing machines, and some $$P/NP$$ considerations.
• TD3: On Time Constructible Functions, NP-Completeness and Hierarchy.
• TD4: On Space Complexity
• TD5: Still on Space