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. Students solve exercises and submit the solutions.
2 h quiz 30 h lecture (12 classes including preparation) 42 h exam preparation 1 h exam----------------------------------------------------------- 75 h = 3 Ects
Assessment consists of 3 components: