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 in room E05: Wednesdays 9:20–10:50.



SWS: 2/1/–

This course can be used in the following modules:


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.


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