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. Students solve exercises and submit the solutions.

ECTS Breakdown

  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:

• 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.