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).


  • 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