News
19.04.2018

The tutorials take place Tuesday 8:30  100 in E1.3 SR016. 
18.04.2018

The result that DTime_{1}(o(n log n)) = DTime_{1}(n) mentioned today in the lecture is Theorem 2 in:
The paper is rather old, so the... Read more The result that DTime_{1}(o(n log n)) = DTime_{1}(n) mentioned today in the lecture is Theorem 2 in:
The paper is rather old, so the notation used there might be a little bit different from modern notation. The only modern reference that I am aware of is unfortunately in German:

Complexity Theory
Time and Date:
 Monday 10:15  12:00, E1.3 HS003
 Wednesday 10:15  12:00, E1.3 HS003
First lecture will be on Wednesday, April 11!
Tutorials:
 Tuesday 8:30  100, E1.3 SR016
Assignments:
There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.
Exams:
There will be oral exams at the end of the semester.
Prerequisites:
"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NPcompleteness) is highly recommended.
Literature:
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.