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 is presented by the lecturer. The students have to solve exercises.
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: