Course announcement: DD2445 Complexity Theory, 7.5 ECTS Credits

First two lectures on Tue Sep 5 at 13-15 in 1537 and Fri Sep 8 at 10-12 in 4523.

This is an advanced course at MSc and PhD level which should also be a great choice for PhD students in computer science and mathematics who want to take a course on computational complexity theory as part of their breadth requirement. If you love both mathematics and computers, then here you will get the best of both worlds!

More information at

BRIEF COURSE DESCRIPTION

Computers are everywhere today---at work, in our cars, in our living rooms, and in our pockets---and have changed the world beyond our wildest imagination. Yet these marvellous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What are the limits of what can be done by such mechanical calculations?

Complexity theory gives this deep and fascinating philosophical question a crisp mathematical meaning. The goal is to understand the power of computers but also---and above all---the limitations of what problems can be solved by them, or more broadly by any type of automated computational process.

This course will give an introduction to complexity theory, survey some major research results, and present open problems that are the focus of current research (probably with a slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art).