[TU Dresden]

Complexity and Logic

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

Prof. Franz Baader

Course Description

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.

Organization

The lecture takes place twice a week in room GRU 350: Tuesday 16:40-18:10 (DS6) and Thursday 16:40-18:10 (DS6).

Lecture Material

A script for this lecture is not availble. Therefore, students are advised to copy what is written on the blackboard.

Exercises

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.

Credits / Examinations

Computational logic students can earn 9 credits by attending this lecture. The lecture can be used for the module TCSL. In order to get the credits, CL students have to do meet both of the following two obligations:
  1. present at least four exercises in front of the exercise group;

  2. pass an oral examination at the end of the term.
Computer Science students are not obliged to present exercises, but are invited to do so.

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.

Literature

Carsten Lutz