Lectures: By Omar Fawzi.
Tutorials: Tuesday, 15h45 to 17h45.
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
- TD01: On Turing Machines and equivalences with other computation models.
- TD02: Universal Turing Machine, and complexity classes.
- TD03: NP-Completeness, and Turing Machines (always).
- TD04: Considerations on space complexity.
- TD05: Mid-term preparation.
- TD06: Time-space relations.
- TD07: Circuit complexity.
- TD08: Randomized classes.
- TD09: Quantum computations.
- TD10: Revisions.
Homeworks
- HW1.
- HW2.
- HW3.
- HW4.
Useful Resources
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach.
- In French: Sylvain Périfel. Complexité Algorithmique.
- Complexity Zoo
- 2015 lecture notes [git].
- Last Year Course.
- \(\LaTeX\) complexity package.