Complexity theory is an important addition to the theory of algorithms. Its aim is to understand why certain computational problems are difficult and to classify them according to their difficulty. The best known and most important example is the theory of NP-completeness. The course is taught in English and especially covers topics from following list:

• Complexity classes, P vs. NP
• Reductions and completeness
• Space complexity
• Hierarchy theorems
• Relativization and oracle Turing machines
• Polynomial-time hierarchy
• Probabilistic complexity classes

After registering in PAUL for this course, you are enrolled (up to 24 hours later) to our PANDA course via which we organise everything. Especially, we provide material and make announcements only via this PANDA course. If the automatic enrollment does not work for you, please contact us.

Every week we will publish two types of exercises:
1) Exercises which you will solve in tutorials under the guidance of a tutor.
2) Homework, which you will have to complete in order to achieve the course achievement ("Studienleistung") required for admission to the oral exam. In addition, you can reach up to two bonus steps, which will count towards the result of the exam. We announce the requirements for course achievement and bonus steps in the first weeks of lectures.

The final exam will be an oral exam, roughly spanning 40 minutes. During the lecture-free time we will offer two examiniation periods, one usually at the beginning and one at the ende. We will announce the concrete periods via PANDA.