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.
- Lectures 13 Jan - 1 Apr, Mon & Wed 10-12, lecture room T3.
- Tutorial sessions 15 Jan - 1 Apr, Wed 14-16, lecture room T4. NB: Tutorials start already in the first week of the course.
- Teaching assistants' office hours Fridays 13-14 (G. Jindal C214, J. Studený B313).
- First midterm Mon 17 Feb 9-12, lecture hall T1.
- Second midterm Tue 7 Apr 13-16, lecture hall T1.
The course is worth 5 credits. The language of instruction is English.
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.
CONTENTS. Models of computation: Turing machines, RAM machines, Boolean circuits. Modes of computation: deterministic, nondeterministic, parallel, randomised, alternating. Basic notions of computational complexity: complexity measures and complexity classes, hierarchy theorems, reductions between problems, completeness. Central complexity classes: P, NP, PSPACE, NC, polynomial time hierarchy, etc. Design of completeness proofs, especially for NP-completeness. Applications and extensions: approximability, counting, games, fine-grained complexity.
MATERIALS. Lecture slides and homework problem sets are posted online on MyCourses. The main reference text is Computational Complexity by C. Papadimitriou (1994). A more recent textbook is Computational Complexity: A Modern Approach by S. Arora and B. Barak (2009). A draft version of the latter is available online at http://theory.cs.princeton.edu/complexity/.
EXAMS, HOMEWORK AND GRADING. The course has two midterm exams, graded at 10 points and 30 points.
Course credit is also awarded for 10 weekly homework problem sets. Each problem set counts for 6 points, for a maximum of 60 points. The points accumulated from the exams and the homework problems determine the final grade as follows:
- 1/5: 40 points
- 2/5: 50 points
- 3/5: 60 points
- 4/5: 70 points
- 5/5: 80 points
In addition, there is a threshold requirement that in order to pass the course, you need to achieve at least 20 points from the two midterms, combined.
DOING THE HOMEWORK. You are allowed and encouraged to work together with your fellow students on the homework problems, and you can get help from the tutorial assistants during the weekly tutorial sessions and the assistants' office hours. However, you must write up your final solutions to the homework problems by yourself, without written notes from such background discussions.
Your solutions should be well-justified, precise, and clearly explained with sufficient detail so that it is easy to follow your reasoning. Return your solutions via MyCourses as an easily readable, single pdf file which is either typeset or written in full sentences in clean handwriting.
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.