This course gives an introduction into complexity theory,
with a special emphasis on applications in logic. It will
introduce important complexity classes such as NP, PSpace,
the polynomial hierarchy, ExpTime, etc., show the relationships
among them, and give examples of various logics with decision
problems that are complete for these classes.
The lecture takes place twice a week in room GRU 350:
Tuesday 16:40-18:10 (DS6) and Thursday 16:40-18:10 (DS6).
A script for this lecture is not availble. Therefore, students are advised
to copy what is written on the blackboard.
The exercise group
takes place every Wednesday at 14:50-16:20 (DS5) in room GRU 350 and is
held by Carsten Lutz.
Every week, an exercise sheet will be made available for download from this
Credits / Examinations
Computational logic students can earn 9 credits by attending this lecture. The lecture can be
used for the modules IT, KRAI, TCSL.
In order to get the credits, CL students have to meet both of the following two
Computer Science students are not obliged to present exercises, but are invited
to do so.
- present at least four exercises in front of the exercise group;
- pass an oral examination at the end of the term.
- Michael Sipser
Introduction to the Theory of Computation
- Christos H. Papadimitriou
Computational Complexity (Addison Wesley, 1994)
- Michael R. Garey and David S. Johnson
Computers and Intractability --- A guide to NP-completeness
(W. H. Freeman and Company, 1979)
- J. Hopcroft and J. Ullmann
Introduction to Automata Theory, Languages and Computation
- Erich Grädel
Skript of lecture "Komplexitätstheorie" (in German)