Complexity Theory Markus Bläser, Balagopal Komarath

Registration for this course is open until Friday, 01.11.2019 00:00.



Hartmanis and Stearns

The following paper motivated the need to classify problems based on the complexity of algorithms to decide them.

Hartmanis and Stearns


Complexity Theory


Time and Date:

  • Tuesday 8:30 - 10:00, E1.3 HS003
  • Friday 10:15 - 12:00, E1.3 HS003
  • First lecture: Tuesday, Oct. 15



  • The time slot for the tutorial is Thursday 8.30 - 10.00



There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.



There will be oral exams at the end of the semester.




"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended.



There are many good books an the topic. Here is a selection:

  • Sanjev Arora and Boaz Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
  • Oded Goldreich, Computational Complexity - A Conceptual Perspective, Cambridge University Press.
  • Uwe Schöning, Gems of Theoretical Computer Science, Springer.
  • Rüdiger Reischuk, Komplexitätstheorie (Band 1), Teubner.


Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators