School of
Electrical Engineering
and Computer Science

DD2446 Complexity theory

Below you find information about

Schedule Professor Who may take this course?
Goals Course material
Short overview Examination

Changes will be announced under news.


 F ti 10-11 v 35   E35 
 F fr 9-10 v 35   E51 
 F ti 13-14 v 36   D3 
 F to 15-16 v 36   D34 
 F ti 10-12 v 37   Q33 
 F to 15-17 v 37   D34 
 F ti 14-15 v 38   L21 
 F to 15-16 v 38   D34 
 F ti 10-11 v 39   E32 
 F fr 15-16 v 39   D34 
 F ti 15-16 v 40   D34 
 F to 15-16 v 40   M31 
 F fr 14-15 v 40   E36 
 F ti 15-16 v 41   Q26 
 F fr 13-14 v 41   D41 



Johan Håstad, <>, 790 6289, rum 1435, no offical office-hours make agreement by email to meet.

Email is the preferred way to contact Johan.


Who may take the course

The course is open to anyone but the target audience is D4, F4 and the MD-line of SU. The course assumes a working knowledge of efficient algorithms.


The goals of the course

The goals of the course are

  • to give an overview of modern complexity theory
in order for the student to
  • understand the notions of complexity classes and complete problems
  • be able to prove statements in complexity theory,
  • be able to read (simple) research papers in complexity theory.


Course material


We use the book Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.

For the more basic material the set of notes by Johan Håstad might be useful.


Short overview

Will be discussed at the first lecture. As the number of lectures have been halved since the last time the course ran, some adjustments have to be made compared to previous years.



Probably we will have three sets of homework problems but this will be decied firmly at the first lecture.

Please note the Nada code of honor that applies to all our courses.

Published by: Johan Håstad <>
Updated 2011-07-25