DD2445 Complexity Theory 7.5 credits

Komplexitetsteori

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 will give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there will probably be a slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art.

Show course information based on the chosen semester and course offering:

Offering and execution

No offering selected

Select the semester and course offering above to get information from the correct course syllabus and course offering.

Course information

Content and learning outcomes

Course contents *

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 will give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there will probably be a slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art.

Intended learning outcomes *

After having completed the course, the student should be able to:

  • Define and motivate basic concepts in complexity theory and explain how these concepts are related to one another.
  • Describe the most important research results in modern complexity theory.
  • Use standard tools and techniques in modern complexity theory to prove basic theorems and independently solve problems amenable to these methods.
  • Present complexity-theoretic arguments with mathematical stringency orally and in writing.
  • For the highest grade: read and understand a research article in complexity theory, and display this understanding by giving an oral presentation of the paper.

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

No information inserted

Recommended prerequisites

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 computer science or mathematics who have not previously taken a dedicated course on computational complexity theory. You need to have taken DD1352 Algorithms, Data Structures, and Complexity or DD2352 Algorithms and Complexity or corresponding courses at other universities, and should feel comfortable with that material. You will also need mathematical maturity and a willingness to learn new stuff. This will be a demanding course, but hopefully even more fun! The lectures will be given in English.

Equipment

No information inserted

Literature

The course literature will be announced no later than 4 weeks before the start of the course. The academic year 2013/14 the book used was “Computational Complexity: A Modern Approach” by Sanjeev Arora and Boaz Barak published by Cambridge University Press. Part of the course will also be based on research articles.

Examination and completion

Grading scale *

A, B, C, D, E, FX, F

Examination *

  • ÖVN1 - Exercises, 7.5 credits, Grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

  • ÖVN1 - Written assignments, 7.5 credits, grading scale: A, B, C, D, E, FX, F

In this course, the code of honour of the school is applied, see: http://www.kth.se/csc/student/hederskodex.

Other requirements for final grade *

Written assignments (ÖVN1; 7.5 credits).

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Johan Håstad

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web DD2445

Offered by

EECS/Computer Science

Main field of study *

Computer Science and Engineering

Education cycle *

Second cycle

Add-on studies

No information inserted

Contact

Jakob Nordström (http://www.csc.kth.se/~jakobn/)

Ethical approach *

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Supplementary information

In this course, the EECS code of honor applies, see:
http://www.kth.se/en/eecs/utbildning/hederskodex