Course home page
OVERVIEW. CS-E4530 Computational complexity theory is a master's level course introducing the basic mathematical theory of analysing the hardness of computational problems, i.e., the basic toolset for understanding what makes some computational problems difficult to solve.
- Second midterm Tuesday April 3 at 13:00-16:00 (Room T1)
- Lectures Monday 10-12, Wednesday 10-12 (Room T3).
- Exercise sessions Tuesday 10-12 (B337).
The course is worth 5 credits. The language of instruction is English.
The lectures are given by Janne H. Korhonen. Teaching assistants are Tuomo Lempiäinen and Abdulmelik Mohammed.
PREREQUISITES. Automata and formal languages. Deterministic and nondeterministic Turing machines. Decidable and undecidable problems (e.g. CS-C2150 / ICS-C2000 Theoretical Computer Science). Basics of discrete mathematics.
CONTENT. Basic concepts of complexity theory: models of computation, complexity measures including time and space, reductions, complexity classes and completeness. Complexity classes: P, NP and coNP; PSPACE, LOGSPACE, EXPTIME. Advanced topics such as the polynomial hierarchy, approximation, randomised computation, circuits and parallel computation, fine-grained complexity, and relativisations.
MATERIAL. Lecture slides and exercise sets will be posted online. The main reference text is the textbook Computational Complexity: A Modern Approach by Arora and Barak. A draft version is available freely online (http://theory.cs.princeton.edu/complexity/).
EXERCISES AND GRADING. The course has two midterm exams, graded pass/fail. You are required to pass both exams to pass the course.
In addition to the midterms, there are 10 sets of weekly exercises. Each exercise set except the first is worth 8 points (the first is 14 points), for a maximum of 86 points. The number of points from the exercises will determine your final grade:
- 1/5: pass midterms
- 2/5: pass midterms + at least 16 points
- 3/5: pass midterms + at least 32 points
- 4/5: pass midterms + at least 48 points
- 5/5: pass midterms + at least 64 points
DOING THE EXERCISES. You are allowed and encouraged to work together with your fellow students on exercises, and you can get help from the teaching assistants during the weekly exercise session. However, you must write up your final solutions by yourself, completely in your own words.
You should return your answers to the exercises via MyCourses. The deadline for each weeks' exercises is on midnight on Friday. Answers must be submitted as a easily readable, single pdf file. Your answers should be self-contained and written with sufficient detail so it is easy to follow your reasoning.
BONUS EXERCISES. In addition to the weekly exercises, there will be some more challenging bonus exercises. These can be completed at any point before the second midterm, and can give extra points on top of the weekly exercises. Practical instructions can be found on the bonus exercise sheets.
DISCUSSION FORUM. The course has a Slack workspace that you can use for discussions and getting help with the exercises. The workspace is available at https://aalto-cct.slack.com.
Sign up at https://aalto-cct.slack.com/signup with your aalto.fi email account.
LEARNING OUTCOMES. Once you have taken the course, you master the central concepts of computational complexity theory and are able to use these concepts to analyse the complexity of computational problems. You can formulate a concrete real-world computational task as a formal computational problem and formally reason about its computational complexity in comparison with well-known problems and complexity classes. You can use reductions and other complexity-theoretic concepts to identify which algorithmic tools — such as randomisation, approximation, parameterisation and parallelism – can and cannot help with the efficient solution of a given problem.