After successful completion of the course, students are able to

• explain fundamental complexity classes and their intuition
• carry out complexity analyses of problems (in particular in the Polynomial Hierarchie)

Basic notions of complexity theory, deterministic und non-deterministic complextiy classes, NP-complete problems, logarithmic space, the polynomal hierarchy, exponentially hard probleme, applications.

The material (including exercises) is presented by the lecturer.

Remark: The course in the WS 2022 is planned to be held in person. If required by the Covid situation, the course will be held online via Zoom. All dates and times (classes as well as written exam) remain the same in this case.

ECTS Breakdown

  2 h quiz 
 30 h lecture (12 classes including preparation)
 40 h exam preparation 
  3 h written + oral exam
-----------------------------------------------------------
 75 h = 3 Ects

Assessment consists of 3 components:

• entrance test
• exercises
• written and/or oral exam at the end (details to be announced in the first class)

• Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory (to the extent taught in the course "Formale Methoden der Informatik").
• Moreover, students should have basic mathematical skills (like carrying out proofs by induction) as taught in the mathematics courses in the bachelor studies.