## Complexity and Logic |
Technische Universität Dresden |

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

The exercise group takes place every Wednesday at 11:10 (DS3) in room GRU 350 and is held by Carsten Lutz.

Every week, an exercise sheet will be made available for download from this webpage.- Exercise sheet 1
- Exercise sheet 2
- Exercise sheet 3
- Exercise sheet 4
- Exercise sheet 5
- Exercise sheet 6
- Exercise sheet 7
- Exercise sheet 8
- Exercise sheet 9
- Exercise sheet 10
- Exercise sheet 11
- Exercise sheet 12
- Exercise sheet 13
- Exercise sheet 14 (corrected)

- present at least four exercises in front of the exercise group;

- pass an oral examination at the end of the term.

The oral exams will take place on February 27 in Room 433. Please send a mail to Carsten Lutz if you want to make an appointment.

- 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

(Addison-Wesley, 1979) - Erich Grädel

Skript of lecture "Komplexitätstheorie" (in German)

Carsten Lutz