Introduction to Complexity Theory

Dr. Rafael Pe├▒aloza

Course Description

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)
3 Nov. – 7 Nov. Lecture
10 Nov. – 14 Nov. Tutorial
(exercise sheet 2)
17 Nov. – 21 Nov. Lecture
24 Nov. – 28 Nov. Lecture Lecture
1 Dec. – 5 Dec. Tutorial
(exercise sheet 3)
8 Dec. – 12 Dec. Lecture
15 Dec. – 19 Dec. Tutorial
(exercise sheet 4)
5 Jan. – 9 Jan.
12 Jan. – 16 Jan. Tutorial
(exercise sheet 5)
19 Jan. – 23 Jan. Lecture
26 Jan. – 30 Jan. Tutorial
(exercise sheet 6)
2 Feb. – 6 Feb. Lecture


SWS: 2/1/–

This course can be used in the following modules:


The following books are relevant for the lecture: The script by Ian Hodkinson also provides some of the basics (starting from Part III).