After successful completion of the course, students are able to
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.
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: