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. Additionally, there is a fortnightly tutorial held by Dr. Marcel Lippmann. Exercise sheets will be available approximately one week before the tutorials.

The lectures and the tutorials will take place in room E05 at the following times: Mondays 13:00-14:30 and Tuesdays 9:20-10:50. The exact distribution of lectures and tutorials can be found in the table below.

	Monday	Tuesday
13 Oct. – 17 Oct.	—	Lecture
20 Oct. – 24 Oct.	—	Lecture
27 Oct. – 31 Oct.	Tutorial (exercise sheet 1)	Lecture
3 Nov. – 7 Nov.	—	Lecture
10 Nov. – 14 Nov.	Tutorial (exercise sheet 2)	Lecture
17 Nov. – 21 Nov.	—	Lecture
24 Nov. – 28 Nov.	Lecture	Lecture
1 Dec. – 5 Dec.	Tutorial (exercise sheet 3)	Lecture
8 Dec. – 12 Dec.	—	Lecture
15 Dec. – 19 Dec.	Tutorial (exercise sheet 4)	Lecture
5 Jan. – 9 Jan.	—	—
12 Jan. – 16 Jan.	Tutorial (exercise sheet 5)	Lecture
19 Jan. – 23 Jan.	—	Lecture
26 Jan. – 30 Jan.	Tutorial (exercise sheet 6)	Lecture
2 Feb. – 6 Feb.	—	Lecture

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

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