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.

Organisation

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/Modules

SWS: 2/1/–

This course can be used in the following modules:

Literature

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