Computational Complexity, 7.5 Credits

Contents

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.

Expected learning outcomes

Knowledge and understanding
Upon completion of the course, the student will, with mathematical accuracy, be able to define, explain and discuss

• (FSR 1) the concept of computational complexity with respect to execution time and memory space, and connections between them,
• (FSR 2) the most central complexity classes and how they are related,
• (FSR 3) the main open issues regarding the relationships between these complexity classes,
• (FSR 4) recurring methods used to prove the relationship between complexity classes, in particular "reachability method" or specific problems, especially reductions between problems.

Competence and skills
Upon completion of the course, the student should be able to

• (FSR 5) independently read a formal mathematical text (the textbook), present it to others, and discuss both the acquired knowledge and possible difficulties,
• (FSR 6) with mathematical accuracy reason about the meaning, formalization and use of the terms computational problem, computational complexity, and completeness, and the relationships between them,
• (FSR 7) based on given examples, create reductions between problems, formulate them in writing, and utilize them to prove that a problem is complete for a given complexity class.

Judgement and approach
Upon completion of the course, the student should be able to

• (FSR 8) critically and in a knowledge-based manner orally discuss the practical significance and limitations of the theoretical results with peers.

Required Knowledge

At least 90 ECTS, including 60 ECTS Computing Science. At least 7.5 ECTS discrete mathematics; 7.5 ECTS data structures and algorithms; and 7.5 ECTS formal languages. Proficiency in English equivalent to the level required for basic eligibility for higher studies.

Form of instruction

The teaching is as described in section Contents and consists of both overview lectures and student-led presentations and discussions of the material.

Examination modes

Module 1 (FSR 1-4, 6-8) is examined by a written exam in halls. The grades given on this module are Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5).

Module 2 (FSR 1-8) is examined by written assignments and oral presentations. In Module 2, one of the grades Fail (U) and Pass (G) is given.

On the course in its entirety, one of the grades Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5) is given. The grade on the course is determined by the grade on Module 1.

Adapted examination
The examiner can decide to deviate from the specified forms of examination. Individual adaptation of the examination shall be considered based on the needs of the student. The examination is adapted within the constraints of the expected learning outcomes. A student that needs adapted examination shall no later than 10 days before the examination request adaptation from the Department of Computing Science. The examiner makes a decision of adapted examination and the student is notified.

Other regulations

This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If in
doubt, consult the student counselors at the Department of Computing Science and / or the program director of your
program.

If the syllabus has expired or the course has been discontinued, a student who at some point registered for the course is guaranteed at least three examinations (including the regular examination) according to this syllabus for a maximum period of two years from the syllabus expiring or the course being discontinued.