Credits: 5

Schedule: 03.01.2018 - 03.04.2018

Teaching Period (valid 01.08.2018-31.07.2020): 

III - IV (Spring)

Learning Outcomes (valid 01.08.2018-31.07.2020): 

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.

Content (valid 01.08.2018-31.07.2020): 

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.

Assessment Methods and Criteria (valid 01.08.2018-31.07.2020): 

Exams and exercises.

Study Material (valid 01.08.2018-31.07.2020): 

Lecture slides and exercises.

S. Arora and B. Barak: Computational Complexity – A Modern Approach, Cambridge U.P. 2009.

C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994. 

Substitutes for Courses (valid 01.08.2018-31.07.2020): 

T-79.5103 Computational Complexity Theory

Prerequisites (valid 01.08.2018-31.07.2020): 

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.

Grading Scale (valid 01.08.2018-31.07.2020):