The following paper motivated the need to classify problems based on the complexity of algorithms to decide them.
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.