School of
Computer Science
and Communication
KTH / CSC / Education / Courses / 2D1446 / Kplx06

2D1446 Complexity theory

An official course will be handed out separately once it is is ready. The coure will be similar to the course given two years ago so please use that as an approximation for the time being.

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 to 13-15 v 11   E32 
 F ti 15-17 v 12-14, 16-19   E32 
 F to 13-15 v 12-13   Q21 
 F to 13-15 v 14,16-17   L51 
 F to 13-15 v 18   V21 
 F to 10-12 v 19   E34 



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


  • C. H. Papadimitriou: Computational complexity, Addison Wesley, 1994.

Additional material

First set of lecture notes.

Intermediate set of lecture notes on Cook's theorem.

Last set of lecture notes.


Short overview

A preliminary plan is given as follows

F1-3 Administration. Introduction to complexity theory and complexity classes. Models of computation and computability. Time and memory. (Chapter 1-3)
F4-9 Complexity classes (P, NP, coNP, L, NL, PSPACE), reductions and complete problems. (Chapter 7-10).
F10-12 Randomized algorithms (Chapter 11), approximation algorithms and approximability (Chapter 13).
F13-15 Additional material to be discussed with course participants. Please make suggestions!



We will have three sets of homework problems. Written solutions will be handed in and discussed orally.

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

Published by: Johan Håstad <>
Updated 2006-05-31