Complexity Theory Markus Bläser, Balagopal Komarath

News

19.04.2018

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

18.04.2018

The result that DTime1(o(n log n)) = DTime1(n) mentioned today in the lecture is Theorem 2 in:

  • Juris Hartmanis: Computational Complextiy of 1-tape Turing Machine Computations, Journal of the ACM, 15(2): 325-339, 1968.

The paper is rather old, so the... Read more

The result that DTime1(o(n log n)) = DTime1(n) mentioned today in the lecture is Theorem 2 in:

  • Juris Hartmanis: Computational Complextiy of 1-tape Turing Machine Computations, Journal of the ACM, 15(2): 325-339, 1968.

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:

  • Rüdiger Reischuk: Komplexitätstheorie, Band I, Teubner (Theorem 3.1.8)
 

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

 



If you encounter technical problems, please contact the administrators