DD2445/FDD3445 Complexity Theory, 7.5 credits

This is an advanced course in theoretical computer science which is usually given every second year (alternating with DD2442 Seminars on Theoretical Computer Science) during periods 1 and 2.

The course is open to anyone, but the main target audience are Master's students in computer science and mathematics. The course is also suitable for PhD students in mathematics or computer science who have not previously taken a dedicated course on computational complexity theory. Master's (or Bachelor's) students take the course with course code DD2445. For PhD students there is a research-level version FDD3445. For this version the requirements are slightly tougher and the grading is only pass/fail, but the course counts fully towards the course credit requirements in the PhD program.

Up to 2013, the course had a different course code and was known as DD2446 Complexity Theory.

This course was last given during the autumn of 2017 and will probably be given next time during the autumn of 2019.

Short Overview

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 is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations?

Complexity theory gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. Complexity theory focuses on classifying computational problems according to their inherent difficulty, and on relating those classes of problems to each other. 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. A problem is regarded as inherently difficult if its solution requires unreasonably large resources regardless of which approach is used to solve it (i.e., no matter which algorithm is employed). Complexity theory formalizes this notion by introducing mathematical models of computation and quantifying the amount of resources needed to solve the problems, such as running time, memory usage, parallelism, communication, et cetera.

This course is intended to

• give an introduction to computational complexity theory,
• survey some of the major results in this area, and
• present some of the open problems that are the focus of current research,

so that that students after having completed the course

• will have a good grasp of the fundamentals of complexity theory,
• will be able to describe, at least in general terms, some of the tools and techniques used in the area,
• will be able to use these tools and techniques to solve and present their own solutions of problems in complexity theory orally and in writing, and
• will have the necessary backgound to be able to read and understand research articles on complexity theory.

While the intention is to give a fairly broad coverage, it should be noted that the course might at times have a slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art.