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

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.