[TU Dresden]

Complexity Theory

Technische Universität Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Carsten Lutz

Course Description

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.

Organization

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.

Lecture Material

A script of the lecture is available.

Credits / Examinations

This lecture can be used for the foundational module and for the module TCSL. Students can earn 3 credit points.

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:

with 50% of the total points going to both, Logic and Science of Computational Logic, and 25% of the total points going to both, Complexity Theory and Computer Algebra.

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.

Literature

The following literature is relevant for the lecture:

See also:
Carsten Lutz