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
- TD6: Padding and Oracles
- TD7: Time-Space tradeoff and Polynomial Hierarchy
- TD8: Two-players game, and circuit complexity
- TD9: Randomized Classes
- TD10: Randomized Computation
Useful Resources
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach
- In French: Sylvain Périfel. Complexité Algorithmique.
- Last year lecture notes [git].