Lectures: By Omar Fawzi.
Tutorials: Tuesday, 15h45 to 17h45.
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).
- 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.