General
- Lectures 7 Jan - 27 Mar, Mon & Wed 10-12, lecture room T3.
- Tutorial sessions 9 Jan - 3 Apr, Wed 12-14, meeting room B337. NB: Tutorials start already in the first week of the course.
- Teaching assistants' office hours 11 Jan - 5 Apr, Fri 1-2 p.m.
- First midterm Mon 18 Feb 9-12, lecture hall T1.
- Second midterm Tue 9 Apr 13-16, lecture hall T1.
The course is worth 5 credits. The language of instruction is English.
The lectures are given by Pekka Orponen (B331) and the tutorial sessions are conducted by Juho Hirvonen (B314) and Gorav Jindal (C214).
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. 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.
MATERIALS. Lecture slides and homework problem sets will be posted online on MyCourses. The main reference text is the book Computational Complexity: A Modern Approach by S. Arora and B. Barak (2009). A draft version of this 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.
In addition to the midterms, there are 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
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.