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