## Complexity Theory |
Technische Universität Dresden |

Complexity theory is an important tool for analyzing the computational properties of logical systems. The aim of this course is to recall the most important notions of complexity theority. It introduces basic complexity classes such as NP and PSpace, discusses their relation, and establishes (theoretical) tools for proving hardness for and containment in these classes. The course aims at students that have little or no knowledge of complexity theory, and it may be used to refresh and deepen the knowledge about complexity theory gained in undergraduate courses.

Time and Place: Every Friday in DS2 (09:20-10:50) in room E005 of Nöthnitzer Str. 46

The course is usually given in the form of a lecture. Occasionally, it takes the form of a tutorial in which the students present their solutions to handed-out exercises.

- Exercise sheet 1 (for November 17)
- Exercise sheet 2 (for January 17)

For the foundational module, there will be a single 120 minute written exam in the examination period. In this exam, there will be two tracks:

- Logic and Science of Computational Logic
- Complexity Theory, Computer Algebra, and Science of Computational Logic

For the module TCSL, oral examinations of approx. 20-30 mins are held on individual appointment. If you want to take such an exam, please send me a mail.

The following literature is relevant for the lecture:

- Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994
- Michael Sipser. Introduction to the Theory of Computation, PWS, 1997
- Ingo Wegener. Complexity Theory. Exploring the Limits of Efficient Algorithms, Springer, 2005
- Oded Goldreich. Computational Complexity: A Conceptual Perspective. Forthcoming, draft available online

- Script by Ian Hodkinson for more details on the basics of complexity theory
- Script by Erich Grädel for a more advanced (and dense) exhibition

Carsten Lutz