Computational Complexity

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. **Module 1, Concepts, results and proofs, 3 ECTS credits**, consists of lectures that introduce and discuss concepts, results and their proofs according to the above contents desciption. Every lecture is related to one ore more sections of the textbook and provides an introduction to the material without considering any details. The goal is to make it easier for the student to obtain a deeper understanding by working with the material themselves. **Module 2, Deepening, reflection, and discussion, 4.5 ECTS credits,** consists of the student's own work with the textbook, and student-guided discussion sessions. When the teacher has presented an overview of sections in the textbook, the student reads those sections and prepares a basic presentation of the material as a basis for discussion with the classmates. A mandatory summary of the central points is handed in before the next lecture (about 1 page). The summary shall in particular mention aspects the student did not manage to comprehend or feels uncertain about. The same holds for possible exercises that the teacher may specify to provide guidance. Students will then be selected in random order to present the material based on their own understanding, and to lead the discussion in the class. Every student has to make at least one such presentation.