Introduction to Complexity Theory

Complexity Theory studies the computational properties of decision problems. In this course, we introduce some of the most important notions of complexity theory. We define the basic complexity classes (P, NP, PSpace, etc.) and provide tools for showing that a problem belongs to, or is as hard as any problem in these classes.
The course is aimed to students with little or no knowledge of the topic.

The lecture takes place once a week in room E05: Wednesdays 9:20–10:50.

Announcements:

• On 9th July, there will be a lecture instead of an exercise session.
• On 25th June, there will be a lecture instead of an exercise session. In return, on 27th June, there will be an exercise session.
• On 13th June, there will be an exercise session instead of a lecture.
• On 23rd May, there will be an exercise session instead of a lecture.
• On 30th April, there will be a lecture instead of an exercise session.
• The exercise session will start on 16th April.
• The lecture will start on 4th April.

SWS: 2/1/–

This course can be used in the following modules:

• Bachelor-Studiengang Informatik: INF-B-510 (Vertiefung), INF-B-520 (Vertiefung zur Bachelor-Arbeit)
• Master/Diplom-Studiengang Informatik: INF-BAS6 (Theoretische Informatik), INF-VERT6 (Theoretische Informatik)
• Master in Computational Logic: MCL-TCSL (Theoretical Computer Science and Logic), MCL-PI (Principles of Inference), MCL-KR (Knowledge Representation), MCL-MV (Modeling and Verification)
• Diplom-Studiengang Informatik (Studienordnung 2004): Fachgebiet Theorie der Programmierung, Fachgebiet Intelligente Systeme

An exercise session will be held every second week by Marcel Lippmann on Mondays 9:20–10:50 in room E05.

Exercise sheets will be available here approximately one week before the session.

• Exercise Sheet 1 (16th April); Solution for Ex. 1, which can be read using JFLAP
• Exercise Sheet 2 (14th May)
• Exercise Sheet 3 (23rd May)
• Exercise Sheet 4 (11th June)
• Exercise Sheet 5 (13th June)
• Exercise Sheet 6 (27th June)

The following books are relevant for the lecture:

• Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994.
• Michael Sipser. Introduction to the Theory of Computation, PWS, 1997.

The script by Ian Hodkinson also provides some of the basics (starting from Part III).