Computational Complexity

About the course

Some algorithms solve a computational problem more efficiently than others. An important aspect of working as a computer scientist is to find efficient ways to solve a given problem. Sometimes one is successful, sometimes not. But how do we know in the latter case whether this is due to our own inability or lies in the nature of the problem, i.e. whether the problem can be solved effectively at all? Each problem has an inherent computational complexity that determines if it is solvable and, if so, how efficiently it can be solved. This leads to a categorization of problems in different classes with regard to their inherent complexity. Understanding this is important because it shows which level of efficiency one can reasonably expect. On the one hand, this leads to more efficient algorithms to the extent possible. On the other hand, it prevents the computer scientist from wasting energy by trying to achieve the impossible.

The course addresses and formalises this inherent complexity of computational problems, resulting in the categorization of problems into different complexity classes, known and unknown relationships between these classes, and the concept of complete problems. The following aspects are addressed: Formalization of computational complexity (primarily in terms of time and memory space) and its practical significance, the speedup theorem and the extended Church-Turing thesis, deterministic and non deterministic complexity classes (predominantly (N)TIME(f(n)), (N)SPACE(f(n)), P, NP, (N)EXPTIME, L, NL, PSPACE; complement classes to those) and what is known or unknown about their mutual relationship, reducing a problem to another one, completeness.