Lectures: By Omar Fawzi, on Thursday 10:15 — 12:15, Amphi ??
Tutorials: On Tuesday 15:45 — 17:45, Amphi B
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).
- 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