Complexity Theory

Course announcement: DD2446 Complexity Theory, 6 ECTS Credits

First three lectures on Tue Sep 3 at 10-12 in D34, Wed Sep 4 at 13-15 in E33, and Thu Sep 5 at 13-15 in Q36.

This advanced Master's course is also suitable for PhD students in computer science and mathematics who want to take a course on computational complexity theory as part of their breadth requirement.

More information at www.csc.kth.se/utbildning/kth/kurser/DD2446/kplx13/ .

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).